P. Lassila, J. Karvo, J. Virtamo,
Efficient Importance Sampling for Monte Carlo Simulation of Multicast Networks.
Proc. INFOCOM'01 , Anchorage, Alaska (Apr. 2001) pp. 432--439

Abstract

We consider the problem of estimating blocking probabilities in a multicast loss system via simulation, applying the static Monte Carlo method with importance sampling. An approach is introduced, where the original estimation problem is first decomposed into independent simpler sub-problems, each roughly corresponding to estimating the blocking probability contribution from a single link. Then we apply importance sampling to solve each sub-problem. The importance sampling distribution is a conditional distribution from which we can generate samples directly into the blocking state region of a single link using the so called inverse convolution method. Finally, a dynamic control algorithm is used for optimally allocating the samples between different sub-problems. The numerical results demonstrate that the variance reduction obtained with the method is truly remarkable, between 400 and 36 000 in the considered examples.

Back to publications page