Kingman’s Bound

We next describe an elegant and useful bound for a single-server queue (G/G/1) due to John Kingman:

\displaystyle \mathbb E[w]\leq\frac{1}{2}\frac{\sigma_s^2+\sigma_a^2}{\bar s-\bar a}.

Consider a workload w\geq0 evolving according to Lindley’s recursion

\displaystyle w'=(w+a-s)_+,

where w' is the workload after an arrival of size a and the provision of s units of service. Here, (z)_+:=\max\{z,0\}.

In a continuous-time queue observed at arrival epochs, a can represent a service requirement and s the time until the next arrival.

Suppose that a and s are mutually independent and independent of w. Write their means as \bar a and \bar s, and their variances as \sigma_a^2 and \sigma_s^2. We assume that \bar a<\bar s, so that the queue is stable.

Kingman’s Bound on Expected Workload

In equilibrium,

\displaystyle \mathbb E[w]\leq\frac{1}{2}\frac{\sigma_s^2+\sigma_a^2}{\bar s-\bar a}.

Proof

Let y:=(w+a-s)_-, where (z)_-:=\max\{-z,0\}. Then

\displaystyle w+a-s=w'-y.

In equilibrium, w' and w have the same distribution. Taking variances gives

\displaystyle \begin{aligned}{var}(w+a-s)&={var}(w)+\sigma_a^2+\sigma_s^2,\\ {var}(w'-y)&={var}(w')+{var}(y)-2{cov}(w',y)\\&={var}(w)+{var}(y)+2\mathbb E[w]\mathbb E[y].\end{aligned}

The final equality uses w'y=0, since at most one of the positive and negative parts can be non-zero.

Taking expectations in w+a-s=w'-y gives

\displaystyle \mathbb E[w]+\bar a-\bar s=\mathbb E[w']-\mathbb E[y]=\mathbb E[w]-\mathbb E[y].

Hence,

\displaystyle \mathbb E[y]=\bar s-\bar a.

Substituting this into the variance identity and rearranging gives

\displaystyle \mathbb E[w]=\frac{1}{2}\frac{\sigma_s^2+\sigma_a^2-{var}(y)}{\bar s-\bar a}\leq\frac{1}{2}\frac{\sigma_s^2+\sigma_a^2}{\bar s-\bar a}.

This proves the bound.

□

The difference between the bound and the exact expression is determined by {var}(y). In heavy traffic, the queue is rarely empty and the undershoot below zero is typically small. The bound therefore becomes increasingly accurate as the load approaches one.

Heavy Traffic and the G/G/1 Queue

The G/G/1 queue can be analysed through Lindley’s recursion, although exact expressions are often difficult to interpret. A useful alternative is to study the queue as its load \rho approaches one from below. This is called the heavy-traffic regime.

Let c_a^2 and c_s^2 denote the squared coefficients of variation of the inter-arrival and service times, respectively, and let \mathbb E[\sigma] be the mean service time. Under standard regularity conditions, the stationary waiting time satisfies

\displaystyle (1-\rho)W\ \xrightarrow{d}\ \widehat W,

where \widehat W is exponentially distributed with mean

\displaystyle \mathbb E[\widehat W]=\frac{c_a^2+c_s^2}{2}\,\mathbb E[\sigma].

Consequently, when \rho is close to one,

\displaystyle \mathbb E[W]\approx\frac{c_a^2+c_s^2}{2}\frac{\mathbb E[\sigma]}{1-\rho}.

This is Kingman’s heavy-traffic approximation. It shows that waiting times grow approximately as 1/(1-\rho) and increase with the variability of both the arrival and service processes.

Leave a comment