A Heuristic-Based Wormhole Routing Algorithm for Hypercube Multicomputer Networks

摘要

In this paper, we consider fault-tolerant routing algorithms in hypercube multicomputer networks. In particular, one of the most quoted adaptive fault-tolerant routing algorithm for hypercubes in the literature is studied in detail and its limited ability to route messages in the presence of some fault patterns (i.e., combination of node and link faults), is pointed out. A modified algorithm is proposed and its performance, using simulation, is compared to that of the above mentioned algorithm. It is shown that the proposed algorithm outperforms the existing one in terms of its ability to route routable messages around the hypercube in the presence of node and/or links faults. This improvement is achieved while using the same average path length or even improving it. Illustrative examples are shown in support of such improvement.