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.
Network connectivity reliability (NCR) : NCR is a classical reliability measure adopted by most work @cite_5 @cite_21 @cite_16 . The network ! ! is modelled as a graph where links are either failed or operational, and NCR is measured by the probability that a given set of nodes are connected when links fail with given probabilities. Authors in @cite_5 take network repair policies into consideration to model link failures, and estimate NCR with the classical MC Authors in @cite_21 combine MC with the particle swarm optimization to handle the NCR problem. To improve the efficiency of MC, authors in @cite_16 apply the IS method and use pre-computed " to approximate the optimal IS estimator.
@cite_5 @cite_21 @cite_16
2017999041 2109289094 2144646757
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. 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. 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.