Title :
Adaptive fault-tolerant wormhole routing algorithms for hypercube and mesh interconnection networks
Author_Institution :
Dept. of Math. & Sci. Educ., Nat. Pingtung Teachers Coll., China
Abstract :
The author presents adaptive fault-tolerant deadlock-free routing algorithms for hypercubes and meshes by using only 3 virtual channels and 2 virtual channels respectively. Based on the concept of unsafe nodes, the author designs a routing algorithm for hypercubes that can tolerate at least n-1 node faults and can route a message via a path of length no more than the Hamming distance between the source and destination plus four. The author also develops a routing algorithm for meshes that can tolerate any block faults, as long as the distance between any two nodes in different faulty blocks is at least 2 in each dimension
Keywords :
distributed algorithms; fault tolerant computing; hypercube networks; network routing; Hamming distance; adaptive fault-tolerant deadlock-free wormhole routing algorithms; block fault tolerance; destination; hypercube interconnection networks; mesh interconnection networks; message routing; node faults; source; unsafe nodes; virtual channels; Algorithm design and analysis; Educational institutions; Fault tolerance; Hamming distance; Hypercubes; Multiprocessor interconnection networks; Pipelines; Routing; Shape; System recovery;
Conference_Titel :
Parallel Processing Symposium, 1997. Proceedings., 11th International
Conference_Location :
Genva
Print_ISBN :
0-8186-7793-7
DOI :
10.1109/IPPS.1997.580923
