BDD-Based Reliability Analysis For Networks With Constraints

With the rapid development of information technology, networks gradually become a necessary carrier and tool in human's production and life. When a network breaks down, it brings significant influence and consequences on people. Thus it is imperative for us to strengthen the construction of network reliability.In the network reliability analysis, using binary decision diagram technique to analyze the reliability of networks can greatly improve network's performance and efficiency. The BDD-based network reliability analysis is mainly to find a better network performance variable collating sequence, and then use EED (edge expansion diagram) to construct a BDD equivalent to the original network, and finally calculate the reliability values of the network. In this thesis, we select an appropriate variable ordering, generate an equivalent BDD to the original network using methods such as network decomposition principle and calculate the value of the whole network reliability through a recursive method.According to the existing research on BDD-based reliability analysis for networks, there are still many actual problems in these aspects. In order to solve these problems, in this thesis, we did some research and specific work, including:(1) the terminal-pair network reliability analysis with path constraints. For the terminal-pair network reliability analysis with path constraints, a data packet being transmitted from the source node S to the target node T, must pass through some nodes between S and T, which are constraints in the sequence. A new reliability analysis algorithm based on BDD is proposed in this paper. The edge expansion diagram is used to implement path constraint, in which the constraint paths simply are kept, then the corresponding BDD is constructed and terminal-pair network reliability is analyzed. This will effectively solve practical path constraint of many problems, such as in e-government and e-commerce path constraint of point to point communication problems. It has strong practical significance.(2) K-terminal network reliability analysis with length constraint has lots of applications in online video and real-time communications. Basically, it will calculate K-terminal network reliability under the condition that the length among any terminal-pair of K-terminal is within a given time delay constraints called D. In this paper we propose the path constraint method based on truncation, and the traditional terminal-pair and K-terminal network reliability algorithm. Then, we build a BDD model for analyzing K-terminal network reliability with constraints. This research method is suitable for video conference and data transmission. For example, K-terminal point-to-point information flow achieves transmission under a certain time delay. It also has strong practical significance.Ultimately, this thesis on BDD-based reliability analysis for networks aims primarily at solving various practical problems and improves the algorithms proposed by Kuo in order to solve these practical problems.