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.

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