The Flexible Hypercube: A New Fault-Tolerant Architecture for Parallel Computing

This paper presents the new Flexible Hypercube architecture. The Flexible Hypercube is a fault-tolerant network topology that can be constructed for an arbitrary number of nodes and is incrementally expandable. This topology maintains the strong features of the Hypercube while overcoming deficiencies in expandability. It is shown to have strong node connectivity, a small diameter, and to be tolerant of faults. The Flexible Hypercube is a suitable architecture for the design of both tightly coupled parallel systems and distributed systems. Efficient fault-free and fault-tolerant algorithms for message routing and broadcasting are presented for the architecture. The fault-free algorithm guarantees successful routing inO(logN) time, whereNis the number of nodes in the system, and the fault-tolerant algorithm guarantees routing to functioning nodes if a route exists. The fault-free and fault-tolerant broadcasting algorithms have time complexityO(logN), and the fault-tolerant algorithm guarantees success if no two faulty nodes are adjacent and no functioning node is adjacent to two faults.     

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     

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 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.     

Efficient Exploration of Faulty Trees

We consider the problem of the exploration of trees, some of whose edges are faulty. A robot, situated in a starting node and unaware of the location of faults, has to explore the connected fault-free component of this node by visiting all its nodes. The cost of the exploration is the number of edge traversals. For a given tree and given starting node, the overhead of an exploration algorithm is the worst-case ratio (taken over all fault configurations) of its cost to the cost of an optimal algorithm which knows where faults are situated. An algorithm, for a given tree and given starting node, is called perfectly competitive if its overhead is the smallest among all exploration algorithms not knowing the location of faults. We design a perfectly competitive exploration algorithm for any line, and an exploration algorithm for any tree, whose overhead is at most 9/8 larger than that of a perfectly competitive algorithm. Both our algorithms are fairly natural and the total time of local computations used during exploration is linear in the size of the explored tree. Our main contribution is the analysis of the performance of these algorithms, showing that natural exploration strategies perform well in faulty trees.     

Unicast-based multicast communication in wormhole-routed networks

Multicast communication, in which the same message is delivered from a source node to an arbitrary number of destination nodes, is being increasingly demanded in parallel computing. System supported multicast services can potentially offer improved performance, increased functionality, and simplified programming, and may in turn be used to support various higher-level operations for data movement and global process control. This paper presents efficient algorithms to implement multicast communication in wormhole-routed direct networks, in the absence of hardware multicast support, by exploiting the properties of the switching technology. Minimum-time multicast algorithms are presented for n-dimensional meshes and hypercubes that use deterministic, dimension-ordered routing of unicast messages. Both algorithms can deliver a multicast message to m-1 destinations in [log ₂ m] message passing steps, while avoiding contention among the constituent unicast messages. Performance results of implementations on a 64-node nCUBE-2 hypercube and a 168-node Symult 2010 2-D mesh are given     

Optimizing responses to broadcast messages in radio networks

Algorithms to optimize the performance of response traffic for broadcast messages in a packet-switched radio network are studied. The situation considered here involves a source node sending a broadcast message to all destinations and collecting positive response packets from these destinations in a fully connected packet radio network. The exact value of the number of destination nodes is unknown. A contention-based two-level protocol is described. Based on the protocol, an optimization problem is formulated in order to minimize the time for the source node to receive all the responses. Several algorithms are presented and numerical results of the corresponding optimization problems are obtained. These optimization problems are treated by the methods of dynamic programming. An extension of the basic scheme—multicast instead of full broadcast message—is also studied.     

Fault-tolerant routing in mesh architectures

It is important for a distributed computing system to be able to route messages around whatever faulty links or nodes may be present. We present a fault-tolerant routing algorithm that assures the delivery of every message as long as there is a path between its source and destination. The algorithm works on many common mesh architectures such as the torus and hexagonal mesh. The proposed scheme can also detect the nonexistence of a path between a pair of nodes in a finite amount of time. Moreover, the scheme requires each node in the system to know only the state (faulty or not) of each of its own links. The performance of the routing scheme is simulated for both square and hexagonal meshes while varying the physical distribution of faulty components. It is shown that a shortest path between the source and destination of each message is taken with a high probability, and, if a path exists, it is usually found very quickly     

