This paper focuses on helping network providers to carry out network capacity planning and sales projection by answering the question: For a given topology and capacity, whether the network can serve current flow demands with high probabilities? We name such probability as “ flow availability” and present the -flow availability estimation (FAVE) problem, which is a generalisation of network connectivity or maximum flow reliability estimations. Realistic networks are often large and dynamic, so flow availabilities cannot be evaluated analytically and simulation is often used. However, naive Monte Carlo (MC) or importance sampling (IS) techniques take an excessive amount of time. To quickly estimate flow availabilities, we utilize the correlations among link and flow failures to figure out the importance of roles played by different links in flow failures, and design three “sequential importance sampling” (SIS) methods which achieve “bounded or even vanishing relative error” with linear computational complexities. When applying to a realistic network, our method reduces the flow availability estimation cost by 900 and 130 times compared with MC and baseline IS methods, respectively. Our method can also facilitate capacity planning by providing better flow availability guarantees, compared with traditional methods.
The most relevant literatures to our work focus on evaluating network reliability . To design reliable networks, one needs to measure the impact of network failures (e.g., link failures) on network performances @cite_15 . It is known that the exact computation of network reliability is #P-complete, and computational complexities of all known algorithms are exponential increasing with the graph scale @cite_17 , which makes the problem intractable even for medium sized networks. Hence, most work on network reliability evaluation considers sampling methods to provide reliability estimations, and they can be classified into ! network connectivity " based and maximum flow " based.
@cite_15 @cite_17
2017999041 1991536882 1975407578 1998076865
Reliability and availability have always been important characteristics of systems but become even more critical and complex issues on networks. Due to the high complexity of accurate calculation methods, simulation methods for network reliability and availability evaluation have been a popular area of research, and received significant attention. In this paper the network topology model, the failure driven simulation method and the reliability and availability statistical algorithms are put forward, and then the network reliability and availability simulation flow based on the Monte Carlo method was designed. This simulation method can be used to calculate the reliability and availability of a network whose nodes and links may be failure. Two repair policies, immediate repair and delay repair, are provided to choose. Finally, the backbone of CERNET (China Education and Research Network) is taken as an example and the simulation results are analyzed. This paper presents an overview of results related to the computational complexity of network reliability analysis problems. Network reliability analysis problems deal with the determination of reliability measures for stochastic networks. We show how these problems are related to the more familiar computational network problems of recognizing certain subnetworks, finding optimal subnetworks, and counting certain subnetworks. We use these relationships to show that the k-terminal, the 2-terminal, and the all-terminal network reliability analysis problems are at least as hard as the renowned set of computationally difficult problems, NP-Complete. Finally, we discuss the impact of these results on how one should approach problem solving in this area. The classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability. The goal is to determine the probability that the network becomes disconnected due to edge failures. This problem has obvious applications in the design of communication networks. Since the problem is @math -complete and thus believed hard to solve exactly, a great deal of research has been devoted to estimating the failure probability. In this paper, we give a fully polynomial randomized approximation scheme that, given any n-vertex graph with specified failure probabilities, computes in time polynomial in n and @math an estimate for the failure probability that is accurate to within a relative error of @math with high probability. We also give a deterministic polynomial approximation scheme for the case of small failure probabilities. Some extensions to evaluating probabilities of @math -connectivity, strong connectivity in directed Eulerian graphs and @math -way disconnection, and to evaluating the Tutte polynomial are also described. This version of the paper corrects several errata that appeared in the previous journal publication [D. R. Karger, SIAM J. Comput., 29 (1999), pp. 492--514]. Several enumeration and reliability problems are shown to be # P-complete, and hence, at least as hard as NP-complete problems. Included are important problems in network reliability analysis, namely, computing the probability that a graph is connected and counting the number of minimum cardinality @math -cuts or directed network cuts. Also shown to be # P-complete are counting vertex covers in a bipartite graph, counting antichains in a partial order, and approximating the probability that a graph is connected and the probability that a pair of vertices is connected.