The Number of Permutations Realizable in Fault-Tolerant Multistage Interconnection Networks

Hiroshi MASUYAMA  Tetsuo ICHIMORI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E77-D   No.9   pp.1032-1041
Publication Date: 1994/09/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Networks
Keyword: 
the number of permutations,  fault-tolerant,  multistage interconnection network,  parallel Omega network,  and INDRA network,  

Full Text: PDF>>
Buy this Article



Summary: 
In this paper we estimate the number of permutations realizable in fault-tolerant multistage interconnection networks designed to tolerate faults on any switching element. The Parallel Omega network and the INDRA network are representative types of fault-tolerate multistage interconnection networks designed to tolerate a single fault. In order to evaluate the enhancement in the function of network by preparing the hardware redundancy for fault-tolerance, we estimate the number of permutations realizable in fault-tolerant networks. This result enables us to set up a standard to evaluate the hardware redundancy required to tolerate multifaults from the viewpoint of the enhancement of network function. This paper concludes that in the case where the number of inputs is up to 32 the increase ratio of the number of realizable permutations is no more than 1/0.73 even if the tolerance to multifaults is prepared instead of the tolerance to a single fault.