VANET环境下基于历史行为的消息路由方案

通过分析车用自组织网络(VANET)在道路交通领域中的应用现状,根据VANET的特点及其消息传输过程中面临的挑战,针对以往算法较难准确进行空间建模并较少考虑社会行为的规律性特征的问题,提出了一种基于车辆历史行为统计的消息路由方案——HBSR,具体分为计算车辆之间的连通性的节点连通算法,计算源节点和目的节点间可达时段数的拓扑重叠算法,选择消息转发路径的路径选择算法和丢包策略四部分。通过在ONE仿真平台上将其和一些典型的路由算法进行比较,实验证明HBSR方案能够更有效地在VANET中找到消息转发路径,在送达时延明显降低的同时交付率有显著提高,并且表现相对稳定。     

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     

Optimal multicast communication in wormhole-routed torus networks

This paper presents efficient algorithms that implement one-to-many, or multicast, communication in wormhole-routed torus networks. By exploiting the properties of the switching technology and the use of virtual channels, a minimum-time multicast algorithm is presented for n-dimensional torus networks that use deterministic, dimension-ordered routing of unicast messages. The algorithm can deliver a multicast message to m-1 destinations in [log₂ m] message-passing steps, while avoiding contention among the constituent unicast messages. Performance results of a simulation study on torus networks with up to 4096 nodes are also given     

One-to-one communication in twisted cubes under restricted connectivity

The dimensions of twisted cubes are only limited to odd integers. In this paper, we first extend the dimensions of twisted cubes to all positive integers. Then, we introduce the concept of the restricted faulty set into twisted cubes. We further prove that under the condition that each node of the n-dimensional twisted cube TQ_n has at least one fault-free neighbor, its restricted connectivity is 2n − 2, which is almost twice as that of TQ_n under the condition of arbitrary faulty nodes, the same as that of the n-dimensional hypercube. Moreover, we provide an O(NlogN) fault-free unicast algorithm and simulations result of the expected length of the fault-free path obtained by our algorithm, where N denotes the node number of TQ_n. Finally, we propose a polynomial algorithm to check whether the faulty node set satisfies the condition that each node of the n-dimensional twisted cube TQ_n has at least one fault-free neighbor.     

Visiting Byzantine Agreement underlying Ad Hoc environment

The Mobile Ad Hoc Network (MANET) has become more popular because the MANET is a self-organizing, self-configuring, and an instantly deployable multi-hop wireless network that responds to application needs without any fixed infrastructure. Moreover, the MANET is fault-tolerant and reliable. A mechanism is needed in the MANET that allows a set of nodes to agree on a common value. The distributed Byzantine Agreement (BA) problem is one of the most important issues in designing a fault-tolerant system. In many cases, reaching a common agreement among fault-free nodes in coping with the influence from faulty components is crucial in a fault-tolerant system. When a common agreement is achieved, all fault-free nodes in the system can produce stable results without any influence from the faulty components. In this study, the BA problem is visited in a MANET, in which the components are subject to a malicious fault. The proposed protocol can tolerate the maximum number of allowable faulty nodes using a minimum number of message exchange rounds. Each fault-free node can reach a common agreement value for the BA problem in a MANET. The text was submitted by the authors in English.     

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     

Fast and proximity-aware multi-source overlay multicast under heterogeneous environment

Overlay multicast has been considered as one of the most important developments for the next generation Internet infrastructure. In this paper, we consider overlay multicast in the scenarios where any participant node is a potential data source. Existing multicast algorithms for single-source always require a long time to deliver messages or have high maintenance overhead when multiple data sources are allowed. There are other algorithms that are designed for multi-source scenarios. But they consume too much network resources and have a long convergence time because of proximity ignorance. To address the issues, we present FPCast, which leverages node heterogeneity and proximity information at the same time. Physically close nodes are grouped into clusters and each cluster selects a powerful, stable node as its rendezvous point. The rendezvous nodes form a DHT-based structure. Data messages are replicated and forwarded along implicit, source specific, and heterogeneity-aware multicast trees. We further reduce the delivery delay by introducing probabilistic forwarding scheme. We show the average delivery path length converges to O(logn) automatically (n is the number of nodes in the overlay). The simulation results demonstrate the superiority of our algorithm in terms of message delivery time and network resource consumption, in comparison with the previous randomized algorithms. The algorithm is also resilient to node failures.     

