THE NUMBER OF PERMUTATIONS REALIZABLE IN FAULT-TOLERANT MULTISTAGE INTERCONNECTION NETWORKS

In this paper we estimate the number of permutations realizable in fau lt-tolerant multistage interconnection networks designed to tolerate f aults on any switching element. The Parallel Omega network and the IND RA network are representative types of fault-tolerate multistage inter connection networks designed to tolerate a single fault. In order to e valuate the enhancement in the function of network by preparing the ha rdware redundancy for fault-tolerance, we estimate the number of permu tations realizable in fault-tolerant networks. This result enables us to set up a standard to evaluate the hardware redundancy required to t olerate multifaults from the viewpoint of the enhancement of network f unction. This paper concludes that in the case where the number of inp uts is up to 32 the increase ratio of the number of realizable permuta tions is no more than 1/0.73 even if the tolerance to multifaults is p repared instead of the tolerance to a single fault.