Tolerating multiple faults in multistage interconnection networks with minimal extra stages

In their 1982 paper. Adams and Siegel proposed an Extra Stage Cube Intercon nection Network that tolerates one switch failure with one extra stage. We extend their results and discover a class of Extra Stage Interconnection Ne tworks that tolerate multiple switch failures with a minimal number of extr a stages. Adopting the same fault model as Adams and Siegel, the faulty swi tches can be bypassed by a pair of demultiplexer/multiplexer combinations. It is easy to show that, to maintain point to point and broadcast connectiv ities. there must be at least of extra stages to tolerate f switch failures . We present the first known construction of an Extra Stage Interconnection Network that meets this lower-bound. This n-dimensional Multistage Interco nnection Network has n + f stages and tolerates f switch failures. An n-bit label called mask is used for each stage that indicates the bit difference s 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 Muitistage Inter connection Network is optimally fault-tolerant if and only if the mask vect ors of every n consecutive stages span the n-dimensional vector space.