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     

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记录了超立方体系统全部最优通路和次最优通路的信息,在具有大量故障的情况下,它不会遗漏任何一条最优通路和次最优通路信息,从而实现了高效的容错路由.在这一点上,它优于其他算法.     

Adaptive Fault-Tolerant Multicast in Hypercube Multicomputers

Fault-tolerant message routing mechanism is a key to the performance of reliable multicomputers. Multicast refers to the delivery of the same message from a source node to an arbitrary number of destination nodes. This paper presents two types of partially adaptive fault tolerant multicast algorithms. The Type A algorithm can deliver messages to all destinations through shortest paths if each fault-free node has at most one faulty neighbor. The Type B algorithm can deliver messages to all destinations if the total number of faulty links and faulty nodes is less than the dimension of the hypercube. The proposed algorithms have the following important features: they are distributed, they only require local information to determine the paths, and they need very little additional message overhead. The performance of the algorithms, measured by the traffic created by the communication, is very close to that in fault-free hypercubes.     

Torus网络中基于标志位的容错路由

针对Torus结构的多处理机系统中容错路由的问题,提出标志位概念,给出一个基于标志位的容错路由算法。存储于Torus网络中各节点的标志位记录系统中的故障信息,用于判定消息的源节点和目的节点之间是否存在最优通路。标志位的赋值可以通过与邻节点间的信息交换完成。     

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.     

A dynamic fault-tolerant message routing algorithm for double-loop networks

Message routing is a fundamental function of a network, and fault-tolerance is an important tool to ensure the quality of service of a network. Assume that the network contains at most one faulty element and the algorithm does not know the faulty element in advance. We present an optimal fault-tolerant message routing algorithm for double-loop networks. We show that sending at most two messages with different routing strategies can ensure that one of the messages will be sent through a shortest path that avoids the faulty element. At each vertex, for any destination, the algorithm needs only constant time and space to determine the next vertex to which the message is to be sent.     

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

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

卫星网络基于ATM鲁棒路由算法中的链路诊断

针对使用星际链路ISL（intersatellite links）的LEO卫星系统,提出一种基于ATM的鲁棒路由算法。只要源卫星与目的卫星之间存在一条通路,二者便可以实现通信。本文关注的是路由算法中的链路诊断部分。源卫星首先利用收集的不可达信息构建离散时间动态虚拓扑图（DT-DVTG）（discrete-time dynamic virtual topology graph）,然后通过概率的方法诊断出最可能出现故障的链路,再经过快速的测试可精确定位故障链路。由于链路诊断过程支持动态路由,使鲁棒路由算法在保持原有动态路由算法各项性能指标的基础上进一步提高了鲁棒性。     

A fault tolerant routing algorithm based on cube algebra for hypercube systems

We propose an approach to determine the shortest path between the source and the destination nodes in a faulty or a non-faulty hypercube. The number of faulty nodes and links may be rather large and if any path between the nodes exists, the developed algorithm determines it. To construct this algorithm, some properties of the cube algebra are considered and some transformations based on this algebra are developed.     

A fault-tolerant routing scheme in dynamic networks

In dynamic networks,links and nodes will be deleted or added regularly.It is very essential for the routing scheme to have the ability of fault-tolerance.The method to achieve such a goal is to generate ore than one path for a given set of source and destination.In this paper,the idea of inderval routing is used to construct a new scheme(Multi-Node Label Interval Routing Scheme,or MNILIR scheme)to realizee fault-tolerance.Interval routing is a space-efficinet routing method for netwroks ,but the method is static and determinative,and it cannot realize faulttoloerance.In MNLIR scheme some nodes will have more than one label,thus some parirs of destination and source will have more than one path;the pairs of nodes, which have inheritance relation,will have the shortest path.Using this character,MNLIR scheme has better overall routing performance than the former interval routing scheme,which can be proven by simulations.The common problem concerning the insertion and deletion of nodes and links is considered in this paper.So if the networks have some changes in topology,MNLIR scheme may find alternative path for certain paris of nodes.In this way,fault-tolerance can be realized with only a little space added to store the multi-node labels.     

Neighbor supported reliable multipath multicast routing in MANETs

