Analysis of fault-tolerance in a class of multistage interconnection networks

Some fault-tolerance properties in a class of 2log₂N- or (2log₂N-1)-stage rearrangeable network are analyzed. The analysis is based on the newly developed inside-out routing algorithm. It is shown that the algorithm can provide us with a higher degree of freedom in the ways of realizing a given permutation than the well-known looping algorithm. In finding a set of complete assignments for the center-stage cycles, alternate paths can be obtained by changing the initial position or changing the assigning direction or even interchanging the first level decompositions of a permutation. Utilizing the alternate paths, it is shown that any single control fault can be tolerated in the network and in addition, any single switching-element fault can also be tolerated with some performance degradation. These new approaches are originated from the fact that the algorithm routes outward from the center stages and due to this, the center stages and two half networks can be treated separately. An example is given to demonstrate the fault-tolerance in the networks