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.
Maximum flow reliability (MFR) : Another line of work @cite_23 @cite_6 @cite_12 generalizes the NCR problem by considering link capac-ities: link capacities are determined by link statuses, i.e., operational, failed or partially failed, which follow certain probability distributions. Given one source and one sink, MFR is defined as the probability that the maximum flow, i.e., the maximum achievable bandwidth from the source to the sink, is above a given threshold. @cite_23 , link capacities are assumed to be continuous and the MC splitting method is applied for the MFR estimation. Authors in @cite_12 follow the idea of permutating MC and assume all links fail at the beginning and each one of them gets repaired after a random time. Authors in @cite_6 consider estimating MFR with the order minimal cut sets.
@cite_12 @cite_6 @cite_23
2108858520 2501980298 2105584052
In this paper we show how the permutation Monte Carlo method, originally developed for reliability networks, can be successfully adapted for stochastic flow networks, and in particular for estimation of the probability that the maximal flow in such a network is above some fixed level, called the threshold. A stochastic flow network is defined as one, where the edges are subject to random failures. A failed edge is assumed to be erased (broken) and, thus, not able to deliver any flow. We consider two models; one where the edges fail with the same failure probability and another where they fail with different failure probabilities. For each model we construct a different algorithm for estimation of the desired probability; in the former case it is based on the well known notion of the D-spectrum and in the later one—on the permutational Monte Carlo. We discuss the convergence properties of our estimators and present supportive numerical results. Flow networks in which each component is associated with multiple capacities are known as Stochastic flow networks. These networks are prone to partial or complete failures and are often subjected to unavailability. To estimate two-terminal reliability for such stochastic flow networks several algorithms exists in literature. Most of these algorithms takes huge computational time to compute network reliability even for moderate sized networks. The known efficient cutset based stochastic flow network reliability estimation algorithm developed till date can be presented as follows (1) Maximal flows for demand d, of the network are generated using the minimal cuts and capacities of the components. (2) Removes the non-maximal flows to obtain the set of upper boundary flows for demand d. (3) Determines unreliability from the upper boundary flows from which reliability is calculated as 1-unreliability of the network. In this work, we present an algorithm that preorders the minimal cuts and calculates the network unreliability using the ordered minimal cuts. Our algorithm reduces the computational time compared to the existing algorithm. We provide an example to illustrate the proposed method. Matlab simulation is performed to compare the proposed method with the existing methods using the standard benchmark networks available in literature. Simulation results show that the proposed method takes lesser computation time and memory. We consider the problem of estimating the unreliability of a stochastic flow network, defined as the probability that the maximum flow value from a source node to a terminal node in a directed network with stochastic link capacities, is less than a specified demand level. The link capacities are assumed to be continuous random variables with a known joint distribution. We are interested in the situation where the unreliability is very small, in which case a crude Monte Carlo is not viable. We show how a Monte Carlo splitting algorithm can be adapted to handle this problem effectively.