Obtaining and Using Cumulative Bounds of Network Reliability

In this chapter, we study the task of obtaining and using the exact cumulative bounds of various network reliability indices. A network is modeled by a non-directed random graph with reliable nodes and unreliable edges that fail independently. The approach based on cumulative updating of the network reliability bounds was introduced byWon and Karray in 2010. Using this method, we can find out whether the network is reliable enough with respect to a given threshold. The cumulative updating continues until either the lower reliability bound becomes greater than the threshold or the threshold becomes greater than the upper reliability bound. In the first case, we decide that a network is reliable enough; in the second case, we decide that a network is unreliable. We show how to speed up cumulative bounds obtaining by using partial sums and how to update bounds when applying different methods of reduction and decomposition. Various reliability indices are considered: k-terminal probabilistic connectivity, diameter constrained reliability, average pairwise connectivity, and the expected size of a subnetwork that contains a special node. Expected values can be used for unambiguous decision-making about network reliability, development of evolutionary algorithms for network topology optimization, and obtaining approximate reliability values.

Related papers:

title: The Combinatorics of Network Reliability
abstract: Preliminaries Exact algorithms The computational complexity of reliability problems Exact algorithms for restricted classes The reliability polynominal Edge-disjoint subgraphs Additive and multiplicative improvements Combining the bounds The k-cycle bound Computational results References Index.

title: Reliable Circuits Using Less Reliable Relays
abstract: An investigation is made of relays whose reliability can be described in simple terms by means of probabilities. It is shown that by using a sufficiently large number of these relays in the proper manner, circuits can be built which are arbitrarily reliable, regardless of how unreliable the original relays are. Various properties of these circuits are elucidated.

title: Algorithms for network reliability and connection availability analysis
abstract: Communications networks used for transmitting and receiving voice or digital data involve copper wire, fiber optics, radio, satellite, and microwave links. In general, these networks are large, diffuse, and complex. Even using modern high-speed computers, exact computations of the network reliability for use as a figure of merit in an interactive network design procedure can take an inordinate amount of time. This paper discusses various exact techniques whose complexity results in run-times short enough for practical network design. We model the network by an undirected probabilistic graph whose vertices represent the nodes and whose edges represent the links. A special feature of our model is that it allows nodes to be imperfect and associates a reliability measure with each node, assumed to succeed or fail independently. Therefore, the network reliability measure is based upon the reliability measures of the individual links and nodes.<<ETX>>

title: On pairwise connectivity of wireless multihop networks
abstract: This paper experimentally investigates the service availability of wireless multihop networks based on the following two metrics: Average Pairwise Connectivity (APC) and Pairwise Connected Ratio (PCR), where the former denotes the average number of node-disjoint paths per node pair and the latter is the fraction of node pairs that are pairwise connected. A theoretical upperbound are derived for APC, which can approximate the exact value very well. We also studied the fault tolerance and attack resilience and proposed a new resilience metric, α-ρ-resilience, where a network is α-ρ-resilient if at least a portion of nodes pairs remain connected as long as no more than p percentage nodes are removed. Three different node removal patterns are studied: random removal, selective removal and partition. The experimental studies show that wireless multihop networks are more sensitive to partition and selective removal attacks are a little bit more severe than random removal attacks.

title: Exact bounds for average pairwise network reliability
abstract: Several methods for finding exact bounds of average pairwise network connectivity (APNC) are proposed. These methods allows faster decision making about if a network is reliable for its purpose. Previous results on cumulitive updating of all-terminal probabilistic connectivity and exact algorithms for calculating average number of disconnected pairs of nodes in a random graph are used as a base for most of presented results.

