CaltechAUTHORS
  A Caltech Library Service

Tolerating multiple faults in multistage interconnection networks with minimal extra stages

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

[img]
Preview
PDF
See Usage Policy.

178Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:FANieeetc00

Abstract

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.


Item Type:Article
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
Record Number:CaltechAUTHORS:FANieeetc00
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:FANieeetc00
Alternative URL:http://dx.doi.org/10.1109/12.869334
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6972
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:03 Jan 2007
Last Modified:26 Dec 2012 09:27

Repository Staff Only: item control page