Fault-tolerant wormhole routing for hypercube networks

We present an adaptive fault-tolerant wormhole routing algorithm for hypercubes by using 3 virtual networks. The routing algorithm can tolerate at least n−1 faulty nodes and can route a message via a path of length no more than the shortest path plus four. Previous algorithms which achieve the same fault tolerant ability need 5 virtual networks. Simulation results are also given in this paper.     

Adaptive and deadlock-free routing for irregular faulty patterns inmesh multicomputer

Message routing achieves the internode communication in parallel computers. A reliable routing is supposed to be deadlock-free and fault-tolerant. While many routing algorithms are able to tolerate a large number of faults enclosed by rectangular faulty blocks, there is no existing algorithm that is capable of handling irregular faulty patterns for wormhole networks. In this paper, a two-staged adaptive and deadlock-free routing algorithm called “Routing for Irregular Faulty Patterns” (RIFP) is proposed. It can tolerate irregular faulty patterns by transmitting messages from sources or to destinations within faulty blocks via multiple “intermediate nodes.” A method employed by RIFP is first introduced to generate intermediate nodes using the local failure information. By its aid, two communicating nodes can always exchange their data or intermediate results if there is at least one path between them. RIFP needs two virtual channels per physical link in meshes     

基于局部故障块三维mesh/torus网的容错路由

当系统包含很少的故障点时．mesh/torus网整个系统就有可能是不可靠的．该文采用扩展的局部可靠性信息来指导三维mesh／torus网的容错路由．扩展的局部可靠性信息在每个平面内部对无故障节点分类，所以系统中的故障块也是在不同的平面上构成的，而不是基于整个系统．很多基于整个系统不可靠的节点在二维的平面中都会变成可靠的节点．不管是在可靠的系统内，甚或不可靠的系统内，扩展的局部可靠性信息都能有效地指导容错路由．不同于以往的方法，作者的方法不会将任何无故障节点设置为无效节点．所有的故障块都是在平面内构成的，而不是基于整个系统；在一个平面内．任何包含在故障块里的无故障节点仍然可作为出发点或者目标点，这样将大大提高系统的计算能力和性能．模拟结果表明该文方法大大优于已有的方法．     

Mesh网络耐故障虫孔路由

耐故障是互连网络设计中的一个重要问题。本文提出了一种新的耐故障路由算法,并将其应用于使用虫孔交换技术的Mesh网络。由于使用了较低的路由限制,这一算法具有很强的自适应性,可以在各种不同故障域的Mesh网络中保持路由的连通性和无死锁性;由于使用了最小限度的虚拟通道,这一算法所需的缓冲器资源很少,非常适宜构建低成本的耐故障互连网络;由于根据本地故障信息进行绕行故障节点的决策,这一算法的路由决策速度较快并且易于在互连网络中实现。最后网络仿真试验显示,这一算法具有良好的平滑降级使用的性能。     

Routing in wormhole-switched clustered networks with applicationsto fault tolerance

This paper presents a novel technique for routing in wormhole-switched multiprocessor interconnection networks with clustered configuration. The network model used here consists of a set of clusters interfaced through a common central network. We assume that the central network and the clusters use independent algorithms to route messages between their internal nodes. A technique for deriving a global routing algorithm based on the local algorithms is presented, which allows the transfer of messages between any pair of nodes in the network. This proposed method is shown to be deadlock-free with two virtual channels. The clustered network model and the proposed routing technique can be used to enhance the fault tolerance capability of existing routing algorithms. In particular, we describe fault-tolerant routing methods for meshes, which can tolerate any arbitrary fault distribution without disabling connected healthy nodes     

Fault-tolerant routing methodology for hypercube and cube-connected cycles interconnection networks

This paper presents a fault-tolerant routing methodology for both injured hypercube and cube-connected cycles interconnection topologies. The proposed routing methodology efficiently tolerates any pattern of faulty regions with any number of faulty nodes in the network which is based on the best-first search and backtracking strategy. Deadlock freedom of the proposed routing methodology is obtained by only one virtual channel per physical channel. In order to evaluate the proposed routing methodology, a 7-dimensional hypercube network is simulated in various conditions, i.e., different traffic rates, different number of faulty nodes and different message lengths. Simulation results confirm that the proposed routing methodology in comparison with the previous methods provides acceptable performance while it significantly increases the reliability of the network. It also guarantees delivery of messages between any pair of source and destination while the network is connected.     

