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 form x –1 log P ( W > x ) → – θ ∗as x → ∞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 –1 log E exp ( θS n ) → ψ ( θ ) as n → ∞, 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.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 290 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.