Parallel Computing the Diameter Constrained Reliability of Networks Using Supercomputers with Distributed Memory
摘要
The problem of computing the diameter constrained reliability of networks is studied. We assume that the network has unreliable communication links and perfectly reliable nodes among which there are terminals that must be able to establish a connection with each other, even if some edges fail. The diameter constrained reliability for such network is defined as a probability that every pair of terminals of network is connected by operational paths with a number of included edges less or equal to a given integer. The problem of computing this characteristic is NP-hard, just like computation problems of other network reliability measures. To solve such problems, methods based on high-performance computing are increasingly being developed. We provide an overview of such approaches, and study the MPI-parallelization of various factoring-based methods, which are used for diameter constrained reliability calculation.