Distributed fault-tolerant routing on hypercubes algorithms and performance study
- 9 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 474-481
- https://doi.org/10.1109/spdp.1991.218261
Abstract
Increasing use of hypercube systems in reliability-critical applications has made fault-tolerant communication algorithms for hypercube important. This paper describes four fault-tolerant routing algorithms for hypercubes subject to link failures, namely any/sub -/nd, sidewalk, lookahead and lookside. The principle of sidewalk and lookahead are similar to two existing approaches. Lookside is an improved version of either of them. Sidewalk, lookahead and lookside guarantee successful routing in a d-cube if the number of link failures is less than d. For higher degree of link failures, the authors measure their performance by probability of successful routing and expected routing distance using two fault distribution models, probability fault model and random fault model. Lookside demonstrates better properties than sidewalk and lookahead in that it has the highest successful routing rate with reasonable routing distance.Keywords
This publication has 11 references indexed in Scilit:
- Distributed algorithms for shortest-path, deadlock-free routing and broadcasting in arbitrarily faulty hypercubesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Topological properties of hypercubesIEEE Transactions on Computers, 1988
- Incomplete hypercubesIEEE Transactions on Computers, 1988
- Routing and broadcasting in faulty hypercube computersPublished by Association for Computing Machinery (ACM) ,1988
- Message routing in an injured hypercubePublished by Association for Computing Machinery (ACM) ,1988
- Hypercube message routing in the presence of faultsPublished by Association for Computing Machinery (ACM) ,1988
- Deadlock-Free Message Routing in Multiprocessor Interconnection NetworksIEEE Transactions on Computers, 1987
- Generalized Hypercube and Hyperbus Structures for a Computer NetworkIEEE Transactions on Computers, 1984
- A Scheme for Fast Parallel CommunicationSIAM Journal on Computing, 1982
- A large scale, homogeneous, fully distributed parallel machine, IPublished by Association for Computing Machinery (ACM) ,1977