One-fault tolerance and beyond in wormhole routed meshes

The ability to tolerate one failing link in communication networks is sufficient for many practical purposes. One-fault tolerance can also be achieved at much lower cost than methods that can guarantee tolerance of multiple faults. We consider wormhole-routed meshes with two different routing algorithms (dimension order and positive first) and for each of these we propose two simple methods that guarantee to tolerate one failing link. Then we study how well these methods work in the presence of multiple faults. Through extensive experiments, we demonstrate that even if these simple methods are not guaranteed to be able to handle more than one fault, there is a high probability of them successfully handling a modest number of faults. (C) 1998 Elsevier Science B.V.