Reliability evaluation and decision problems in extra stage shuffle‐exchange MINs
Jerry L. Trahan, Suresh Rai · Networks · 1993
Abstract A multistage interconnection network (MIN) uses switching elements for interconnecting processors to memory or processors. This paper first considers a stochastic model of a shuffle exchange network (of sizeN) with an extra stage and develops terminal, broadcast, andK‐terminal reliability evaluation algorithms that run in timeO(log logN),O(logN), andO(klogN), respectively, wherek= |K|. Second, a deterministic model for the MIN is considered and decision problems in which one is interested in evaluating whether a network can effect a specified set of connections with a given set of failures are solved. We develop a set of approaches for the SENE for the terminal decision, broadcast decision, and network decision problems and for the generalS, Tdecision problem for an input setSand output setT. Each algorithm runs within time polynomial in the size of the SENE and the number of faults and, in some cases, logarithmic in the size of the SENE and polynomial in the number of faults. These approaches are based on either testing for the existence of an appropriate pathset or testing for the nonexistence of an appropriate cutset. ©1993 by John Wiley & Sons, Inc.