Title :
Fault-Tolerant Routing in (n, k) - Star Graphs
Author :
Ito, Takara ; Myojin, Manabu ; Hirai, Yuki ; Kaneko, Keiichi
Author_Institution :
Grad. Sch. of Eng., Tokyo Univ. of Agric. & Technol., Koganei, Japan
Abstract :
An (n, k)-star graph Sn, k is a promising topology for interconnection networks of parallel processing systems because it inherits the merits of a star graph while providing various network sizes. In this study, we propose a fault-tolerant routing algorithm that establishes a fault-free path between any pair of non-faulty nodes in an Sn, k with faulty nodes by using limited global information called safety vectors. In addition, we carried out a computer experiment to verify its effectiveness.
Keywords :
fault tolerant computing; graph theory; parallel processing; vectors; fault-free path; fault-tolerant routing algorithm; interconnection networks; parallel processing systems; safety vectors; star graphs; Fault tolerance; Fault tolerant systems; Hypercubes; Network topology; Routing; Safety; Topology;
Conference_Titel :
Parallel and Distributed Computing, Applications and Technologies (PDCAT), 2014 15th International Conference on
DOI :
10.1109/PDCAT.2014.27
