Fault tolerant message routing on large parallel systems

The problem of designing massively fault-tolerant message routing schemes for large parallel systems is considered. The notion of faults is extremely flexible and applies to all situations where a component is unavailable to participate in message communications. Attention is focused on the performance of schemes which use only local information to make local decisions. A framework for the analysis of fault-tolerant routing schemes is presented and used to analyze the efficacy of minimal path routing methods. Fault-tolerant routing schemes are derived by application of a technique called sidetracking. Viewed as making local decisions, a sidetracking scheme attempts to decrease the distance to the destination: if this is not possible, then the packet is routed randomly so as to increase the distance as little as possible. For single-message routing on a hypercube, it is shown that the performance of a sidetracking scheme is near optimal, successfully routing with high probability and low average excess delay. Applications of the sidetracking technique to single-message routing on a two-dimensional mesh and to multiple-message permutation routing on a hypercube are presented