Logarithmic asymptotics for steady-state tail probabilities in a single-server queue

Abstract

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 asymptotics of the formx^–1logP(W> x) → –θ∗asx→ ∞forθ∗>0. We require only stationarity of the basic sequence of service times minus interarrival times and a Gärtner–Ellis condition for the cumulant generating function of the associated partial sums, i.e.n^–1logEexp (θS_n) →ψ(θ) asn→ ∞, 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 non-decreasing 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 multiclass queues based on asymptotic decay rates.