For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
The Number of Permutations Realizable in Fault-Tolerant Multistage Interconnection Networks
Hiroshi MASUYAMA Tetsuo ICHIMORI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1994/09/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Networks
the number of permutations, fault-tolerant, multistage interconnection network, parallel Omega network, and INDRA network,
Full Text: PDF(658.5KB)
>>Buy this Article
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.