Fault-tolerant wormhole routing algorithms in meshes in the presence of concave faults

Seungjin Park, Jong Hoon Youn, Bella Bose

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


A fault ring is a connection of only nonfaulty adjacent nodes and links such that the interior of the ring contains only faulty components. This paper proposes two wormhole routing algorithms that deal with more relaxed shapes of fault rings than previously known algorithms in the mesh networks. As a result, the number of components to be made disabled would be reduced considerably in some cases. First algorithm, called F4, uses four virtual channels and allows all four sides of fault rings to contain concave shapes. Second algorithm, F3, permits up to three sides to contain concave shapes using only three virtual channels. Both F3 and F4 are free of deadlock and livelock and guarantee the delivery of messages between any pair of nonfaulty and connected nodes in the network.

Original languageEnglish (US)
Pages (from-to)633-638
Number of pages6
JournalProceedings of the International Parallel Processing Symposium, IPPS
StatePublished - 2000
Externally publishedYes

ASJC Scopus subject areas

  • Hardware and Architecture


Dive into the research topics of 'Fault-tolerant wormhole routing algorithms in meshes in the presence of concave faults'. Together they form a unique fingerprint.

Cite this