Design of Fault Tolerant Multistage Interconnection Networks with Dilated Links

Naotake KAMIURA  Takashi KODERA  Nobuyuki MATSUI  

IEICE TRANSACTIONS on Information and Systems   Vol.E84-D   No.11   pp.1500-1507
Publication Date: 2001/11/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Function Integrated Information Systems)
multistage interconnection network,  fault tolerance,  baseline network,  throughput,  

Full Text: PDF>>
Buy this Article

In this paper we propose a MIN (Multistage Interconnection Network) whose performance in the faulty case degrades as gracefully as possible. We focus on a two-dilated baseline network as a sort of MIN. The link connection pattern in our MIN is determined so that all the available paths established between an input terminal and an output terminal via an identical input of a SE (Switching Element) in some stage will never pass through an identical SE in the next stage. Extra links are useful in improving the performance of the MIN and do not complicate the routing scheme. There is no difference between our MIN and others constructed from a baseline network with regard to numbers of links and cross points in all SEs. The theoretical computation and simulation-based study show that our MIN is superior to others in performance, especially in robustness against concentrated SE faults in an identical stage.