Fault-Tolerant Routing in Hypercube Multicomputers Using Depth-First Search

TitleFault-Tolerant Routing in Hypercube Multicomputers Using Depth-First Search
Publication TypeTechnical Report
Year of Publication1989
AuthorsChen, M-S., & Shin K. G.
Other Numbers505

A fault-tolerant routing scheme for hypercube multicomputers is developed using the depth-first search. The routing scheme requires a node to know only the condition (faulty or not) of its own links, and adds information on the components traversed to each message as it is routed toward the destination node. Performance of the proposed routing scheme is rigorously analyzed. We derive an exact expression for the probability of routing messages via optimal paths (of length identical to the Hamming distance between the corresponding pair of nodes) from the source node to an obstructed node, the first node on a path determined by the above routing scheme from which no optimal path to the destination exists. Moreover, bounds for this probability are derived in closed form. The probability of routing messages via optimal paths between the source and destination can be obtained from this expression by replacing the obstructed node with the destination node. The lengths of paths obtained from this scheme are analyzed, and the scheme, despite its simplicity, is shown to be able to route messages via optimal paths with a very high probability. Due to the absence of information at each node on components other than its own links, the actual paths chosen by the above scheme could sometimes be longer than the desired. To alleviate this deficiency, we also present a simple modification to the above routing scheme in which every node is made aware of not only the condition of its own links but also that of links one hop away from the node. The improvement of routing efficiency with this additional information at each node is analyzed.

Bibliographic Notes

ICSI Technical Report TR-89-006

Abbreviated Authors

M.-S. Chen and K. G. Shin

ICSI Publication Type

Technical Report