A unified approach to fast teller queues and ATM

This paper examines a problem of importance to the telecommunications indus try. In the design of modern ATM switches, it is necessary to use simulatio n to estimate the probability that a queue within the switch exceeds a give n large value. Since these are extremely small probabilities, importance sa mpling methods mast 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 A independent sources of cells where each source i s modeled by a Markov renewal point process with batch arrivals. We do not assume the sources are necessarily identically distributed, nor that batch sizes are independent of thr state of the Markov process. These arrivals jo in a queue served by multiple independent servers, each with service times also modeled as a Markov renewal process. We only discuss a time-slotted sy stem. The queue is viewed as the additive component of a Markov additive ch ain subject to the constraint that the additive component remains non-negat ive. We apply the theory in McDonald (1999) to obtain the asymptotics of th e tail of the distribution of the queue size in steady state plus the asymp totics of the mean time between large deviations of the queue size.