Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 1, 1996 | public
Report Open

Optimal Constructions of Fault-Tolerant Multistage Interconnection Networks

Abstract

In this paper we discover the family of Fault-Tolerant Multistage Interconnection Networks (MINs) that tolerates switch faults with a minimal number of redundant switching stages. While previously known constructions handled switch faults by eliminating complete stages, our approach is to bypass faulty switches by utilizing redundant paths. As a result, we are able to construct the first known fault-tolerant MINs that are optimal in the number of redundant stages. Our fault model assumes that a faulty switch can be bypassed and our goal is to guarantee arbitrary point to point and broadcast connectivity. Under this model, we show that to tolerate f switch faults the MIN must have at least f redundant stages. We then present the explicit construction of a MIN that meets this lower-bound. This construction repeatedly uses the singleton basis of the n-dimensional vector space as the mask vectors of the MIN. We generalize this construction and prove that an n-dimensional MIN is optimally fault-tolerant if and only if the mask vectors of every n consecutive stages span the n-dimensional vector space.

Files

etr014.pdf
Files (1.6 MB)
Name Size Download all
md5:724251336ebc0a979b45005ebba72774
1.3 MB Preview Download
md5:6cf6b81be6ffc233a393da82bd9a4965
317.9 kB Download

Additional details

Created:
August 20, 2023
Modified:
October 24, 2023