In: Journal of Systems and Software, Vol. 45, No. 2, pages 155-171. 1998.
Abstract: To study and analyze the reliability of complex systems such as multistage interconnection networks (MINs) and hierarchical interconnections networks (HINs), traditional techniques such as simulation, the Markov chain modeling, and probabilistic techniques have been widely used. Unfortunately, these traditional approaches become intractable when dealing with real-life applications. For the purpose of reliability analysis, the Petri net theory can also be used, but the major drawback of PN models is the state space explosion with increasing model complexity. Therefore, this paper proposes two analytical decomposition techniques for computing (approximately) the transient state space solution of large stochastic Petri net (SPN) models of MINs and HINs. In the first technique, a large scale SPN model is partitioned into smaller submodels. These submodels are compressed and combined to calculate the entire net. Throughout the reliability analysis of a simple example, the decomposition of an entire net model of the system into subnets is explained. The modeling power of the proposed technique is illustrated through the reliability analysis of an 8 by 8 Omega network as a practical example of MINs. The second approach uses the topological properties of HINs to build an SPN generic modeling methodology to aid the reliability evaluation of different HIN configurations. Finally, the numerical reliability results obtained from the proposed techniques are discussed. It has been shown that the proposed techniques give results quite close to those obtained by the exact method with an enormous saving in computation time and memory usage.
Keywords: Markov chains, decomposition techniques, interconnection networks, reliability analysis, stochastic Petri nets, transient analysis.