Computing Network Reliability

Abstract

This paper presents an algorithm to compute reliability measures on a stochastic network in which both nodes and links can fail. The measures considered are the probability that nodes s and t can communicate for all node pairs s and t , the probability that all operative node pairs can communicate, and the expected number of node pairs communicating. It also computes the latter two measures when all communication must proceed through a root node. A specialized version of the algorithm is given for networks in which only nodes can fail.