LOGARITHMIC ASYMPTOTICS FOR STEADY-STATE TAIL PROBABILITIES IN A SINGLE-SERVER QUEUE

We consider the standard single-server queue with unlimited waiting sp ace and the first-in first-out service discipline, but without any exp licit independence conditions on the interarrival and service times. W e find conditions for the steady-state waiting-time distribution to ha ve asymptotics of the form x-1 log P(W > x) --> -theta as x --> infin ity for theta > 0. We require only stationarity of the basic sequence of service times minus interarrival times and a Gartner-Ellis conditi on for the cumulant generating function of the associated partial sums , i.e. n-1 log E exp (thetaS(n)) --> psi(theta) as n --> infinity), pl us regularity conditions on the decay rate function psi. The asymptoti c decay rate theta is the root of the equation psi(theta) = 0. This r esult in turn implies a corresponding asymptotic result for the steady -state workload in a queue with general non-decreasing input. This asy mptotic result covers the case of multiple independent sources, so tha t it provides additional theoretical support for a concept of effectiv e bandwidths for admission control in multiclass queues based on asymp totic decay rates.