A Routing Algorithm for the Star Interconnection Network in the Presence of Faults*
Abstract
This paper presents a fault tolerant routing algorithm for the star graph. The suggested algorithm is based on the concept of unsafety vectors, originally proposed for hypercubes. In this algorithm, each node starts by computing a first level unsafety set, composed of the set of unreachable neighbors. It then performs some exchanges with its neighbors to determine the unsafety nodes. After that, all nodes have the addresses of all faulty nodes. Based on the information gathered in each node, faulttolerant routing between a source node and a destination node is realized. We conducted a performance comparison between the star and hypercube graph using the unsafety vectors routing algorithm under different working conditions. The results obtained through simulation experiments reveal that the hypercube is of superior performance compared to the star graph in the presence of low fault rates. But its performance under high fault rates falls short of that of the star graph.
Keywords
multicomputers, interconnection networks, stars, hypercube, fault-tolerant routing, performance comparison
