Premium
Reliability evaluation and decision problems in extra stage shuffle‐exchange MINs
Author(s) -
Trahan Jerry L.,
Rai Suresh
Publication year - 1993
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230230422
Subject(s) - logarithm , multistage interconnection networks , set (abstract data type) , reliability (semiconductor) , computer science , time complexity , discrete mathematics , polynomial , decision problem , interconnection , binary logarithm , mathematical optimization , mathematics , combinatorics , algorithm , computer network , mathematical analysis , power (physics) , physics , quantum mechanics , programming language
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 size N ) with an extra stage and develops terminal, broadcast, and K ‐terminal reliability evaluation algorithms that run in time O (log log N ), O (log N ), and O ( k log N ), respectively, where k = | 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 general S, T decision problem for an input set S and output set T . 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.