A New Algorithm for the Reliability Analysis of Multi-Terminal Networks

In a probabilistic network, source-to-multiple-terminal reliability (SMT reliability) is the probability that a specified vertex can reach every other vertex. This paper derives a new topological formula for the SMT reliability of probabilistic networks. The formula generates only non-cancelling terms. The non-cancelling terms in the reliability expression correspond one-to-one with the acyclic t-subgraphs of the network. An acyclic t-subgraph is an acyclic graph in which every link is in at least one spanning rooted tree of the graph. The sign to be associated with each term is easily computed by counting the vertices and links in the corresponding subgraph. Overall reliability is the probability that every vertex can reach every other vertex in the network. For an undirected network, it is shown the SMT reliability is equal to the overall reliability. The formula is general and applies to networks containing directed or undirected links. Furthermore link failures in the network can be s-dependent. An algorithm is presented for generating all acyclic t-subgraphs and computing the reliability of the network. The reliability expression is obtained in symbolic factored form.     

Factoring and reductions for networks with imperfect vertices

Factoring and reductions are effective methods for computing the K-terminal reliability of undirected networks, but they have been applied mostly to networks with perfect vertices. However, in real problems, vertices may fail as well as edges. Imperfect vertices can be factored like edges, but the complexity then increases exponentially with their number. A technique has been developed to account for the failure of vertices with small additional cost, using a modified method of factoring and reductions. This technique is very easy to integrate into a factoring algorithm. It consists of factoring not on a single element (e.g., a single edge) but on a set of elements (e.g., an edge and its endpoints). The problem is that random variables associated with the elements of the network are no longer independent. This can be handled by choosing factoring edges that have at least one perfect endpoint. This technique leaves the factoring algorithm practically unchanged. The only difference is that some supplementary probability values are kept for the imperfect vertices of the original and the induced graphs. For algorithms using simple reductions, it has negligible computational cost     

利用因子分解方法计算网络的根通信可靠性

本文使用因子分解(factoring)的方法计算网络的根通信可靠性(存在从根点到每一个其它结点正常运行道路的概率)。我们充分利用无圈有向网络的拓扑结构提出了两个新的可靠性保护缩减(Reliability-Preserving Reduction)和一个进行因子分解的选边规则。在此基础上,给出一个因子分解算法(factoring algorithm)。对于不是非常稠密的网络,该算法是非常有效的。     

A practical implementation of the factoring theorem for networkreliability

The factoring theorem is a simple tool for determining the K -terminal reliability of a network, i.e. the probability that a given set K of terminals in the network are connected to each other by a path of working edges. An implementation of an algorithm which uses the factoring theorem, in conjunction with degree-1 and degree-2 vertex reductions, to determine the reliability of a network is presented. Networks treated have completely reliable nodes and have edges which fail statistically and independently with known probabilities. The reliability problem is to determine the probability that all nodes in a designated set of nodes can communicate with each other. Such an implementation of the factoring theorem can be incorporated in a small, stand-alone program of about 500 lines of code. A program of this type requires little computer memory and is ideally suited for microcomputer use     

Reliability of directed networks using the factoring theorem

The authors present a framework in which the factoring theorem can be used in conjunction with other network reductions and simplifications to determine the reliability of source-to-sink communication in a directed network. On published test networks, the proposed microcomputer implementation of this framework solves the two-terminal reliability problem substantially faster than existing implementations of other current algorithms     

K-Terminal Network Reliability Measures With Binary Decision Diagrams

We present a network decomposition method using binary decision diagrams (BDD), a state-of-the-art data structure to encode, and manipulate Boolean functions, for computing the reliability of networks such as computer, communication, or power networks. We consider the K-terminal reliability measure R_K, which is defined as the probability that a subset K of nodes can communicate with each other, taking into account the possible failures of the network links. We present an exact algorithm for computing the if-terminal reliability of a network with perfect vertices in O(m^.F_max ^.2^Fmax.B_Fmax), where B_Fmax is the Bell number of the maximum boundary set of vertices F_max, and m is the number of network links. Several examples, and experiments show the effectiveness of this approach.     

