Logarithmic Asymptotics for Steady-State Tail Probabilities in a Single-Server Queue

P. W. Glynn and W. Whitt

Advances in Applied Probability, 131-156 (1994)

We consider the standard single-server queue with unlimited waiting space and the first-in first-out service discipline, but without any explicit independence conditions on the interarrival and service times. We find conditions for the steady-state waiting-time distribution to have small-tail asymptotics of the form x-1log P(W>x)->-θ* as x->∞ for θ>0. We require only stationarity of the basic sequence of service times minus interarrival times and a Gartner- Ellis condition for the cumulant generating function of the associated partial sums, i.e., n-1log Eexp(θSn)->ψ(θ), plus regularity conditions on the decay rate function ψ. The asymptotic decay rate θ* is the root of the equation ψ(θ)=0. This result in turn implies a corresponding asymptotic result for the steady-state workload in a queue with general nondecreasing input. This asymptotic result covers the case of multiple independent sources, so that it provides additional theoretical support for a concept of effective bandwidths for admission control in multi-class queues based on asymptotic decay rates.