title: Diameter constrained network reliability :exact evaluation by factorization and bounds
abstract: Consider a network where the links are subject to random, independent failures. The diameter constrained network reliability parameter R(G,K,D) measures the probability that the set K of terminals of the network are linked by operational paths of length less or equal to D. This parameter generalizes the classical network reliability, allowing to reflect performance objectives that restrict the maximum length of a path in the network. This is the case, for example, when the transmissions between every two terminal nodes in the subset K are required to experience a maximum delay D.T (where T is the delay experienced at a single node or link); then the probability that after random failures of the communication links, the surviving network meets the maximum delay requirement is the diameter constrained reliability R(G,K,D). This paper defines the diameter constrained network reliability, and gives a formulation in terms of events corresponding to the operation of the (length constrained) paths of the network. Based on this formulation, the exact value of the diameter constrained reliability is derived, for the special case where K={s,t} and the upper bound D of the path length is 2. For other values of K and D an exact evaluation algorithm based on a factorization approach is proposed. As this algorithm has exponential worst case complexity, upper and lower bounds for K={s,t} are developed, which in some cases may be used instead of the exact value.

title: Cumulative Update of All-Terminal Reliability for Faster Feasibility Decision
abstract: Designing a reliable network becomes a time-consuming task if it involves All-Terminal Reliability (ATR) calculation, which belongs to the class of NP-hard problems. To make this task easier to address, we propose a new algorithm to decide the ATR feasibility of a given network G without performing exhaustive calculation. The proposed algorithm cumulatively updates the lower and upper bounds of the ATR using the set of subnetworks decomposed or branched from G. Once the lower or upper bound reaches the predetermined ATR requirement, the feasibility of G is determined. The proposed algorithm is characterized by four existing ATR calculation methods, which decompose or branch G into multiple subnetworks. The four implementations of the proposed algorithm will be tested via computer experiments. The results show that the proposed algorithm can make feasibility decision dramatically faster. The arrangement of subnetworks that can improve the performance of the proposed algorithm is also discussed.

title: Triconnected decomposition for computing K-terminal network reliability
abstract: Let R(Gk) denote the probability that a subset of vertices K in the undirected graph G = (V, E) can communicate when the edge of G fail independently with known probabilities. Suppose that Gk contains as separting pair of vertices {u, v} such that Gk= Gk ∪ Ǧǩ, Ṽ ∩ V ={u v}, Ẽ ∩ E = o, |Ẽ| ⩾ 2, and |E| ⩾2. It is shown that Ĝk may be replaced by a chain χ of at most three edges between u and v such that R(Gk) = ΩR ((G ∪ χ)k′) where Ω is a derived constant and K′ is defined by the procedure. The failure probabilities of the edges in χ and the value of Ω are shown to be computable by evaluating the reliability of one of four variants of Ĝk. Minimal components Ĝk can be efficiently found using triconnected decomposition and the above procedure embedded within a recursive factoring algorithm for computing K-terminal reliability. Conditions are derived which guarantee the new algorithm is at least as good as a pure factoring algorithm, and an example shows that the new algorithm can be exponentially better.

title: Cumulative estimated values of structural network's reliability indices and their usage
abstract: Tasks of obtaining and usage of exact cumulative expected values of some indecies of a network's structural reliability, such as k-terminal probabilistic connectivity, average pairwise connectivity and expected size of a subnetwork that contains some special node are considered in the paper. Random non-oriented random graph with reliable nodes and unreliable edges that fails independently is used as a model of a network. At the same time the proposed approach can be used in the case of unreliable nodes also. The factoring method, exhaustive search, methods of reduction and decomposition are used as a base. Expected values are used for unambiguous decision making about network's reliability, designing evolutionary algorithms for structural optimization and obtaining approximate expected values that are more precious than cumulative ones obtained to the moment.

title: Network Probabilistic Connectivity: Exact Calculation with Use of Chains
abstract: The algorithmic techniques which allow high efficiency in the precise calculation of the reliability of an undirected graph with absolutely reliable nodes and unreliable edges are considered in this paper. The new variant of the branching algorithm that allow branching by chains is presented along with improvement of series-parallel reduction method that permits the reduction of a chain with more than two edges by one step. Some programming techniques which accomplish high efficiency are also discussed. Special notice is given to the problem of computer storage economy. Comprehensive computer simulation results show the advantages of the proposed algorithms, that the calculation time decreases significantly in comparison with existent methods.

