DocumentCode
3599706
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
fYear
2014
Firstpage
113
Lastpage
118
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel and Distributed Computing, Applications and Technologies (PDCAT), 2014 15th International Conference on
Type
conf
DOI
10.1109/PDCAT.2014.27
Filename
7174774
Link To Document