Fault-tolerant routing with non-adaptive wormhole algorithms in mesh networks
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We present simple techniques to enhance the e-cube algorithm for fault-tolerant routing in mesh networks. These techniques are based on the concept of fault rings, which are formed using fault free nodes and links around each fault region. We use fault rings to enhance the e-cube to route messages in the presence of rectangular block faults. We show that if fault rings do not overlap with one another-the sets of links in fault rings are pairwise disjoint, then two virtual channels per physical channel are sufficient to make the e-cube tolerant to any number of faulty blocks. For more complex cases such as overlapping fault rings and faults on network boundaries, three or four virtual channels are used. In all cases, the routing guarantees livelock and deadlock free delivery of each and every message injected into the network. Our simulation results for isolated faults indicate that the proposed method provides acceptable performance with as many as 10 percent faulty links.Keywords
This publication has 17 references indexed in Scilit:
- The J-machine Multicomputer: An Architectural EvaluationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- The Touchstone 30 Gigaflop DELTA PrototypePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- A Comparison Of Adaptive Wormhole Routing AlgorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Pipelined circuit-switching: a fault-tolerant variant of wormhole routingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Fault-tolerant wormhole routing in meshesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A new theory of deadlock-free adaptive routing in wormhole networksIEEE Transactions on Parallel and Distributed Systems, 1993
- The turn model for adaptive routingPublished by Association for Computing Machinery (ACM) ,1992
- Routing techniques for massively parallel communicationProceedings of the IEEE, 1991
- Deadlock-Free Message Routing in Multiprocessor Interconnection NetworksIEEE Transactions on Computers, 1987
- Prevention of Deadlocks in Packet-Switched Data Transport SystemsIEEE Transactions on Communications, 1981