Fault-tolerant wormhole routing algorithm for mesh networks

A multicomputer system can hardly avoid having faulty components in the rea l world. A good fault-tolerant routing scheme should tolerate as many fault patterns as possible and hence, reduce the number of disabled functional n odes. The authors consider disconnected unsurrounded faults, i.e, all disco nnected faults discussed in the literature. In disconnected unsurrounded fa ult models, there is no restriction on the shapes of faults. In the propose d routing scheme, a message always leaves each f-ring encountered at an app ropriate node such that no message will encounter the same f-ring again and therefore never get trapped in faults.