Fault-Tolerant Routing in (n, k) - Star Graphs

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.