Monte Carlo and Markov Chain techniques for network reliability and sampling
Abstract
We examine a heuristic to approximate various reliability‐related parameters of communications networks under link failures. The heuristic is based on Monte Carlo and Markov chain simulation techniques. (These techniques have emerged in recent years in theoretical computer science in the context of obtaining efficient approximations forNP‐hard combinatorial optimization problems.) We present the ideas of these Monte Carlo and Markov chain techniques in terms of a specific reliability measure. The general method could be applicable to other reliability measures, just as it has been applied to other combinatorial problems. We present initial experimental results that suggest our approach is typically efficient in the computational complexity sense (running in time polynomial the size of the input); furthermore, our results suggest practical applicability for medium‐size networks and single‐edge parameters. As an example, we present the results of our experiments on a network that was posed for analysis by Applied Research at Bellcore: We estimated all single‐edge parameters on a single DEC‐5000 in less than 4 hours. The software that supported our experiments involves approximately 3000 lines of C code and is easy to adapt to other applications.Keywords
This publication has 15 references indexed in Scilit:
- Balanced matroids1992
- On the expansion of combinatorial polytopes1992
- A random polynomial-time algorithm for approximating the volume of convex bodiesJournal of the ACM, 1991
- Approximating the PermanentSIAM Journal on Computing, 1989
- Monte-Carlo approximation algorithms for enumeration problemsJournal of Algorithms, 1989
- On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated AnnealingProbability in the Engineering and Informational Sciences, 1987
- How hard is it to marry at random? (On the approximation of the permanent)1986
- Monte-Carlo algorithms for the planar multiterminal network reliability problemJournal of Complexity, 1985
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is ConnectedSIAM Journal on Computing, 1983
- The Complexity of Enumeration and Reliability ProblemsSIAM Journal on Computing, 1979