超立方体系统中基于安全通路向量的容错路由

n维超立方体结构的多处理机系统在并行与分布式处理中具有良好的性能.随着多处理机系统规模的增大,系统出现链路与节点故障的概率也随之增大,因此设计容错性更强的路由算法对n维超立方体结构的多处理机系统具有重要意义.针对系统中存在链路故障的情况,提出了用于记录最优通路的安全通路向量(safety path vectors,简称SPVs)概念,并给出了建立SPVs及其容错路由算法.其中SPVs的赋值可以通过n-1轮邻节点之间的信息交换来完成,且算法中各节点的存储开销仅为n bits,因此,SPVs是安全向量(SVs)与扩展安全向量(ESVs)的一种扩展,具有比SVs和ESVs更好的记录最优通路的能力.另外，与基于最优通路矩阵(optimal path matrices,简称OPMs)及扩展最优通路矩阵(extended optimal path matrices,简称EOPMs)的容错路由算法相比,SPVs呈指数级地降低了算法的存储开销，且能够记录OPMs和EOPMs所不能记录到的最优通路信息.理论分析和仿真实验验证了SPVs的上述性能.     

基于NPV广义超立方体最佳容错路由算法

在网络可靠性研究中,设计较好的容错路由策略、尽可能多地记录系统中最优通路信息,一直是一项重要的研究工作.超立方体系统的容错路由算法分为可回溯算法和无回溯算法.一般说来,可回溯算法的优点是容错能力强:只要消息的源节点和目的节点有通路,该算法就能够找到把消息传递到目的地的路径;其缺点是在很多情况下传递路径不能按实际存在的最短路径传递.其代表是深度优先搜索(DFS)算法.无回溯算法是近几年人们比较关注的算法.该算法通过记录各邻接节点的故障信息,给路由算法以启发信息,使消息尽可能按实际存在的最短路径传递.这些算法的共同缺点是只能计算出Hamming距离不超过n的路由.在n维超立方体系统连通图中,如果系统存在大量的故障,不少节点对之间的最短路径大于n,因此,这些算法的容错能力差.提出了一个实例说明采用上述算法将遗失60%的路由信息.另外,由于超立方体的结构严格,实际中的真正超立方体系统不多.事实上,不少的网络系统可转换为具有大量错误节点和错误边的超立方体系统.因此,研究能适应具有大量错误节点和错误边的超立方体系统的容错路由算法是一个很有实际价值的工作.研究探讨了:(1) 定义广义超立方体系统;(2) 在超立方体系统中提出了节点通路向量(NPV)概念及其计算规则;(3) 提出了中转点技术,使得求NPV的计算复杂度降低到O(n);(4) 提出了基于NPV的广义超立方体系统最佳容错路由算法(OFTRS),该算法是一种分布式的和基于相邻节点信息的算法.由于NPV记录了超立方体系统全部最优通路和次最优通路的信息,在具有大量故障的情况下,它不会遗漏任何一条最优通路和次最优通路信息,从而实现了高效的容错路由.在这一点上,它优于其他算法.     

超立方体多处理机系统中基于扩展最优通路矩阵的容错路由

该文在高峰等文章的基础上，提出了针对超立方体结构多处理机系统的扩展最优通路矩阵（Extended Optimal Path Matrices,EOPMs）的概念，并给出了一个建立EIPMs的算法和基于EOPMs的容错路由算法，证明了基于EOPMs的容错路由算法是基于扩展安全向量（ESVs）^[13]和基于最优通路矩阵（OPMs)^[14]容错路由算法的扩展，与原文相比，该算法的存储开销与OPMs,相同，但记录的最优通路的信息，包含了原文所记录的最优通路的信息，使搜索最优通路的能力比它们有进一步的提高。     

用最优通路矩阵实现超立方体多处理机系统的容错路由

针对拓扑结构为超立方体的多处理机系统提出了最优通路矩阵（ＯＰＭ）的概念,并约出了一个基于最优通路矩阵的路由算法。存储于超产方体各节点中的最优通路矩阵记录系统中的故障信息,用于判定消息的源节点和目的节点之间是否存在最优通路（长度等于两节点间Ｈａｍｍｉｎｇ距离的通路）。对于ｎ维超方立体,每个节点所需的存储开销为ｎ＾２个字,基于最优通路矩阵的路由算法所选的通路的长度不超过两点间的Ｈａｍｍｉｎｇ距离加２。     

