Adaptive fault-tolerant wormhole routing algorithms for hypercube and mesh interconnection networks

Author

Shih, Jau-Der

Author_Institution

Dept. of Math. & Sci. Educ., Nat. Pingtung Teachers Coll., China

fYear

1997

fDate

1-5 Apr 1997

Firstpage

333

Lastpage

340

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Processing Symposium, 1997. Proceedings., 11th International

Conference_Location

Genva

ISSN

1063-7133

Print_ISBN

0-8186-7793-7

Type

conf

DOI

10.1109/IPPS.1997.580923

Filename

580923