Fault-tolerant wormhole routing in meshes
Christopher J. Glass, Lionel Ming-shuan Ni · 2002
It is shown how to modify the routing algorithms produced by the turn model to encompass dynamic faults. The authors describe how to modify the negative-first routing algorithm, which the turn model produces for n-dimensional meshes without virtual channels, to make it one-fault tolerant. Simulations of the one-fault-tolerant routing algorithms in a two-dimensional mesh indicate that misrouting increases communication latencies significantly at high throughputs. The conclusion is that misrouting should be used only for increasing the degree of fault tolerance, never for just increasing adaptiveness. Finally, the authors describe how to modify the negative-first routing algorithm to make it (n-1)-fault tolerant for n-dimensional meshes.