超立方体中基于极大安全通路矩阵的容错路由

n维超立方体结构的多处理机系统在并行与分布式处理中具有良好的性能,随着多处理机系统规模的增大,系统出现链路与节点故障的概率也随之增大,因此设计容错性更强的路由算法对n维超立方体结构的多处理机系统具有重要意义.针对超立方体结构的多处理机系统中存在链路故障的情况,提出了用于最优通路记录的极大安全通路矩阵(maximum safety path matrices,简称MSPMs)这一概念,给出了一种建立MSPMs及其容错路由算法.证明了MSPMs通过n-1轮邻节点之间的信息交换,能以矩阵的形式记录最多的最优通路     

故障超立方体网络中的路由算法

针对超立方体结构的多处理机系统中存在故障的情况,提出了一个应用于超立方体网络的容错路由算法。该容错路由算法是基于局部信息的,只需要知道邻节点的状态,而无需知道整个网络的运行情况。对于给定的源节点和目的节点,路由算法均能够找到一条最优通路,并且可以预防死锁。模拟实验结果表明,路由算法所构造的路径长度接近于两个节点之间的最优路径长度。     

基于局部扭曲立方体的单播容错路由算法

对n维局部扭曲立方体存在节点故障时,提出了一种基于节点安全级概念的单播容错路由算法。该算法除了考虑邻接节点的安全状况外,还充分利用了局部扭曲立方体自身特有的结构,使得信息尽可能沿最优路径传递。通过模拟仿真实验可知,算法具有较高的容错能力。当故障节点的数目达到或超过一半时,算法仍能保持一个相当高的容错路由成功率,且算法所选路径在多数情况下是最优路径。     

超立方体网络下的自适应容错路由研究*

针对超立方体结构的多处理机系统出现故障的问题,对容错超立方体网络的局部连通性进行了研究。根据局部连通性的特点定义了相邻节点集合类的概念,提出并证明了求解两类相邻节点集合的公式。给出了满足任意子连通性条件的超立方体网络的自适应容错路由算法。该算法是分布式和基于局部信息的,可以预防死锁。仿真实验的结果表明算法是高效的,且构建的路径长度接近于最优路径长度。     

基于超立方体容错路由算法分析*

基于超立方体的优良的拓扑性质,提出了一个应用于超立方体网络的容错路由算法.该容错路由算法是基于局部信息的,因为路由算法在路由过程中,只需要知道其邻节点的信息,而无须知道其他节点的出错情况.对于给定的源节点和目的节点,路由算法均能够找到一条最优容错路径,并且可以预防死锁.模拟实验结果表明,路由算法所构造的路由路径长度接近于两个节点之间的最优路径长度.     

故障超立方体网络中的高效容错路由算法研究

对超立方体网络中具有大量节点和链路故障模式进行了研究,提出了两类"子连通性"即k-维子连通性和任意子连通性的概念;基于两类子连通性概念,分别给出了两个满足该两类子连通性条件的超立方体网络的分布式容错路由算法.证明了已有的两类局部连通性概念中的条件"错误节点数小于正确节点数"是不必要的.提出的两个子连通性概念是两类局部连通性概念的最大扩展,可以在更大程度上保证整个超立方体网络的全局连通性,是已有的两类局部连通性概念的一种完全扩展.     

Reliable Communication on Cube-Based Multicomputers

We consider a distributed unicasting algorithm for hypercubes with faulty nodes(including disconnected hypercubes)using the safety level concept.The safety level of ach node in an n-dimensional hypercube in an approximated measure of the number and distribution of faulty nodes in the neighborhood and it can be easily calculated through n-1 rounds of information exchange among neighboring nodes.Optimal unicasting between two nodes is guaranteed if the safety level of the source node is no less than the Hamming distance between the source and the destination.The feasibility of an optimal or suboptimal unicasting can be easily determined at the source node by comparing its safety level,together with its neighbors‘ safety levels,with the Hamming distance between the source and the destination.The proposed scheme is also the first attempt to address the unicasting problem in discronnected hypercubes.The safety level concept is also extended to be used in hypercubes with both faulty nodes and links and in generalized hypercubes.     

