Scaling limit of a queue

An asymptotic description obtained by increasing queue resources or input size, or by approaching critical load while rescaling time and workload. Large-buffer queue scaling, many-source queue scaling, moderate-deviation queue scaling and the heavy-traffic limit of a queue preserve different relations between mean load, random fluctuations and storage.

For fixed independent and identically distributed arrivals of mean $\mu$ and positive finite variance ${\sigma }^2$, put service at $\mu +\epsilon d$. Rescaling net input by space $\epsilon$ and time ${\epsilon }^{-2}$ gives Brownian motion with drift $-d$ by the functional central limit theorem. The continuous Skorokhod reflection map on the half-line gives the displayed transient limit, with a correspondingly scaled initial workload. A stationary approximation additionally requires justification of limit interchange. When valid, the stationary law of negatively drifted reflected Brownian motion predicts $\mathbb{P}(Q_{\epsilon }>b/\epsilon )\approx e^{-2db/{\sigma }^2}$.

For a bufferless queue with Poisson mean input $L\lambda$, place the service margin at $C{L}^{(1+\beta )/2}$, $0<\beta <1$. It exceeds the ordinary square-root fluctuation scale but is sublinear in total input. The Poisson moderate deviation principle gives the displayed overflow exponent. This interpolates between a central-limit safety margin and a fixed per-source excess capacity.

Scale independent source count, service and buffer by the same factor $L$. For lookback horizon $n$, the source-average cumulative input has rate function $I_n$, and reaching buffer level $b$ requires input above $b+cn$. Optimizing this horizon gives the displayed exponent under uniform control of the infinite stationary supremum. For independent slots, $I_n(x)=n{I}_A(x/n)$; discrete time keeps $n$ an integer. Temporal dependence instead enters through the cumulative-input cumulant-generating function.

Hold a stable input law and service rate of a queue fixed while the buffer size of a queue grows. Under interior exponential-moment and root hypotheses, the Cramér-Lundberg workload exponent gives an exponential tail linear in buffer size. A likely overflow accumulates during a lookback horizon proportional to the buffer size.

For nondegenerate independent and identically distributed arrivals with mean below $c$, suppose the positive root is interior to the moment-generating function domain. Then ${\Lambda }_A^{\prime }({\theta }_{\ast })>c$. The Fenchel–Young inequality gives $t{I}_A(c+1/t)\ge {\theta }_{\ast }$ for every $t>0$, and equality occurs at $t=[{\Lambda }_A^{\prime }({\theta }_{\ast })-c{]}^{-1}$. The exponential workload bound from cumulative arrival moments gives the upper logarithmic tail bound for every $\theta <{\theta }_{\ast }$. A horizon of the indicated length times buffer size gives the matching lower bound by Cramér's theorem. A positive interior root is an assumption; if arrivals never exceed capacity, positive workload cannot arise.