FoCM 2014 conference
Workshop A4 - Graph Theory and Combinatorics
No date set
Methods for reliability analysis of diameter constrained networks
Denis Migov
Institute of Computational Mathematics and Mathematical Geophysics of SB RAS, Russia - mdinka@rav.sscc.ru
Networks where the edges are a subject to random failures are studied in the present article. As a rule networks with unreliable elements are modeled by a probabilistic graph in which an operational probability is associated with every element (a node or an edge). The most common reliability measure of such networks is the probability that all the terminal nodes in a network can keep connected together, given the reliability of each network node and edge. The analysis of the network reliability has been a subject of considerable research [1, 2, 3]. Today we have a lot of different methods for network reliability calculation and evaluation. These methods may be useful during network topology design and optimization.
In practice it often needs not only the existence of a path between each pair of nodes, but the existence of a path passing via a limited number of communication links. Thus, we arrive to a different reliability measure. The diameter constrained network reliability (DCNR) is a probability that every two nodes from a given set of terminals are connected with a path of length less or equal to a given integer. By the length of a path we understand the number of edges in this path.
This reliability measure was introduced in [4] and studied in more detail in [5, 6]. The problem of computing this measure in general is known to be NP-hard, just like the problem of computing the probability of network connectivity. Now the complexity of DCNR calculation is completely studied [6].
The new approach in reliability calculation (without diameter constraint) was introduced in [2]: cumulative update of lower and upper bounds of network reliability for faster feasibility decision. This method allows to decide the feasibility of a given network without performing exhaustive calculation. The approach was further developed with the help of network decomposition [3]. We propose the method for cumulative updating of lower and upper bounds of diameter constrained network reliability. This method allows us to make a decision about the network reliability (or unreliability) with diameter constraint with respect to a given threshold without performing the exhaustive calculation.
One of the main reasons, which make the calculation of diameter constrained network reliability much more complicated in comparison with other network reliability measures, is the lack of methods of recursion quantity decrease. For example, for k-terminal network reliability calculation we may use a lot of network reduction and decomposition methods. We propose to use the decomposition methods and some other techniques for DCNR calculation. Let us demonstrate one of these methods.
Suppose that graph $G$ includes cutnode $x$ dividing the graph in two $G_1$ and $G_2$ subgraphs. Let us consider 2-terminal case. Let terminals $s$ and $t$ belong to $G_1$ and $G_2$ respectively and none of them is $x$. DNCR is defined as the probability that nodes $s$ and $t$ are connected with diameter constrain $d$ in a graph $G$. We denote it by $ R_{s, t} ^d(G) $. By $R_{s,t}^{\overline{d}}(G)$ we denote a probability that nodes $s$ and $t$ are connected in $G$ and a length of shortest path between them is equal to $d$. By $d_i$ we denote the distance between $s$ and $x$ or $y$ in subgraph $G_i$. We obtained how $R_{s,t}^d(G)$ is expressed in terms of $R_{s, x}^i(G_1)$, $ R_{s, x}^{\overline{i}}(G_1)$, $R_{x,t}^i(G_2)$, and $R_{x, t}^{\overline{i}}(G_2)$: \begin{equation} R^{d}_{s,t}(G)=\sum^{d-d_2}_{i=d_1}R^{\overline{i}}_{s,x}(G_1)R^{d-i}_{x,t}(G_2) \label{ArtFormula} =\sum^{d-d_1}_{i=d_2}R^{d-i}_{s,x}(G_1)R^{\overline{i}}_{x,t}(G_2). \end{equation}
Also we obtained some other effective techniques for DCNR calculation, including the formula that lets performing decomposition for the computation of diameter constrained 2-terminal reliability of a network that contains 2-node cuts. While the calculation of DCNR known to be a NP-hard problem, the proposed methods allow to considerably reduce the calculation time.
This work was supported by Russian Foundation for Basic Research under Grant 14-07-31069 and by Novosibirsk city administration under Grant 39-14.
References
1. Ball M.O. Computational complexity of network reliability analysis: An overview // IEEE Transactions on Reliability. Vol. 35, 1986, p. 230-239.
2. Won J.-M., Karray F. Cumulative Update of All-Terminal Reliability for Faster Feasibility Decision // IEEE Transactions on Reliability. Vol. 59, issue 3, 2010, 551-562.
3. Rodionov A.S., Migov D.A., Rodionova O.K. Improvements in the Efficiency of Cumulative Updating of All-Terminal Network Reliability // IEEE Transactions on Reliability. Vol. 61, issue 2, 2012, p. 460-465.
4. Cancela H., Petingi L. Diameter Constrained Network Reliability: Exact Evaluation by Factorization and Bounds // Proc. Int. Conf. on Industrial Logistics. Japan, 2001, p. 359-356.
5. Migov D.A. Computing Diameter Constrained Reliability of a Network with Junction Points // Automation and Remote Control. Vol. 72, issue 7, 2011, p. 1415-1419.
6. Eduardo Canale, Hector Cancela, Franco Robledo, Gerardo Rubino and Pablo Sartor. On Computing the 2-diameter-constrained K-reliability of Networks // International Transactions in Operational Research. Vol. 20, issue 1, January 2013, p. 49-58.