Exact calculation of computer network reliability

Abstract In designing a distributed computer network, the reliability and availability of the communication paths between all pairs of centers is a primary consideration. Many different approaches have been taken to calculate exactly the probability of successful communication between any specified pair of centers, for a given failure probability of the individual computer systems and communication facilities. However, almost all of these methods are not computationally feasible for large networks. Consequently, approximate calculations of network reliability have been suggested. In this paper a procedure is given for the exact calculation of the probability that all paths between a pair of nodes in a given network are interrupted. The procedure generates mutually exclusive sets of cutting states and calculates the probability of the related events. Summing these values one obtains the probability of service interruption between the specified pair of nodes. If all links fail with equal probability p, the coefficients of a polynomial can be calculated, describing the service disruption probability as a function of p.