Distributed fault-tolerant routing in kautz networks

Wei Kuo Chiang, Rong-Jaye Chen*

*Corresponding author for this work

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

For a Kautz network with faulty components we propose a distributed fault-tolerant routing scheme, called DFTR, in which each nonfaulty node knows no more than the condition of its links and adjacent nodes. We construct a rooted tree for a given destination in the Kautz network, and use it to develop DFTR such that a faulty component will never be encountered more than once. In DFTR, each node is attempting to route a message via the shortest path. If a node detects a faulty node at the next hop, a best alternative path for routing the message around the faulty component is to be obtained. A best alternative path is first generated by the reduced concatenation of this node and the destination, and then is checked to make sure that it does not contain any of encountered faulty nodes. If it does, a new alternative path is generated as before. We invent an efficient approach in the checking step to reduce computational time. With a slight modification, DFTR may adapt to de Bruijn networks as well.

Original languageEnglish
Pages (from-to)99-106
Number of pages8
JournalJournal of Parallel and Distributed Computing
Volume20
Issue number1
DOIs
StatePublished - 1 Jan 1994

Fingerprint Dive into the research topics of 'Distributed fault-tolerant routing in kautz networks'. Together they form a unique fingerprint.

  • Cite this