Fault-Tolerant Routing Algorithm in Meshes with Solid Faults

A fault-tolerant routing method that can tolerate solid faults using only two virtual channels is presented. The proposed routing algorithm, called FT-Ecube, not only uses a fewer number of virtual channels but also tolerates f-chains in the meshes. Furthermore, the proposed scheme misroutes messages both clockwise and counter clockwise directions to reduce channel contention on f-rings. It is shown that the proposed algorithm is deadlock-free and livelock-free in meshes when it has nonoverlapping multiple f-regions. Further, we conducted flit-level simulations to evaluate the performance of the proposed routing algorithm. As our simulation results show, FT-Ecube tolerates multiple faulty blocks using only two virtual channels per physical channel, and has good performance in terms of average latency. This work is supported by the NSF grant MIP-9705738     

Fault-tolerant wormhole routing in mesh with overlapped solid fault regions

A fault-tolerant wormhole routing algorithm on mesh-connected processors is proposed. The proposed algorithm is based on the solid fault model and allows the fault polygons to be overlapped. The algorithm utilizes the position of fault region relative to the current channel to route a message around overlapped fault polygons. A node deactivating algorithm to convert a non-solid fault region into a solid fault region is also proposed. The proposed routing algorithm uses four virtual channels and is deadlock- and livelock-free.     

片上网络中面向链路故障的容错路由方法研究

片上网络在工业和学术领域越来越受欢迎,但是晶体管显著缩小后可靠性不足问题给片上网络带来严峻挑战。传统的容错路由算法通过使报文绕过故障区域,因此可以克服链路或路由器故障。但是这些方法会增加报文延时,并在故障区域周围产生拥塞。本文利用两个虚拟信道提出一种新的容错路由方法,它通过确定每个虚拟信道哪些转向被允许和禁止,使得一个虚拟信道中被禁止的转向在另一信道被允许。当发生链路故障时,该方法基于一种新的故障信息传播机制使报文在最短路径上传输。另外,通过充分利用网络中的所有被允许转向对本文方法进行扩展,以支持多链路故障。最后的仿真实验也验证了本文方法的有效性。     

基于裂痕故障块的自适应容错路由表算法

基于裂痕故障块的二维网格自适应容错路由算法是一种有效的容错算法,不仅能够解决活锁问题,而且克服了传统故障块模型中状态良好的节点不能参与路由的缺陷,但同时具有明显的缺点：每次路由到以故障块边界节点为根节点的内部树时,都需要遍历此内部树,因此算法的路由长度并不是最短的。针对上述问题,提出基于裂痕故障块的自适应容错路由表算法,其中路由表由裂痕故障块内部树上的节点创建,通过路由表上保留的有用消息决定是否遍历内部树。实验结果证明,随着网格规模的扩大,该算法最大可减少70％的平均路由长度,并且其实现简单,可以有效地延长网络寿命。     

无向双环网络的容错路由研究

在节点出现故障的情况下,如何保证网络节点之间的路由是一个重要的问题。将无向双环网络的节点按照最短路径访问方式映射到直角坐标系形成最优路由构图[CG(N;±r,±s)];基于该构图根据源节点和目的节点是否位于坐标轴上以及它们周围的故障节点数,提出故障节点封闭区和逃逸区的概念;存在故障逃逸区的情况下,源、目的节点之间仍然可以进行最优路由,针对出现故障节点封闭区而无法进行最优路由的情况下,增加等价节点形成扩展路由构图[ECG(N;±r,±s)],从而寻找容错路由;给出最优路由构图、扩展路由构图和容错路由的算法,并编程仿真了这些算法。     

Torus网络自适应容错路由算法

在应用于大规模并行计算机的互连网络的设计中,容错问题是其中的一个关键问题和难点问题。提出了一种基于Torus虫孔交换网络的容错路由算法,这一算法使用了矩形故障模型,无论故障区域大小多少和如何分布,算法始终是无死锁的,而且具有足够的自适应性,只要故障节点没有断开网络的连接,算法就能够通过选路使消息绕过故障区域,保持路由的连通性。同时,算法仅需要使用3个额外的虚拟通道。最后算法在不同故障率的Torus网络中进行了仿真实验,结果显示这一算法具有良好的平滑降级使用的特性。     

An Adaptive Routing Algorithm for WK-Recursive Topologies

