|
The network has been widely used for modeling a complex system
which can have component failures. Large networks have become
very common nowadays. The quality and the reliability of a network have to be fast evaluated with the best efficiency when adds a new edge or a new node. In other words, as the scale of the network is increasing, efficient evaluation tools have become very important. In this thesis, several symbolic methods are presented for different application domains to efficiently evaluate the reliabilities of large networks. These novel
methods are based on edge expansion diagram using OBDD
(ordered binary decision diagram) [20]. Due to the advantage of
sharing isomorphic graphs and Boolean manipulation using OBDD,
the computation becomes very efficient.
The application domains include finding a good variable ordering for OBDDs, efficiently evaluating the reliability of
a 2-terminal or a k-terminal network with perfect nodes, and analyzing the reliability of a network with imperfect nodes. These problems are all NP-hard problems and the exact enumerative algorithms can only solve a problem of limited size. However, due to more and more understanding about these problems, the proposed algorithms can efficiently deal
with large networks better than previous works.
The developed algorithms and notable results of four major
items of this thesis are briefly described in the following:
(1) For building OBDDs, two efficient variable ordering strategies for OBDDs are presented for different Boolean functions:
(i) a gate-level circuit with a large number of I/Os,
(ii) the reliability function of a network. A divide-and-conquer approach is presented to obtain a good variable ordering more efficiently than existing methods for gate-level circuits with a large number of I/Os. One notable result from our method is that we are able to build the OBDD for the cs38417 circuit within 1000 seconds on a SPARC 20 with 128M byte memory. For a given network, a breadth-first-search approach is proposed to obtain a good variable ordering for the reliability function of a network. One dramatic case of our experimental results for a 2-by-20 lattice network is only 115 nodes generated that the number of OBDD nodes is linearly proportional to the number of stages, which is much better than previous algorithms with exponential complexity using sum of disjoint products.
(2) On the calculation of terminal-pair reliability, an efficient methodology based on edge expansion diagram using OBDD with BFS ordering is presented in this thesis. The effectiveness of the proposed approach is demonstrated by performing experiments on benchmarks collected by previous works including the large networks (from 4 to 299 paths). One dramatic
improvement as demonstrated by our experimental results for a 2-by-n lattice network is that the CPU time of reliability calculation for a 100-stage lattice network is only about 2.28 seconds with 595 nodes generated on a SPARC 20 workstation with 128 Mbyte memory.
(3) On determination of the reliability of an undirected k-terminal network with perfect nodes, an efficient approach based on 2-terminal reliability function is presented in this thesis. One significant improvement as demonstrated by our experimental results on evaluating a st3x10 all-terminal network reliability is that it takes only 1.75 seconds on a SPARC 20 workstation, which is much better than the previous factoring algorithms.
(4) For analysis of the reliability of a network with imperfect nodes, two efficient strategies based on edge expansion diagrams using OBDD are presented in this thesis. The first method is to directly construct the reliability Boolean function of a given network using OBDD by traversing the network with diagram-based edge expansion. The second method is to build the OBDD-based reliability function by assuming that all nodes are perfect
initially, then substitute this reliability function with incident edge formula. Finally, the network reliability is obtained by evaluating on this OBDD. In order to analyze the property of a network, the essential variable and the network sensitivity are also defined. Two notable results are that
the CPU time of analyzing the essential variable for a 299-path network is only about 65 seconds on a SPARC 20 workstation with 128 Mbyte memory and the overhead due to considering imperfect nodes using our strategies is very low with a value of 0.2% in average for seven st3xn networks, where n = 13,14, ..,19.
In fact, the proposed methods have avoided many limitations
of existing algorithms in manipulating large networks, and our results have outperformed those results by previous approaches significantly as shown in the experimental results of later chapters. In other words, we can efficiently evaluate and analyze the reliability of large networks, hitherto thought impossible.
|