Reliability Analysis for Disjoint Paths

Our contemporary society survives on the services provided by several network infrastructures, such as communication, power, and transportation, so their reliability should be accurately evaluated from various aspects. While past studies defined network reliability in terms of connectivity, some of the network connections that have been established may suffer from insufficient resources, i.e., vertices may be connected on a network but flows might fail due to resource contention. As a first step to address resource protection, this paper introduces path disjointness to the field of network reliability analysis, i.e., we evaluate the probability that given terminals are connected via edge-or vertex-disjoint paths. In addition, we also deal with identifying critical links under path disjointness. Since network reliability analysis is a computationally tough problem, we propose efficient algorithms utilizing the data structure of binary decision diagrams. Numerical experiments show that our method scales up to a network with 189 links. We show that network reliability and the criticality of links are greatly dependent on path disjointness; this validates the importance of the proposed method.