Efficient Simulation of Queues in Heavy Traffic

Abstract

When simulating queues in heavy traffic, estimators of quantities such as average delay in queue, d, converge slowly to their true values. This problem is exacerbated when inter-arrival and service distributions are irregular. For the GI/G/1 queue, delay moments can be expressed in terms of moments of idle period I. Instead of estimating d directly, by a standard regenerative estimator that we call DD, a method we call DI estimates d from estimated moments of I. DI was investigated some time ago and shown to be much more efficient than DD in heavy traffic. Efficiency is the factor by which variance is reduced. For GI/G/1, we show how to generate a sequence of realized values of the equilibrium idle period, i.e., that are not i.i.d., but have the correct statistical properties in the long run. We show how to use this sequence to construct a new estimator of d, called DE, and of higher moments of delay as well. When arrivals are irregular, we show that DE is more efficient than DI, in some cases by a large factor, independent of the traffic intensity. Comparing DE with DD, these factors multiply. In the rest of the paper, not discussed in this talk, we use efficient estimators of single-server average delay as control variates to efficiently estimate multi-server average delay. At the end of this talk, we describe some of the results in a second simulation paper, which refines and improves single-server estimators. (Joint work with: Chia-Li Wang, Dept. of Mathematics, National Dong Hwa University, Hualien, Taiwan, ROC)