Performance of sufficient conditions for distributed quality-of-service support in wireless networks

Given a wireless network where some pairs of communication links interfere with each other, we study sufficient conditions for determining whether a given set of minimum bandwidth quality-of-service requirements can be satisfied. We are especially interested in algorithms which have low communication overhead and low processing complexity. The interference in the network is modeled using a conflict graph whose vertices correspond to the communication links in the network. Two links are adjacent in this graph if and only if they interfere with each other due to being in the same vicinity and hence cannot be simultaneously active. The problem of scheduling the transmission of the various links is then essentially a fractional, weighted vertex coloring problem, for which upper bounds on the fractional chromatic number are sought using only localized information. We recall some distributed algorithms for this problem, and then assess their worst-case performance. Our results on this fundamental problem imply that for some well known classes of networks and interference models, the performance of these distributed algorithms is within a bounded factor away from that of an optimal, centralized algorithm. The performance bounds are simple expressions in terms of graph invariants. It is seen that the induced star number of a network plays an important role in the design and performance of such networks.     

Terminal-pair reliability of network system using flow augmenting path search algorithm

This paper considers a network reliability problem as a special type of flow problem and presents an algorithm to evaluate the exact 2-terminal reliability of networks on the basis of the factoring theorem and a backtracking technique. It employs a polygon-to-chain reduction in addition to series and parallel reduction techniques to reduce execution time. In comparisons, it presents a better performance than other existing algorithms.     

Factoring Algorithms for Computing K-Terminal Network Reliability

Let GK denote a graph G whose edges can fail and with a set K ? V specified. Edge failures are independent and have known probabilities. The K-terminal reliability of GK, R(GK), is the probability that all vertices in K are connected by working edges. A factoring algorithm for computing network reliability recursively applies the formula R(GK) = piR(GK * ei) + qiR(GK - ei) where GK * ei is GK, with edge ei contracted, GK - ei is GK with ei deleted and pi ? 1 - qi is the reliability of edge ei. Various reliability-preserving reductions can be performed after each factoring operation in order to reduce computation. A unified framework is provided for complexity analysis and for determining optimal factoring strategies. Recent results are reviewed and extended within this framework.     

K终端可靠度分解算法中多边形→链简化定理的完善

无向网络K终端可靠度的分解算法中,包括多边形→链简化在内的等可靠度简化和分解定理结合,可以降低算法的复杂度。本文完善了边随机无向网络和混合随机无向网络的4#,6#,7#型多边形→链简化定理。计算机编程验证了其正确性。     

Maximizing the Mean Number of Communicating Vertex Pairs in Series-Parallel Networks

A communication network can be modelled as a probabilistic graph where each of b edges represents a communication line and each of n vertices represents a communication processor. Each edge e (vertex v) functions with probability Pe (pv). If edges fail independently with uniform probability p and vertices do not fail, the probability that the network is connected is the probabilistic connectedness and is a standard measure of network reliability. The most reliable maximal series-parallel networks by this measure are those with exactly two vertices of degree two. However, as p becomes small, or n becomes large, the probability that even the most reliable series-parallel network is connected falls very quickly. Therefore, we wish to optimize a network with respect to another reliability measure, mean number of communicating vertex pairs. Experimental results suggest that this measure varies with p, with the diameter of the network, and with the number of minimum edge cutsets. We show that for large p, the most reliable series-parallel network must have the fewest minimum edge cutsets and for small p, the most reliable network must have maximum pairs of adjacent edges. We present a construction which incrementally inproves the communicating vertex pair mean for many networks and demonstrates that a fan maximizes this measure over maximal series parallel networks with exactly two edge cutsets of size two.     

Adaptive reliability satisfaction in wireless sensor networks through controlling the number of active routing paths

