''Dependent & Multimode Failures in Reliability Evaluation of Extra-Stage Shuffle-Exchange MINs''

Jerry L. Trahan

Daniel X. Wang

Suresh Rai

IEEE Trans. Reliability, vol. 44, no. 1, pp. 73-86, 1995


Previous reliability evaluation efforts for Multistage Interconnection Networks (MINs) assumed that all failures are statistically independent and that no degraded operational modes exist for switches, though these assumptions are inconsistent with realistic conditions. For example, researchers have described instances of dependent failures, or fault side-effects, in some MINs. This paper presents efficient algorithms for terminal, broadcast, and K-terminal reliability evaluation of the Shuffle-Exchange Network with an Extra stage (SENE), a redundant path MIN, under assumptions that allow dependence between failures and degraded operational modes for switches. A modified shock model incorporates failure dependency and multiple operational modes into the reliability evaluation. For an N x N SENE, the reliability algorithms run in time O(log N), O(log N), and O(k log N), respectively, where k = | K |.