一种二维网格中最小路径区的构建模型

矩形故障块模型可用来解决二维网格中的容错路由问题.本文基于最小路径区(RMP)概念,提出了一种最小路径区的分布式构建模型.该模型首先将带有矩形故障块的网格划分成若干个不同大小的矩形块,通过矩形块的不同组合来构成相应两点之间的最小路径区.最后对该构建模型进行了扩展讨论,指出其在特殊二维网格和容错路由算法中的应用.     

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

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

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

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

反图对角网格中可容错的自适应路由算法

提出一种新型的网络结构－反图对角网格，分析反图对角网格网络的优点，在这种新型网络结构上提出了一种可容错的自适应路由算法，无故障情况下消息通过无死锁确定性路由进行寻径，有故障情况下消息通过自适应路由沿着故障块进行寻径。     

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

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

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

在n维局部扭曲立方体存在节点故障的情况下,基于路由能力的概念提出了一种单播容错路由算法,该算法首先寻找最短路径上满足路由能力值要求的邻接节点,其次寻找非最短路径上满足路由能力值要求的邻接节点。这样求得的容错路径首先是最优路径,其次为次优路径。     

基于故障节点再利用的细粒度NoC容错路由算法

针对传统NoC容错算法中容错粒度过粗造成资源浪费的问题,提出了一种细粒度的自适应容错路由算法,对带有部分故障的节点重新利用。算法将各种故障映射为一种功能故障模型,结合新提出的路由端口优先级策略和嵌入的奇偶转向模型,实现数据包的无死锁容错路由。实验表明,随着负载和故障数目的增加,该算法具有更优越的容错性能,证明了算法的有效性。     

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

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

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

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

面向非规则三维片上网络的自适应可靠路由方法

面向存在永久性链接故障的非规则三维片上网络,提出一种低成本自适应可靠路由方法.首先根据非规则三维片上网络的拓扑结构,优先选择一条汉密尔顿路径进行容错路由,在没有汉密尔顿路径的情况下,则执行生成树容错路由算法绕过故障链接;然后将基于动态规划的端口选择机制拓展到三维空间,结合前述路由算法来避开网络冲突区域,完成将数据包由源路由器节点传输至目的路由器节点的路由过程.实验结果表明,与之前的AFRA方法和基于生成树的可靠路由方法相比,该方法具有较高的通信性能和可靠性,同时所需的网络开销较低.     

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

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

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 theory of deadlock-free adaptive multicast routing in wormholenetworks

A theory for the design of deadlock-free adaptive routing algorithms for wormhole networks, proposed by the author (1991, 1993), supplies sufficient conditions for an adaptive routing algorithm to be deadlock-free, even when there are cyclic dependencies between channels. Also, two design methodologies were proposed. Multicast communication refers to the delivery of the same message from one source node to an arbitrary number of destination nodes. A tree-like routing scheme is not suitable for hardware-supported multicast in wormhole networks because it produces many headers for each message, drastically increasing the probability of a message being blocked. A path-based multicast routing model was proposed by Lin and Ni (1991) for multicomputers with 2D-mesh and hypercube topologies. In this model, messages are not replicated at intermediate nodes. This paper develops the theoretical background for the design of deadlock-free adaptive multicast routing algorithms. This theory is valid for wormhole networks using the path-based routing model. It is also valid when messages with a single destination and multiple destinations are mixed together. The new channel dependencies produced by messages with several destinations are studied. Also, two theorems are proposed, developing conditions to verify that an adaptive multicast routing algorithm is deadlock-free, even when there are cyclic dependencies between channels. As an example, the multicast routing algorithms of Lin and Ni are extended, so that they can take advantage of the alternative paths offered by the network     

Fault-Tolerant Wormhole Routing with 2 Virtual Channels in Meshes

