Monte Carlo and Markov Chain Techniques for Network Reliability and Sampling
Report ID: TR-391-92Author: Mihail, Milena / Buchsbaum, Adam L.
Date: 1992-09-00
Pages: 18
Download Formats: |Postscript|
Abstract:
We outline a heuristic to approximate various reliability related parameters of communications networks under link failures. Our scheme is based on Monte Carlo and Markov chain simulation techniques. We shall present the ideas of these Monte Carlo and Markov chain techniques in terms of a specific reliability measure. However, the general method could be applicable to other reliability measures and, in fact, to other combinatorial problems. We present initial experimental results which suggest that our approach is efficient in the computational complexity sense (running time polynomial in 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.