Reliability Analysis of Interconnection Networks Using Hierarchical Composition

Based on the nature of the upper-and lower-bound block diagram models of Multistage Interconnection Networks (MINs), we generalize and consider a series system consisting of independent subsystems. In order to model the reliability of such a system with Online repair and imperfect coverage, the usual approach is to construct and solve a large, overall Markov model. Instead, we propose a 2-level hierarchical model in which each subsystem is modeled as a Markov chain and the system reliability is then modeled as a series system of independent “Markov” components. We extend this technique to compute the instantaneous availability of the system with imperfect coverage and Online repair. We have thus extended the size of problems for which reliability/availability analysis, incorporating imperfect coverage and Online repair, can be computed without resorting to a large, 1-level Markov model. Extensions to allow for transient faults and phase-type repair time distributions are straightforward. It should be possible to apply our approach to other fault-tolerant MINs and to any system that can be modeled as a series system where each subsystem has a parallel-redundant structure. © 1989 IEEE