This paper presents an easy and straightforward routing algorithm for WK-recursive topologies. The algorithm, based on adaptive routing, takes advantage of the geometric properties of such topologies. Once a source node S and destination node D have been determined for a message communication, they characterize, at some level l, two virtual nodes and that respectively contain S but not D and D but not S. Such virtual nodes characterize other (where is the node degree for a fixed topology) virtual nodes of the same level that contain neither S nor D. Consequently, it is possible to locate triangles whose vertices are these virtual nodes with property to share the same path, called the self-routing path, directly connecting to . When the self-routing path is unavailable to transmit a message from S to D because of deadlock, fault, and congestion conditions, the routing strategy can follow what we call the triangle rule to deliver it. The proposed communication scheme has the advantage that 1) it is the same for all three conditions; 2) each node of a WK-recursive network, to transmit messages, does not require any information about their presence or location. Furthermore, this routing algorithm is able to tolerate up to faulty links. Received: July 19, 1998; revised May 17, 1999     

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

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

Pseudo-cycle-based multicast routing in wormhole-routed networks

This paper addresses the problem of fault-tolerant multicast routing in wormholerouted multicomputers.A new pseudo-cycle-based routing method is presented for constructing deadlock-free multicast routing algorithms.With at most two virtual channels this technique can be applied to any connected networks with arbitrary topologies.Simulation results show that this technique results in negligible performance degradation even in the presence of a large number of faulty nodes.     

Fault-tolerant adaptive and minimal routing in mesh-connectedmulticomputers using extended safety levels

The minimal routing problem in mesh-connected multicomputers with faulty blocks is studied. Two-dimensional meshes are used to illustrate the approach. A sufficient condition for minimal routing in 2D meshes with faulty blocks is proposed. Unlike many traditional models that assume all the nodes know global fault distribution, our approach is based on the concept of an extended safety level, which is a special form of limited fault information. The extended safety level information is captured by a vector associated with each node. When the safety level of a node reaches a certain level (or meets certain conditions), a minimal path exists from this node to any nonfaulty nodes in 2D meshes. Specifically, we study the existence of minimal paths at a given source node, limited distribution of fault information, and minimal routing itself. We propose three fault-tolerant minimal routing algorithms which are adaptive to allow all messages to use any minimal path. We also provide some general ideas to extend our approaches to other low-dimensional mesh-connected multicomputers such as 2D tori and 3D meshes. Our approach is the first attempt to address adaptive and minimal routing in 2D meshes with faulty blocks using limited fault information     

A Necessary and Sufficient Condition for Deadlock-Free Wormhole Routing

An important open problem in wormhole routing has been to find a necessary and sufficient condition for deadlock-free adaptive routing. Recently, Duato has solved this problem for a restricted class of adaptive routing algorithms. In this paper, a necessary and sufficient condition is proposed that can be used for any adaptive or nonadaptive routing algorithm for wormhole routing, as long as only local information is required for routing. The underlying proof technique introduces a new type of dependency graph, thechannel waiting graph, which omits most channel dependencies that cannot be used to create a deadlock configuration. The necessary and sufficient condition can be applied in a straightforward manner to most routing algorithms. This is illustrated by proving deadlock freedom for a partially adaptive nonminimal mesh routing algorithm that does not require virtual channels and a fully adaptive minimal hypercube routing algorithm with two virtual channels per physical channel. Both routing algorithms are more adaptive than any previously proposed routing algorithm with similar virtual channel requirements.     

虚网叠加构造自适应路由算法的有效框架

大规模并行处理机系统中路由算法对互联网络通信性能和系统性起着重要作用。     

基于扩展安全级的Torus网络容错路由算法研究

在存在故障结点的网络中如何设计最小容错路由是网络容错研究中的一个热点问题。以存在矩形故障块的二维Torus网络为例,将扩展安全级运用到Torus中,对于网络中任意一对结点,给出存在最小路径的充要条件;并且结合扩展安全级的概念,给出建立最小通路区的方法,并用实验验证了方法的可行性。研究为存在故障结点的Torus网络寻找最小容错路径提供了理论依据。     

A fault-tolerant wormhole routing scheme for torus networks with nonconvex faults

In this paper, we present a fault-tolerant routing algorithm for torus networks by using only 4 virtual channels. The proposed algorithm is based on the solid fault model, which includes rectangular faults and many practical nonconvex faults. Previous works need at least 6 virtual channels to achieve the same fault-tolerant ability.