zbMATH — the first resource for mathematics

Logarithmic asymptotics for steady-state tail probabilities in a single- server queue. (English) Zbl 0805.60093
Summary: 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 form \(x^{-1} \log {\mathbf P} (W>x)\to -\theta^*\) as \(x\to\infty\) for \(\theta^*>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^{-1}\log {\mathbf E} \exp(\theta S_ n)\to \psi(\theta)\) as \(n\to \infty\), plus regularity conditions on the decay rate function \(\psi\). The asymptotic decay rate \(\theta^*\) is the root of the equation \(\psi(\theta)=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.

60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
Full Text: DOI