Fault-tolerant routing in multistage interconnection networks

The fault tolerance of multiprocessor systems with multistage interconnection networks under multiple faults in the network is studied. The fault tolerance is analyzed with respect to the criterion of dynamic full access (DFA) property of the processors in the system. A characterization of multiple faults in the Omega network is introduced and used to develop simple tests for the DFA capability under a given set of faults. It is shown that the DFA capability is maintained under a large number of faults. A maximum of three passes is shown to be sufficient for communication between any two processors in the system when the faults satisfy certain conditions which can be checked easily. For cases in which these conditions do not hold, at most log₂ N-2 passes through the network are shown to be sufficient if a set of weaker conditions is satisfied. Techniques for routing data between processing elements through the faulty network are described. Extension of the results to general k-stage shuffle/exchange networks with k<log₂N is also given. These techniques allow continued operation of a multiprocessor system in the presence of network faults with full connectivity among the processing elements of the system and minimal loss of network throughput