Analyzing network reliability with imperfect nodes using OBDD

Abstract

The nodes as well as the links may fail in a real network. Almost all the existing tree-based partitioning algorithms are inefficient in finding the disjoint paths in a large network even if all the nodes are perfect. The number of disjoint paths will increase dramatically if a network has imperfect nodes. In this paper, strategies based on edge expansion diagram using OBDD are proposed to efficiently evaluate the reliability of a network with imperfect nodes. The fixed sink algorithm is proposed to further speed up the process for k-terminal networks. The essential variable is also defined to help us identify the most critical part of the network. Our methods are better than previous numeric algorithms and have two significant results. First, it takes only about 65 seconds to identify the essential variable for a 2/sup 99/-path network on a SPARC 20 with 128 MB of memory. Second, the overhead due to considering imperfect nodes is as low as 0.2% in average for seven st3/spl times/n networks, where n = 13, 14,..., 19.