Network Reliability Evaluation Using Binary Decision Diagrams

Network reliability is the probability of correct communication between two specified nodes on a network. It is an important measure of a network’s quality of service, but the problem of determining it is NP-hard, and naive methods are difficult to compute even for networks with dozens of links. For practical use, however, it is known that network reliability can be computed exactly even for networks of several hundred links using a data structure called a zero-suppressed binary decision diagram (ZDD). Although network reliability has been studied for more than 60 years, efficient methods for evaluating reliability considering delay and time variation are still not known. In this project, we are studying efficient methods for reliability evaluation that take into account various real-world constraints.