Journal of Information Science and Engineering, Vol. 34 No. 6, pp. 1353-1366

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.

Keywords:
interconnection network, parallel processing, hypercube, star graph, faulty
node