Large deviations theory and efficient simulation of excessive backlogs in a GI/GI/m queue

The problem of using importance sampling to estimate the average time to buffer overflow in a stable GI/GI/m queue is considered. Using the notion of busy cycles, estimation of the expected time to buffer overflow is reduced to the problem of estimating p_n=P (buffer overflow during a cycle) where n is the buffer size. The probability p_n is a large deviations probability (p_n vanishes exponentially fast as n→∞). A rigorous analysis of the method is presented. It is demonstrated that the exponentially twisted distribution of S. Parekh and J. Walrand (1989) has the following strong asymptotic-optimality property within the nonparametric class of all GI/GI importance sampling simulation distributions. As n→∞, the computational cost of the optimal twisted distribution of large deviations theory grows less than exponentially fast, and conversely, all other GI/GI simulation distributions incur a computational cost that grows with strictly positive exponential rate