Adaptive fault-tolerant routing in cube-based multicomputers usingsafety vectors

Reliable communication in cube-based multicomputers using the safety vector concept is studied in this paper. In our approach, each node in a cube-based multicomputer of dimension n is associated with a safety vector of n bits, which is an approximated measure of the number and distribution of faults in the neighborhood. The safety vector of each node can be easily calculated through n-1 rounds of information exchange among neighboring nodes. Optimal unicasting between two nodes is guaranteed if the kth bit of the safety vector of the source node is one, where k is the Hamming distance between the source and destination nodes. The concept of dynamic adaptivity is introduced, representing the ability of a routing algorithm to dynamically adjust its routing adaptivity based on fault distribution in the neighborhood. The feasibility of the proposed unicasting can be easily determined at the source node by comparing its safety vector with the Hamming distance between the source and destination nodes. The proposed unicasting can also be used in disconnected hypercubes, where nodes in a hypercube are disjointed (into two or more parts). We then extend the safety vector concept to general cube-based multicomputers     

具有大量错误结点的超立方体网络中并行路由算法

本文讨论具有大量错误结点的超立方体网络中的并行路由算法。假定Hn是一个局部k-维子立方体连通用的n-维超立方体网络,本文提出的并行路由算法能够找出至少K=min（Dk(u),Dk(v）条并行路径,其中每一条路径的长度不超过（dH(Uk,Vk）＋3）2^k。该算法的时间复杂度为O（Kn2^k）。这里,Dk(u）和Dk(v）分别代表源结点u和目的结点v的正确的邻结点个数（不考虑u和v所在的k－维子立方体内部的邻结点）,dH(Uk,Vk）代表源结点u和目的结点v所在的两个k－维子立方体Uk和Vk之间的海明距离。本文还考察了了k=3的特殊情况,在k=3并且有分别不超过12．5％和25％的错误结点的情况下,该算法的时间复杂度为O（Kn）,并且每一条路径的路径长度分别在大约1．5和2倍源结点和目的结点之间的海明距离之内。该算法只要求结点知道其邻结点的状态,而无需知道整个网络信息,也就是说,该算法是基于局部信息的,因而该算法具有很强的实际意义。     

点对点网络容错路由算法的路径长度分析

用概率性分析方法 ,研究了在结点错误概率性分布的情形下超立方体网络点对点容错路由算法的路径长度 ,得出了算法的路径长度期望值 ,分析表明 :对于结点错误概率 p≤ 10时 ,源点 U到终点 V所在的 k维子立方体的路径长度期望值不超过 1.11* h,比以往通常的长度分析结果 2 * h小得多 .提出一种改进的算法并证明这一新算法所构造的路径长度的期望值不大于 1.11h- 0 .11k 2 ,这大大改进了以前的路径 2 h k 2 ,其中 h为 U与 V的 Ham ming距离 .     

网络容错路由算法概率分析的一种新的方法

该文提出了一种新的概率分析方法来研究在给定结点错误概率的情况下超立方体网络强容错路由算法的容错性的概率。针对文中提出的基于新的局部连通性网络容错模型的高效的强容错路由算法犤1犦,该文首次严格证明了一个具有1024个结点的10维超立方体网络能够容许多达4.7%的错误结点而具有99%的概率确保找到正确结点组成的路径,而如果结点的错误概率不超过0.1%,则所有实际规模的超立方体网络能够具有99.9%的概率确保找到正确结点组成的路径。该算法的时间性能是最优的,且该算法构造的路径的长度不超过源结点和目的结点之间海明距离的两倍加上一个很小的常数。     

Depth-first search approach for fault-tolerant routing in hypercubemulticomputers

Using depth-first search, the authors develop and analyze the performance of a routing scheme for hypercube multicomputers in the presence of an arbitrary number of faulty components. They derive an exact expression for the probability of routing messages by way of optimal paths (of length equal to the Hamming distance between the corresponding pair of nodes) from the source node to an obstructed node. The obstructed node is defined as the first node encountered by the message that finds no optimal path to the destination node. It is noted that the probability of routing messages over an optimal path between any two nodes is a special case of the present results and can be obtained by replacing the obstructed node with the destination node. Numerical examples are given to illustrate the results, and they show that, in the presence of component failures, depth-first search routing can route a message to its destination by means of an optimal path with a very high probability     

Embedding and reconfiguration of spanning trees in faultyhypercubes

The problem of tolerating faulty nodes in hypercubes has been studied by many researchers either by using spares or by reconfiguration. Algorithms for tolerating faulty nodes and links in hypercubes are presented. The algorithms are based on using general spanning trees (GST), complete unbalanced spanning trees (CUST), and balanced spanning trees (BST) for reconfiguring the hypercube to avoid faulty nodes and links. The algorithms contain two phases: the first phase involves the construction of the spanning tree and the second one is for reconfiguring the hypercube should a faulty node be detected. The reconfiguration process consists of two basic steps. First, the faulty node is disconnected from the spanning tree. Then, a new spanning tree is constructed by reconnecting the children of the faulty node to the spanning tree. One hundred percent single fault correction (avoidance) and almost 100 percent fault correction (avoidance) of double and triple faults are achieved by the proposed algorithms for hypercubes having a dimension of n⩾6. Simulation results for the algorithm under more than three faults also are presented. For any k faulty nodes (1⩽k⩽2ⁿ-1), the reconfiguration algorithm may be applied k times to avoid these k faulty nodes as long as no combination of any two of the faults results in a blocking situation. The proposed reconfiguration algorithms tolerate all possible single-link faults. The reconfiguration algorithms are extended to tolerate (k⩽n-1) multiple faults, causing blocking situation, with a backtracking     

Near-optimal broadcast in all-port wormhole-routed hypercubes usingerror-correcting codes

A new broadcasting method is presented for hypercubes with wormhole routing mechanism. The communication model assumed allows an n-dimensional hypercube to have at most n concurrent 110 communications along its ports. It further assumes a distance insensitivity of (n+1) with no intermediate reception capability for the nodes along the communication path. The approach is based on determination of the set of nodes (called stations) in the hypercube such that for any node in the network there is a station at distance of at most 1. Once stations are identified, parallel disjoint paths are formed from the source to all stations. The broadcasting is accomplished first by sending the message to all stations which will in turn inform the rest of the nodes of the message. To establish node-disjoint paths between the source node and all stations, we introduce a new routing strategy. We prove that multicasting can be done in one routing step as long as the number of destination nodes are at most n in an n-dimensional hypercube. The number of broadcasting steps using our routing is equal to or smaller than that obtained in an earlier work; this number is optimal for all hypercube dimensions n⩽12, except for n=10     

Unicast-based fault-tolerant multicasting in wormhole-routed hypercubes

A unicast-based fault-tolerant multicasting method is proposed for hypercubes, which can still work well when the system contains enough faults. A multicast message may be unable to reach a destination if Hamming distance between the destination and the multicast source is large enough. A multicast message fails if any one of the destinations is unreachable from the source. An effective destination ordering scheme of the destinations is proposed for one-port systems first, it is extended to all-port systems for unicast-based fault-tolerant multicasting. Unreachable destinations from the source based on the local safety information are forwarded to a reachable destination, where the multicast message can be routed reliably. Destination ordering is completed based on Hamming distance. A multiple round p-cube routing scheme is presented for a deadlock-free fault-tolerant routing for each unicast step in hypercubes, where the same virtual channel is used for each round of p-cube routing. Sufficient simulation results are presented by comparing with the previous methods.     

超立方体互连网络自适应简捷盲寻径搜索算法

根据n-cube超立方体互连网络的并行特点，分析了任意当前结点相邻集合类的求解方法，并给出一种自适应优化盲寻径搜索算法，即通过任一当前结点的Hamming距离相邻测度，寻找从任一始发结点到目标结点的所有可能的自适应盲寻径优化算法．