A novel scheme to improve fault-tolerant capabilities of multistage interconnection networks

In this paper, we propose a novel augmenting and partitioning scheme for constructing multistage interconnection networks (MINs) with improved fault-tolerant capabilities. We first propose a partitioning scheme to construct and analyze partitioned MINs (PMINs). A simulation method is developed, based on the stuck-at fault model, to evaluate dynamic full access (DFA) and average number of passes in PMINs. We then propose an augmenting scheme to construct augmented partitioned MINs (APMINs) with further enhanced fault-tolerant capabilities. Simulation analysis of APMINs, based on the switch level fault model, showed that the proposed scheme significantly improves the fault-tolerant capability of MINs. Finally, the effectiveness of the proposed scheme is evaluated with respect to cost, DFA, locality, and average path length. This revised version was published online in June 2006 with corrections to the Cover Date.