Conditional importance sampling and its application to ATM switch analysis

Importance sampling has been used as an efficient method for estimating rare probabilities (on the order of 10/sup -6/ or less) relating to the performance of communication systems and networks. Parametric importance sampling methods are not very effective in cases where the input processes are characterized by uniform probability distributions (e.g., random delays), which arise frequently. We present a conditional importance sampling scheme for systems with input processes that can be characterized by uniform distributions. The scheme adaptively modifies an initial biasing strategy as samples are taken. Changing a problem specific component enables the algorithm to be applied to a diverse set of systems. The overall approach is more effective than parametrically biasing the uniform input distributions. We use the conditional biasing algorithm to estimate rare jitter probabilities in ATM switches for CBR sources multiplexed with heterogeneous background traffic. For the experimental systems considered, we observe that the improvement in simulation efficiency is inversely proportional to the probability being estimated.