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.
Communications networks used for transmitting and receiving voice or digital data involve copper wire, fiber optics, radio, satellite, and microwave links. In general, these networks are large, diffuse, and complex. Even using modern high-speed computers, exact computations of the network reliability for use as a figure of merit in an interactive network design procedure can take an inordinate amount of time. This paper discusses various exact techniques whose complexity results in run-times short enough for practical network design. We model the network by an undirected probabilistic graph whose vertices represent the nodes and whose edges represent the links. A special feature of our model is that it allows nodes to be imperfect and associates a reliability measure with each node, assumed to succeed or fail independently. Therefore, the network reliability measure is based upon the reliability measures of the individual links and nodes. > A fast simulation technique based on importance sampling is developed for the analysis of path service availability in mesh networks with dynamic path restoration. The method combines the simulation of the path rerouting algorithm with a "dynamic path failure importance sampling" (DPFS) scheme to estimate path availabilities efficiently. In DPFS, the failure rates of network elements are biased at increased rates until path failures are observed under rerouting. The simulated model uses "failure equivalence groups," with finite infinite sources of failure events and finite infinite pools of repair personnel, to facilitate the modeling of bidirectional link failures, multiple in-series link cuts, optical amplifier failures along links, node failures, and more general geographically distributed failure scenarios. The analysis of a large mesh network example demonstrates the practicality of the technique.