Algorithms for network reliability and connection availability analysis

Communications networks used for transmitting and receiving voice or digital data involve copper wire, fiber optics, radio, satellite, and microwave links. In general, these networks are large, diffuse, and complex. Even using modern high-speed computers, exact computations of the network reliability for use as a figure of merit in an interactive network design procedure can take an inordinate amount of time. This paper discusses various exact techniques whose complexity results in run-times short enough for practical network design. We model the network by an undirected probabilistic graph whose vertices represent the nodes and whose edges represent the links. A special feature of our model is that it allows nodes to be imperfect and associates a reliability measure with each node, assumed to succeed or fail independently. Therefore, the network reliability measure is based upon the reliability measures of the individual links and nodes