Depth-First Search Approach for Fault-Tolerant Routing in Hypercube Multicomputers

Abstract

Using depth-first search, we develop and analyze the performance of a routing scheme for hypercube multicomputers in the presence of an arbitrary number of faulty components. We derive an exact expression for the probability of routing messages via optimal paths (of length equal to the Hamming distance between the corresponding pair of nodes) from the source node to an obstructed node. The obstructed node is defined as the first node encountered by the message that finds no optimal path to the destination node. Also, bounds for this probability are derived in closed form. Note that the probability of routing messages via an optimal path between any two nodes is a special case of our results, and can be obtained by replacing the obstructed node with the destination node. Numerical examples are also given to illustrate our results, and show that in the presence of component failures the depth-first search routing can route a message via an optimal path to its destination with a very high probability. © 1990 IEEE