title: Improvements in the Efficiency of Cumulative Updating of All-Terminal Network Reliability
abstract: This paper contains some algorithms and recommendations that enable increasing efficiency of cumulative updating of all-terminal reliability for a network with unreliable links. The existence of cutnodes, 2-node cuts, and chains in a network structure can be used for faster calculations.

title: Network Probabilistic Connectivity: Using Node Cuts
abstract: The new algorithmic technique which allow higher efficiency in the precise calculation of the reliability of an undirected graph with absolutely reliable nodes and unreliable edges is considered in this paper. As graph’s reliability we mean its probabilistic connectivity. The proposed technique is based on the reduction of the dimension of a calculated graph by considering its node’s cuts. Comprehensive computer simulation results show the advantages of the proposed algorithms, that the calculation time decreases significantly in comparison with existent methods.

title: Factorization of network reliability with perfect nodes I: Introduction and statements
abstract: A new general all terminal network reliability factorization theorem is stated. We relegate the proof to a forthcoming second part paper.

title: Factorization of network reliability with perfect nodes II: Connectivity matrix
abstract: We prove the determinant connectivity matrix formula. Mathematically, the proof introduces novel techniques based on an algebraic approach and connectivity properties. Although this is the second part of a previous paper and has its original motivation there, the paper is self contained and the result is interesting in itself.

title: The Complexity of Enumeration and Reliability Problems
abstract: The class of $# P$-complete problems is a class of computationally eqivalent counting problems (defined by the author in a previous paper) that are at least as difficult as the $NP$-complete problems. Here we show, for a large number of natural counting problems for which there was no previous indication of intractability, that they belong to this class. The technique used is that of polynomial time reduction with oracles via translations that are of algebraic or arithmetic nature.

title: Methods of Speeding up of Diameter Constrained Network Reliability Calculation
abstract: We consider the problem of reliability calculation of networks with diameter constraint. It is assumed that the network has unreliable communication links and perfectly reliable nodes. The diameter constrained reliability (DCNR) for such network is defined as a probability that every pair of terminals of network is connected by operational paths with a number of included edges less or equal to a given integer. The problem of computing this characteristic is known to be NP-hard, just like the problem of computing the probability of network connectivity. We propose new methods of speeding up of DCNR calculation. These methods are the edge reduction and the edge selection strategy for DCNR computing by the well-known factoring method. Also, we propose the parallel method for DCNR calculation and the method of cumulative updating of lower and upper bounds of DCNR, which allows to decide the feasibility of a network with respect to given threshold without performing exhaustive calculation of reliability. Experiments show an applicability of proposed methods.

title: Decomposing graph with 2-node cuts for diameter constrained network reliability calculation
abstract: We consider a network with unreliable communication channels and perfectly reliable nodes. The diameter constrained reliability for such a network is defined as a probability that a set of terminals of a network are linked by operational paths with number of included edges less or equal to given integer. The problem of computing this characteristic is known to be NP-hard, just like the problem of computing the probability of a network connectivity. We propose a new method that allows using node cuts to compute the reliability of a two-terminal network with diameter constraints, which makes the computations faster.

title: Network Probabilistic Connectivity: Expectation of a Number of Disconnected Pairs of Nodes
abstract: The task of calculating the expectation of a number of disconnected pairs of nodes (EDP) in unreliable network is discussed. The task is NP-hard that is it requires complete enumeration of subgraphs. The techniques for decreasing a number of enumerated subgraphs by using the branching (factoring) method and taking advantage from possible structural features are discussed. Usage of chains, bridges, cutnodes and dangling nodes is considered.

title: On the Expected Value of a Number of Disconnected Pairs of Nodes in Unreliable Network
abstract: The task of calculating the expectation of a number of disconnected pairs of nodes (EDP) in unreliable network is discussed. The task is NP-hard, that is it requires exhaustive search of subgraphs. The techniques for decreasing a number of enumerated subgraphs by using the branching (factoring) method and taking advantage from possible structural features are discussed. Usage of chains for reduction of the task dimension is considered.