André Dabrowski - A unified approach to fast teller queues and ATM

In the design of modern ATM switches, it is necessary to use simulation to estimate the probability that a queue within the switch exceeds a given large value. Since these are extremely small probabilities, importance sampling methods must be used. Here we obtain a change of measure for a broad class of models with direct applicability to ATM switches.

We consider a model with several independent (not necessarily identical) sources of cells where each source is modeled by a Markov renewal point process with batch arrivals. We do not assume that batch sizes are independent of the state of the Markov process. These arrivals join a queue served by multiple independent servers, each with service times also modeled as a Markov renewal process. The queue is viewed as the additive component of a Markov additive chain constrained so that the additive component remains nonnegative. We apply the theory in McDonald (1996) to obtain the asymptotics of the tail of the distribution of the queue size in steady state and that of the mean time between large deviations of the queue size.

Joint work with B. Beck (Université Catholique de Louvain) and D. McDonald (Ottawa).