Optimizing responses to broadcast messages in radio networks

Algorithms to optimize the performance of response traffic for broadcast messages in a packet-switched radio network are studied. The situation considered here involves a source node sending a broadcast message to all destinations and collecting positive response packets from these destinations in a fully connected packet radio network. The exact value of the number of destination nodes is unknown. A contention-based two-level protocol is described. Based on the protocol, an optimization problem is formulated in order to minimize the time for the source node to receive all the responses. Several algorithms are presented and numerical results of the corresponding optimization problems are obtained. These optimization problems are treated by the methods of dynamic programming. An extension of the basic scheme—multicast instead of full broadcast message—is also studied.This work was supported by the US Army Research Office under Contract No. DAAG29-84-K-0084.     

Deadlock-free multicast wormhole routing in 2-D mesh multicomputers

Multicast communication services, in which the same message is delivered from a source node to an arbitrary number of destination nodes, are being provided in new-generation multicomputers. Broadcast is a special case of multicast in which a message is delivered to all nodes in the network. The nCUBE-2, a wormhole-routed hypercube multicomputer, provides hardware support for broadcast and a restricted form of multicast in which the destinations form a subcube. However, the broadcast routing algorithm adopted in the nCUBE-2 is not deadlock-free. In this paper, four multicast wormhole routing strategies for 2-D mesh multicomputers are proposed and studied. All of the algorithms are shown to be deadlock-free. These are the first deadlock-free multicast wormhole routing algorithms ever proposed. A simulation study has been conducted that compares the performance of these multicast algorithms under dynamic network traffic conditions in a 2-D mesh. The results indicate that a dual-path routing algorithm offers performance advantages over tree-based, multipath, and fixed-path algorithms     

Fault-tolerant routing over shortest node-disjoint paths in hypercubes

This paper presented a routing algorithm that finds n disjoint shortest paths from the source node s to target node d in the n-dimensional hypercube. Fault-tolerant routing over all shortest node-disjoint paths has been investigated to overcome the failure encountered during routing in hypercube networks. In this paper, we proposed an efficient approach to provide fault-tolerant routing which has been investigated on hypercube networks. The proposed approach is based on all shortest node-disjoint paths concept in order to find a fault-free shortest path among several paths provided. The proposed algorithm is a simple uniform distributed algorithm that can tolerate a large number of process failures, while delivering all n messages over optimal-length disjoint paths. However, no distributed algorithm uses acknowledgement messages (acks) for fault tolerance. So, for dealing the faults, acknowledgement messages (acks) are included in the proposed algorithm for routing messages over node-disjoint paths in a hypercube network.     

A fast pessimistic diagnosis algorithm for generalized hypercube multicomputer systems

The reliability of processors is an important issue for designing a massively parallel processing system for which fault-tolerant computing is crucial. In order to achieve high system reliability and availability, a faulty processor (node) when found should be replaced by a fault-free processor. Within a multiprocessor system, the technique of identifying faulty nodes by constructing tests on the nodes and interpreting the test outcomes is known as system-level diagnosis. The topological structure of a multicomputer system can be modeled by a graph of which the vertices and edges correspond to nodes and links of the system, respectively. This work presents a system-level diagnosis algorithm for a generalized hypercube which is an attractive variance of a hypercube. The proposed algorithm is based on the PMC model and can isolate all faulty nodes to within a set which contains at most one fault-free node. If the total number of nodes to be diagnosed in a generalized hypercube is N, the proposed algorithm can run in O(Nlog?N) time, and being superior to Yang??s algorithm proposed in 2004, it can diagnose not only a hypercube but also a generalized hypercube.     

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.