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.
Importance sampling is one of the classical variance reduction techniques for increasing the efficiency of Monte Carlo algorithms for estimating integrals. The basic idea is to replace the original random mechanism in the simulation by a new one and at the same time modify the function being integrated. In this paper the idea is extended to problems arising in the simulation of stochastic systems. Discrete-time Markov chains, continuous-time Markov chains, and generalized semi-Markov processes are covered. Applications are given to a GI G 1 queueing problem and response surface estimation. Computation of the theoretical moments arising in importance sampling is discussed and some numerical examples given. Reliability optimization has been a popular area of research, and received significant attention due to the critical importance of reliability in various kinds of systems. Most network reliability optimization problems are only focused on solving simple structured networks (e.g., series-parallel networks) of which the reliability function can be easily obtained in advance. However, modern networks are usually very complex, and it is impossible to calculate the exact network reliability function by using traditional analytical methods in limited time. Hence, a new particle swarm optimization (PSO) based on Monte Carlo simulation (MCS), named MCS-PSO, has been proposed to solve complex network reliability optimization problems. The proposed MCS-PSO can minimize cost under reliability constraints. To the best of our knowledge, this is the first attempt to use PSO combined with MCS to solve complex network reliability problems without requiring knowledge of the reliability function in advance. Compared with previous works to solve this problem, the proposed MCS-PSO can have better efficiency by providing a better solution to the complex network reliability optimization problem. 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. 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. We propose a new Monte Carlo method, based on dynamic importance sampling, to estimate the probability that a given set of nodes is connected in a graph (or network) where each link is failed with a given probability. The method generates the link states one by one, using a sampling strategy that approximates an ideal zero-variance importance sampling scheme. The approximation is based on minimal cuts in subgraphs. In an asymptotic rare-event regime where failure probability becomes very small, we prove that the relative error of our estimator remains bounded, and even converges to 0 under additional conditions, when the unreliability of individual links converges to 0. The empirical performance of the new sampling scheme is illustrated by examples. 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. We consider network reliability in layered networks where the lower layer experiences random link failures. In layered networks, each failure at the lower layer may lead to multiple failures at the upper layer. We generalize the classical polynomial expression for network reliability to the multi-layer setting. Using random sampling techniques, we develop polynomial time approximation algorithms for the failure polynomial. Our approach gives an approximate expression for reliability as a function of the link failure probability, eliminating the need to resample for different values of the failure probability. Furthermore, it gives insight on how the routings of the logical topology on the physical topology impact network reliability. We show that maximizing the min cut of the (layered) network maximizes reliability in the low failure probability regime. Based on this observation, we develop algorithms for routing the logical topology to maximize reliability.