Statistical optimization of dynamic importance sampling parameters for efficient simulation of communication networks

Abstract

AbstMct-Importance sampling (IS) is recogsdsed as a potentially powerftd method for reducing simulation run times when estimating the probabilittea of rare events in communication systems using Monte Carlo simulation. Of special inteswat is the probability of buffer overflow in networks of queues. When simulating networks of queu~ regenerative techniques make the applkmtkm of IS feasible and efBcient. The applkation of regenerative techsdquea is also crucial in obtahdng correct confidence intervals for the estimates involved. However, using the moat favorable IS settings very often makes the length of regeneration cycles infinite or impractically long. We discuss here a methddogy that uses IS dynamically within each regeneration cycle, in order to drive the system back to the regeneration state, after an accurate estimate baa been obtahsed. To obtain large speed-up factors in simulation run time using IS, the modification or bias of the underlying probability measures must be carefully chosen. Analytically or numerically mhdndzing the variance of the IS estimator with respect to the biasing parameters or finding the optimal exponential change of measure is only possible under certain conditions. In this paper, we formulate a s&atistically based technique for optimishsg IS parameter vatues for simulations of queueing systems, including complex systems with bursty arrivat pmcesaes. We use a detersninistic variant of stochastic simulated annealing (SA) called mean tleld annealing (MFA) to minimise statistical estimates of the IS estimator variance. We demonstrate the techsdque by evaluating blocking probabititiea for the W1/K, M/D/l/K, GI/D/lm Geo/Gedl/K, and IBP/Geo/l/K queuea (where Go stands for Geometric and IBP for Interrupted Bernoulli Recess), a 16 x 16 synchronous Cloa Asynchronous ‘IYansfer Mode (ATM) switch, and a 4 x 4 ATM switch with priority and push-out. Run time speed-up factom of two to eteven orders of magnitude over conventional Monte Carlo are obtained for these examples.