Probability-based fault-tolerant routing in hypercubes

J. Al-Sadi, K. Day, M. Ould-Khaoua*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)


This paper describes a new fault-tolerant routing algorithm for the hypercube, using the concept of probability vectors. To compute these vectors, a node first determines its faulty set, which represents the set of all its neighbouring nodes that are faulty or unreachable due to faulty nodes or links. Each node then calculates a probability vector, where the kth element represents the probability that a destination node at distance k cannot be reached through a minimal path due to a faulty node or link. The probability vectors are used by all the nodes to achieve an efficient fault-tolerant routing in the network. A performance comparison with the recently proposed safety-vectors algorithm, through extensive simulation, shows that the new algorithm exhibits superior performance in terms of routing distances and percentage of reachability.

Original languageEnglish
Pages (from-to)368-373
Number of pages6
JournalComputer Journal
Issue number5
Publication statusPublished - 2001

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'Probability-based fault-tolerant routing in hypercubes'. Together they form a unique fingerprint.

Cite this