Аналіз надійності комп’ютерної мережі на основі бінарної діаграми рішень

Abstract

Досліджено спосіб оцінки надійності комп’ютерних мереж на основі бінарної діаграми рішень (БДР). Розглянуто різні алгоритми обчислення надійності комп’ютерної мережі на основі БДР: алгоритм факторизації, алгоритм, що ґрунтується на пошуку мінімальних шляхів або перерізів, алгоритм створення БДР без отримання булевого виразу. Методи обчислення надійності на основі БДР дають змогу обчислити надійність мережі із сотень елементів. The present paper is aimed at investigating modelling and analysis techniques for the calculating the reliability of computer communication network using binary decision diagram. The network can be represented in a form of a graph, whose elements (vertices and edges) are considered as binary objects characterized by a working or a failed condition. Nodes and communication links of computer network may fail with known probability. The network reliability is defined as the probability that all nodes, or a subset of the nodes, of the graph communicate through at least one path of working edges. Failure of a single component may directly affect the functioning of a network. Determination of the probability properties of the network is based on Binary Decision Diagram and Shannon’s decomposition principle. Binary decision diagram is a modern data structure proved to be compact in representation and efficient in manipulation of Boolean formulas. A path is defined as asset of edges so that if these edges are all up, the system is up. A path is minimal if it has no proper subpaths. A cut is defined as a set of edges so that if these edges are all down, the system is down. A cut is minimal if it has no proper subcuts. Different approaches are based on the use of BDD. One is factoring algorithm. The idea is to choose an edge and break the model down into two cases: the first assumes the edge has failed, the second assumes it has not failed. For each case, a new reliability graph is built by taking into account the behavior of the chosen edge. The alternative class of methods is to directly obtain minpaths or mincuts. Minpaths are searched by means of the Dijkstra algorithm, while mincuts are searched by means of a recursive algorithm. In these methods we first enumerate all the minpaths and mincuts of the given network and then the reliability expression is evaluated using different methods, like inclusionexclusion method or sums of disjoint products. There are some disadvantages in the above methods. In the factoring algorithm, the number of factored reliability graphs will increase exponentially with the number of edges increases. In the minpaths or mincuts methods, as the number of edges becomes large, the number of minpaths or mincuts will be large and inclusion-exclusion or sums of disjoint products expression will be increased too large. Size of BDD strongly depends on the ordering of variables. The size of BDD means the total number of non-terminal vertices in the BDD and the number of vertices in particular level. There is no polynomial search algorithms for optimal variable ordering. The present paper introduces BDD representation of the 2-terminal connectivity of a graph without preliminary search for the minpaths or mincuts. The algorithm starts from the source node and visits the graph until the destination node is reached. The BDD construction starts recursively once the destination node is reached. The BDD’s of the nodes along a path from source node to destination node are combined in AND. If a node possesses more than one outgoing edge the BDD of the paths starting from each edge are combined in OR. A bridge network with directed arcs is considered as an example under assumption that only arcs can failure.