We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Fault-Tolerant Routing Based on Routing Capabilities in a Hyper-Star Graph.
- Authors
YO NISHIYAMA; YUKO SASAKI; YUKI HIRAI; HIRONORI NAKAJO; KEIICHI KANEKO
- Abstract
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.
- Subjects
ROUTING (Computer network management); WIRELESS sensor networks; GRAPHIC methods; PARALLEL processing; STAR graphs (Graph theory)
- Publication
Journal of Information Science & Engineering, 2018, Vol 34, Issue 6, p1353
- ISSN
1016-2364
- Publication type
Article
- DOI
10.6688/JISE.201811_34(6).0001