In wormhole meshes, a reliable routing is supposed to be deadlock-free and fault-tolerant. Many routing algorithms are able to tolerate a large number of faults enclosed by rectangular blocks or special convex, none of them, however, is capable of handling two convex fault regions with distance two by using only two virtual networks. In this paper, a fault-tolerant wormhole routing algorithm is presented to tolerate the disjointed convex faulty regions with distance two or no less, which do not contain any nonfaulty nodes and do not prohibit any routing as long as nodes outside faulty regions are connected in the mesh network. The processors＇ overlapping along the boundaries of different fault regions is allowed. The proposed algorithm, which routes the messages by X-Y routing algorithm in fault-free region, can tolerate convex fault-connected regions with only two virtual channels per physical channel, and is deadlock- and livelock-free. The proposed algorithm can be easily extended to adaptive routing.     

A heuristic fault-tolerant routing algorithm in mesh using rectilinear-monotone polygonal fault blocks

A new, rectilinear-monotone polygonally shaped fault block model, called Minimal-Connected-Component (MCC), was proposed in [D. Wang, A rectilinear-monotone polygonal fault block model for fault-tolerant minimal routing in mesh, IEEE Trans. Comput. 52 (3) (2003) 310–320] for minimal adaptive routing in mesh-connected multiprocessor systems. This model refines the widely used rectangular model by including fewer non-faulty nodes in fault blocks. The positions of source/destination nodes relative to faulty nodes are taken into consideration when constructing fault blocks. Adaptive routing algorithm was given in Wang (2003), that constructs a minimal “Manhattan” route avoiding all fault blocks, should such routes exist. However, if there are no minimal routes, we still need to find a route, preferably as short as possible. In this paper, we propose a heuristic algorithm that takes a greedy approach, and can compute a nearly shortest route without much overhead. The significance of this algorithm lies in the fact that routing is a frequently performed task, and messages need to get to their destinations as soon as possible. Therefore one would prefer to have a fast answer about which route to take (and then take it), rather than spend too much time working out an absolutely shortest route.     

An optimal fault-tolerant routing algorithm for weighted bidirectional double-loop networks

Double-loop networks are widely used in computer networks. In this paper, we present an optimal message routing algorithm and an optimal fault-tolerant message routing algorithm for weighted bidirectional double-loop networks. The algorithms presented are novel, and they do not use routing tables. After a precalculation of O(log N) steps to determine network parameters, the algorithms can route messages using constant time at each node along the route. The algorithm presented can route messages in the presence of up to three faulty nodes or links. The fault-tolerant routing algorithm guarantees an optimal route in the presence of one node failure.     

LCFAA:一个低代价的完全自适应路由算法

大规模并行处理机系统（ＭＰＰ）中路由算法对互联网络通信性能和系统性能起着重要作用。自适应路由算法具有灵活性好、网络的通道利用率高和网络容错能力强等优点,但其实现难度较大,因而目前仅在少数ＭＰＰ系统中得以实现。文中在ｍｅｓｈ结构上提出了一个低代价无死锁的安全自适应最短虫孔路由算法ＬＣＦＡＡ,该算法所需虚通道数少,具有代价低、自适应性强的特点。文中证明了算法的无死锁、无活锁性和完全自适应性,并模拟验证     

A simple fault-tolerant adaptive and minimal routing approach in 3-D meshes

In this paper we propose a sufficient codition for minimal routing in 3-dimensional (3-D) meshes with faulty nodes,It is based on an early work of the author on minial routing in 2-dimensional(2-D) meshes,Unlike many traditional models that assume all the nodes know global fault distribution or just adjacent fault information,our approach is based on the concept of limited global fault information,First,we propose a fault model called faulty cube in which all faulty nodes in the system are contained in a set of faulty cubes.Fault information is then distributed to limited number of nodes while it is still sufficeint to support minimal routing.The limited fault information collcted at each node is represented by a vector caaled extended safety level.The extended safety level associated with a node can be used to determine the existence of a minimal path from this node to a given destination .Specifically,we study the existence of minimal paths at a given source node,limited distribution of fault information,minimal routing,and deadlock-free and livelock-free routing.our results show that any minimal routing that is partially adaptive can be applied in our model as long as the dstination node meets a certain conditon.We also propose a dynamic planar-adaptive routing scheme that offers better fault tolerance and adaptivity than the planar-adaptive routing scheme in 3-D meshes.Our approach is the first attempt to address adaptive and minimal routing is 3-D meshes with faulty nodes using limited fault information.     

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