Fan, Chenggong Charles and Bruck, Jehoshua (2000) Tolerating multiple faults in multistage interconnection networks with minimal extra stages. IEEE Transactions on Computers, 49 (9). pp. 998-1004. ISSN 0018-9340 http://resolver.caltech.edu/CaltechAUTHORS:FANieeetc00
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:FANieeetc00
Adams and Siegel (1982) proposed an extra stage cube interconnection network that tolerates one switch failure with one extra stage. We extend their results and discover a class of extra stage interconnection networks that tolerate multiple switch failures with a minimal number of extra stages. Adopting the same fault model as Adams and Siegel, the faulty switches can be bypassed by a pair of demultiplexer/multiplexer combinations. It is easy to show that, to maintain point to point and broadcast connectivities, there must be at least S extra stages to tolerate I switch failures. We present the first known construction of an extra stage interconnection network that meets this lower-bound. This 12-dimensional multistage interconnection network has n+f stages and tolerates I switch failures. An n-bit label called mask is used for each stage that indicates the bit differences between the two inputs coming into a common switch. We designed the fault-tolerant construction such that it repeatedly uses the singleton basis of the n-dimensional vector space as the stage mask vectors. This construction is further generalized and we prove that an n-dimensional multistage interconnection network is optimally fault-tolerant if and only if the mask vectors of every n consecutive stages span the n-dimensional vector space.
|Additional Information:||© Copyright 2000 IEEE. Reprinted with permission. Manuscript received 27 Oct. 1997; revised 15 Mar. 1999; accepted 21 June 2000. The authors wish to thank the editor and the reviewers for their valuable input to this paper. This research was supported in part by US National Science Foundation (NSF) Young Investigator Award CCR-9457811, by the NSF Graduate Fellowship, by the Sloan Research Fellowship, and by DARPA and BMDO through an agreement with NASA/OSAT.|
|Subject Keywords:||Multistage Interconnection Networks (MIN), fault tolerance, extra-stage, switch faults, stage masks|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Archive Administrator|
|Deposited On:||03 Jan 2007|
|Last Modified:||26 Dec 2012 09:27|
Repository Staff Only: item control page