Designing a New Class of Fault Tolerant Multistage Interconnection Networks

摘要

This paper proposes a technique to modify a Multistage Interconnection Network (MIN) to augment it with fault tolerant capabilities. The augmented MIN is referred to as Enhanced MIN (E-MIN). The technique employed for construction of E-MIN is compared with the two known physical fault tolerance techniques, namely, extra staging and chaining. E-MINs are found to be more generic than extra staged networks and less expensive than chained networks. The E-MIN realizes all the permutations realizable by the original MIN. The routing strategies under faulty and fault free conditions are shown to be very simple in the case of E-MINs.