Publication Details
Title: Fault-Tolerant Routing in Hypercube Multicomputers Using Depth-First Search
Author: M.-S. Chen and K. G. Shin
Group: ICSI Technical Reports
Date: February 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-006.pdf
Overview:
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 Information:
ICSI Technical Report TR-89-006
Bibliographic Reference:
M.-S. Chen and K. G. Shin. Fault-Tolerant Routing in Hypercube Multicomputers Using Depth-First Search. ICSI Technical Report TR-89-006, February 1989
Author: M.-S. Chen and K. G. Shin
Group: ICSI Technical Reports
Date: February 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-006.pdf
Overview:
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 Information:
ICSI Technical Report TR-89-006
Bibliographic Reference:
M.-S. Chen and K. G. Shin. Fault-Tolerant Routing in Hypercube Multicomputers Using Depth-First Search. ICSI Technical Report TR-89-006, February 1989