Fault-tolerant routing in unique-path multistage interconnection networks

Two pass routing scheme is described for communication in a multiprocessor system employing a unique-path multistage interconnection network in the presence of faults in the network. It is capable of tolerating all single faults and many multiple faults in all except the first and last stages of the network. The routing scheme is useful for tolerating both permanent as well as intermittent faults in the network. The hardware over head for implementing the scheme is very small and no time-penalty is paid in the fault-free case.