JISE


  [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ]


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


YO NISHIYAMA1, YUKO SASAKI1, YUKI HIRAI2, HIRONORI NAKAJO1
AND KEIICHI KANEKO1,+
1Graduate School of Engineering
Tokyo University of Agriculture and Technology
Koganei-shi, Tokyo 184-8588, Japan

2Adimissons Center
Shinshu University
Matsumoto-shi, Nagano 390-8621, Japan

+E-mail: k1kaneko@cc.tuat.ac.jp


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(n2). 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

  Retrieve PDF document (JISE_201806_01.pdf)