The limited battery power, unpredictable mobility and large variation of received signal strength in nodes of Mobile Ad Hoc Networks (MANETs) create link and node vulnerability and instability. Multicast routing in MANETs for group communication requires the establishment of reliable links between neighboring nodes called as reliability pair beginning from the source and extending such reliability pairs enroute to the destination. We propose a scheme for Multipath Multicast Routing in MANETs using reliable Neighbor Selection (MMRNS) mechanism. A mesh of multipath routes are established from source to multicast destinations using neighbors that have high reliability pair factor. MMRNS operates in the following phases. (1) Computation of reliability pair factor based on node power level, received differential signal strength between the nodes and mobility. (2) Pruning neighbor nodes that have reliability pair factor smaller than a threshold. (3) Discovery of multipath multicast mesh routes with the help of request and reply packets. (4) Multipath priority assignment based on minimum value of reliability pair factor of a path and information transfer from source to the multicast destinations and (5) route maintenance against link/node failures. The scheme is simulated to evaluate the performance parameters like packet delivery ratio, memory overhead, message overhead, control overhead and packet delays in comparison to the mesh based multicast routing protocols such as On-demand Multicast Routing Protocol (ODMRP) and Enhanced ODMRP (EODMRP). MMRNS performs better than ODMRP and EODMRP as observed from the simulation results.     

Routing in modular fault-tolerant multiprocessor systems

In this paper, we consider a class of modular multiprocessor architectures in which spares are added to each module to cover for faulty nodes within that module, thus forming a fault-tolerant basic block (FTBB). In contrast to reconfiguration techniques that preserve the physical adjacency between active nodes in the system, our goal is to preserve the logical adjacency between active nodes by means of a routing algorithm which delivers messages successfully to their destinations. We introduce two-phase routing strategies that route messages first to their destination FTBB, and then to the destination nodes within the destination FTBB. Such a strategy may be applied to a variety of architectures including binary hypercubes and three-dimensional tori. In the presence of f faults in hypercubes and tori, we show that the worst case length of the message route is min {σ+f, (K+1)σ}+c where σ is the shortest path in the absence of faults, K is the number of spare nodes in an FTBB, and c is a small constant. The average routing overhead is much lower than the worst case overhead     

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.     

Addressing and routing in hexagonal networks with applications for tracking mobile users and connection rerouting in cellular networks

Nodes in a hexagonal network are placed at the vertices of a regular triangular tessellation, so that each node has up to six neighbors. The network is proposed as an alternative interconnection network to a mesh connected computer (with nodes serving as processors) and is used also to model cellular networks where nodes are the base stations. In this paper, we propose a suitable addressing scheme for nodes (with two variants), derive a formula for distance between nodes, and present a very simple and elegant routing algorithm. This addressing scheme and corresponding routing algorithm for hexagonal interconnection are considerably simpler than previously proposed solutions. We then apply the addressing scheme for solving two problems in cellular networks. With the new scheme, the distance between the new and old cell to which a mobile phone user is connected can be easily determined and coded with three integers, one of them being zero. Further, in order to minimize the wireless cost of tracking mobile users, we propose hexagonal cell identification codes containing three, four, or six bits, respectively, to implement a distance based tracking strategy. These schemes do not have errors in determining cell distance in existing hexagonal based cellular networks. Another application is for connection rerouting in cellular networks during a path extension process.     

Backup path set selection in ad hoc wireless network using link expiration time

Topological changes in mobile ad hoc networks frequently render routing paths unusable. Such recurrent path failures have detrimental effects on quality of service. A suitable technique for eliminating this problem is to use multiple backup paths between the source and the destination in the network. Most of the proposed on-demand routing protocols however, build and rely on single route for each data session. Whenever there is a link disconnection on the active route, the routing protocol must perform a path recovery process. This paper proposes an effective and efficient protocol for backup and disjoint path set in an ad hoc wireless network. This protocol converges into a highly reliable path set very fast with no message exchange overhead. The paths selection according to this algorithm is beneficial for mobile ad hoc networks, since it produces a set of backup paths with much higher reliability. Simulations are conducted to evaluate the performance of our algorithm in terms of route numbers in the path set and its reliability. In order to acquire link reliability estimates, we use link expiration time (LET) between each two nodes.In another experiment, we save the LET of entire links in the ad hoc network during a specific time period, then use them as a data base for predicting the probability of proper operation of links.Links reliability obtains from LET. Prediction is done by using a multi-layer perceptron (MLP) network which is trained with error back-propagation error algorithm. Experimental results show that the MLP net can be a good choice to predict the reliability of the links between the mobile nodes with more accuracy.     

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

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

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.     

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.     

Effective fault detection and routing scheme for wireless sensor networks

In a wireless sensor network (WSN), random occurrences of faulty nodes degrade the quality of service of the network. In this paper, we propose an efficient fault detection and routing (EFDR) scheme to manage a large size WSN. The faulty nodes are detected by neighbour node’s temporal and spatial correlation of sensing information and heart beat message passed by the cluster head. In EFDR scheme, three linear cellular automata (CA) are used to manage transmitter circuit/ battery condition/microcontroller fault, receiver circuit fault and sensor circuit fault representation. On the other hand, L-system rules based data routing scheme is proposed to determine optimal routing path between cluster head and base station. The proposed EFDR technique is capable of detecting and managing the faulty nodes in an efficient manner. The simulation results show 86% improvement in the rate of energy loss compared to an existing algorithm.