Title :
Fault-Tolerant Routing Based on Directed Safety Levels in a Hyper-Star Graph
Author :
Nishiyama, Youji ; Hirai, Yuki ; Kaneko, Kunihiko
Author_Institution :
Dept. of Comput. & Inf. Sci., Tokyo Univ. of Agric. & Technol., Tokyo, Japan
Abstract :
A hyper-star graph HS(2n, n) is promising as a generic topology for interconnection networks of parallel processing systems because it has merits of a hypercube and a star graph. This paper proposes an algorithm that constructs a fault-free path between a pair of non-faulty nodes in HS(2n, n) with faulty nodes. In addition, we conduct a computer experiment to show its effectiveness.
Keywords :
computational complexity; fault tolerance; graph theory; hypercube networks; multiprocessing systems; network theory (graphs); directed safety levels; fault-free path; fault-tolerant routing; faulty nodes; generic topology; hyper-star graph; hypercube; interconnection networks; nonfaulty nodes; parallel processing systems; faulty nodes; hypercube; interconnection network; star graph;
Conference_Titel :
Advanced Computer Science Applications and Technologies (ACSAT), 2012 International Conference on
Conference_Location :
Kuala Lumpur
Print_ISBN :
978-1-4673-5832-3
DOI :
10.1109/ACSAT.2012.76
