Monte Carlo and Markov chain techniques for network reliability and sampling
Adam L. Buchsbaum, Milena Mihail · DIMACS series in discrete mathematics and theoretical computer science · 1994
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 for NP-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.