Monte Carlo and Markov Chain Techniques for Network Reliability and Sampling

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.