The number of active paths in multipath routing scenarios (with concurrent data transmission over the established paths) affects the provided reliability degree as well as the imposed overhead of path management. Since the reliability of individual links varies over the time, adaptively setting the sufficient number of active paths turns out to be essential. In this paper, we first propose a Reliability Estimation for WSNs (RE-WSNs) algorithm, based on ordered binary decision diagram (OBDD) data structure, which gives the network reliability in terms of the reliability of all individual links. Second, we propose a novel algorithm called adaptive reliability satisfaction–multipath routing (ARS–MR) which adaptively sets the sufficient number of active paths, aiming at keeping the network reliability within a desired quantitative range and minimizing path management overhead. In activation/inactivation process it further takes into account energy efficiency considerations. The proposed ARS–MR algorithm can be used in conjunction with any arbitrary multipath algorithm in WSNs. Simulation results with NS-2 reveal that ARS–MR is quite successful in timely reacting to variations of links reliability. Indeed, it manages the number of active paths and keeps the reliability of the network satisfactory over the course of network lifetime.     

Dynamic recovery for survivable virtual network embedding

Network virtualization is a promising way to overcome the current ossification of the Intemet. It is essential challenge to find effective, efficient and robust embedding algorithms for recovering virtual network. The virtual network mapping algorithm based on integer programming which was proposed months ago. But it did consider the faults of physical network resources, which is so called survivable virtual network embedding （VNE） problem. Previous strategies for enabling survivability in network virtualization focused on providing protection for the physical network or enhancing the virtual networks by providing backup physical resources in advance, and treated all the physical failures as link failures. In the article, a dynamic recovery method is proposed to solve the survivable virtual network embedding problem based on the integer programming VNE algorithm. The dynamic recovery method doesn＇t need to backup physical resources and it makes more substrate resources which can be used in the embedding. The dynamic recovery process will be activated only when physical failures occur. Different algorithms are used to recovery node and link failures. Simulations show that the method helps to recover almost all of physical failures by finding the substitute nodes and paths, and its performance is very close to that of pure VNE method without considering physical failures.     

Multi‐hour design of survivable classical IP networks

Most of Internet intra‐domain routing protocols (OSPF, RIP, and IS–IS) are based on shortest path routing. The path length is defined as the sum of metrics associated with the path links. These metrics are often managed by the network administrator. In this context, the design of an Internet backbone network consists in dimensioning the network (routers and transmission links) and establishing the metric. Many requirements have to be satisfied. First, Internet traffic is not static as significant variations can be observed during the day. Second, many failures can occur (cable cuts, hardware failures, software failures, etc.). In this paper, we present algorithms (meta‐heuristics and greedy heuristic) to design Internet backbone networks, taking into account the multi‐hour behaviour of traffic and some survivability requirements. Many multi‐hour and protection strategies are studied and numerically compared in this paper. Our algorithms can be extended to integrate other quality of service constraints. Copyright © 2002 John Wiley & Sons, Ltd.     

Reliability evaluation for distributed computing networks withimperfect nodes

This paper examines two compensating methods that: (1) account for imperfect nodes, and (2) can be embedded in most symbolic network reliability algorithms that presume perfect nodes. The Aggarwal method can be exponential in time with the number of links, whereas the Torrieri method is always linear. However the Torrieri method can yield incorrect results for some undirected networks. This paper points out such incorrectness and then proposes an efficient reliability evaluation algorithm (ENR/KW) accounting for imperfect nodes in distributed computing networks. Based on the concept of network partition, ENR/KW exploits some simple efficient techniques to handle the unreliable nodes, for directly computing the network reliability expression considering imperfect nodes instead of using any compensating method. The basic idea of ENR/KW is to partition the network directly into a set of smaller disjoint subnetworks by only considering link elements as if all nodes are perfect. Each disjoint subnetwork is generated by maintaining a specific directed graph structure to consider the effect of imperfect nodes. Therefore, the reliability expression for imperfect nodes can be obtained directly from the disjoint subnetwork and the specific directed graph. ENR/KW can be generalized to evaluate various network reliability measures considering imperfect nodes such as terminal-pair reliability, K-terminal reliability, and distributed-program reliability. Many experiments for evaluating the terminal-pair reliability and distributed-program reliability were performed on a SUN workstation to show the efficiency of ENR/KW in terms of the number of generated subnetworks and overall computation time     

