ADAPTIVE FAULT-TOLERANT ROUTING IN STAR NETWORKS
Khaled Day, Abdel‐Elah Al‐Ayyoub · Journal of Interconnection Networks · 2001
We take advantage of the hierarchical structure of the star graph network to obtain an efficient method for constructing node-disjoint paths between arbitrary pairs of nodes in the network. A distributed fault-tolerant routing algorithm for the star network based on this construction method is then presented and evaluated. The proposed algorithm adapts the routing decisions in response to node failures. Node failure and repair conditions may arise dynamically (at any time) provided that the total number of faulty nodes at any given time is less than the node-connectivity n - 1 of the n-star. When a message is blocked due to faulty components, the source of the message is warned and requested to switch to a different node-disjoint path. The methods used to identify the paths, to propagate failure information back to source nodes, and to switch from a routing path to another incur little communication and computation overhead. We show that if the node failures occur 'reasonably' apart in time, then all messages will be routed on paths of length δ + ε where δ is the minimum distance between the source and the destination and ε is 0, 2, or 4. In the unlikely case where more failures occur in a 'short period', the algorithm still delivers all messages but via possibly longer paths.