55035418
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.
122217418
The Combinatorics of Network Reliability
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.
62475917
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.
62647882
Algorithms for network reliability and connection availability analysis
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>>
17952879
On pairwise connectivity of wireless multihop networks
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.
11597648
Exact bounds for average pairwise network reliability
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.
125650500
Diameter constrained network reliability :exact evaluation by factorization and bounds
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.
5500317
Cumulative Update of All-Terminal Reliability for Faster Feasibility Decision
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.
7202748
Triconnected decomposition for computing K-terminal network reliability
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.
503187
Cumulative estimated values of structural network's reliability indices and their usage
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.
45750854
Network Probabilistic Connectivity: Exact Calculation with Use of Chains
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.
206772980
Improvements in the Efficiency of Cumulative Updating of All-Terminal Network Reliability
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.
8767776
Network Probabilistic Connectivity: Using Node Cuts
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.
6418098
Factorization of network reliability with perfect nodes I: Introduction and statements
A new general all terminal network reliability factorization theorem is stated. We relegate the proof to a forthcoming second part paper.
32325201
Factorization of network reliability with perfect nodes II: Connectivity matrix
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.
3759261
The Complexity of Enumeration and Reliability Problems
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.
45124634
Methods of Speeding up of Diameter Constrained Network Reliability Calculation
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.
14235847
Decomposing graph with 2-node cuts for diameter constrained network reliability calculation
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.
11217268
Network Probabilistic Connectivity: Expectation of a Number of Disconnected Pairs of Nodes
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.
31371468
On the Expected Value of a Number of Disconnected Pairs of Nodes in Unreliable Network
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.