Fault-Tolerant Routing Based on Routing Capabilities in a Hyper-Star Graph

摘要

A hyper-star graph HS(n, k) provides a promising topology for interconnection networks of parallel processing systems because it inherits the advantages of a hypercube and a star graph. In this paper, we focus on fault-tolerant routing in an HS(n, k) graph with faulty nodes and propose an algorithm to establish a fault-free path between a pair of non-faulty nodes. The algorithm uses limited global information called routing capabilities. Though routing capabilities were originally invented for a hypercube, we extend their notion so that they can be applied to an HS(n, k) graph, which is asymmetric. We have proved that the time complexity to calculate routing capabilities with respect to all the distances at each node is O(n(2)). In addition, we present the results of a computer experiment to verify that our algorithm attains high reachability to the destination nodes.