Optimized priority based energy efficient routing algorithm for mobile ad hoc networks

Recently more and more research interest focuses on the energy efficient routing in mobile ad hoc networks and many related routing algorithms are reported. In this paper, a new optimized priority based energy efficient routing algorithm is presented and priority is added to the existing routing algorithm according to the residual energy proportion of the nodes. Lower residual energy means lower priority and the nodes with lower priority are less likely to forward packets to other nodes. The algorithm needs no global information of the networks and only a little modification is needed to the existing algorithm, so it is practical to be implemented. The algorithm can improve the performance of routing discovery, routing maintenance and cache management at the same time. Some optimization strategy is taken to reduce the network overhead and the lifetime of the network is much longer and the network with our algorithm can transfer much more effective data. Simulation with NS-2 is done and satisfying results are obtained with this algorithm. The results show that the algorithm is efficient.     

Hypermedia and network reliability

A simple algorithm utilizing the factoring theorem and other elementary network reductions is available to determine network reliability in a number of different forms. This paper describes a computer-based implementation of such an algorithm housed in a hypermedia environment. The environment can provide for both the formulation and the solution of reliability problems. In our treatment the user draws the network interactively on the computer screen and clicks an on-screen button to perform the reliability analysis. This provides an alternative to manual calculations that become tedious or impossible with networks which are neither series-parallel nor extremely small.     

Evaluation of system reliability with common-cause failures, by apseudo-environments model

An efficient method for calculating system reliability with CCFs (common-cause failures) is presented by applying the factoring (total probability) theorem when the system and its associated class of CCFs are both arbitrary. Existing methods apply this theorem recursively until no CCF remains to be considered, and so can be time-consuming in computation. The method applies such a theorem only once and can be carried out in two steps: (1) determine each state in terms of the occurrence (or not) of every CCF in the associated class, to regard it as a pseudo-environment and to calculate its probability or weight; (2) determine each resulting subsystem of the system under the environment, calculate its reliability as in the no CCF case and take the weighted sum of such reliabilities, viz, the system reliability. This method is in terms of a Markov process and requires only the occurrence rate of each CCF to obtain the probability of each environment and only the failure rate of each component to obtain the system reliability under each environment; hence, it is practical, efficient, and useful     

High-reliability topological architectures for networks under stress

In this paper, we consider the design of a physical network topology that meets a high level of reliability using unreliable network elements. We are motivated by the use of networks and, in particular, all-optical networks, for high-reliability applications which involve unusual and catastrophic stresses. Our network model is one in which nodes are invulnerable and links are subject to failure - a good approximation for optical networks with passive nodes and vulnerable fiber under stress of disconnection - and we focus on statistically independent link failures with initial steps taken toward generalization to dependent link failures. Our reliability metrics are the all-terminal connectedness measure and the less commonly considered two-terminal connectedness measure. We compare in the low and high stress regimes, via analytical approximations and simulations, common commercial architectures designed for all-terminal reliability when links are very reliable with alternative architectures which are mindful of both of our reliability metrics and regimes of stress. We derive new results especially for one of these alternative architectures, Harary graphs, which have been shown to possess attractive reliability properties. Furthermore, we show that for independent link failures network design should be optimized with respect to reliability under high stress, as reliability under low stress is less sensitive to graph structure; and that under high stress, very high node degrees and small network diameters are required to achieve moderate reliability performance. Finally, in our discussion of correlated failure models, we show the danger in relying on an independent failure model and the need for the network architect to minimize component failure dependencies.