A depth-first search routing algorithm for star graphs and its performance evaluation

A fault-tolerant routing algorithm has been developed for star graph interconnection topology by using a depth-first search strategy. The proposed algorithm routes a message from the source to the destination along an optimal path with a very high probability and is guaranteed to trace a path as long as the source and the destination are not disconnected. We derive exact mathematical expressions for the probabilities that the algorithm will compute an optimal path for a given number of faulty links in the network. The analysis reveals many interesting topological properties of the star graphs.