Heavy traffic approximation

In queueing theory, a heavy traffic approximation (sometimes heavy traffic limit theorem or diffusion approximation) is a stochastic process which has similar behaviour to a scaled version of a queueing model when utilisation of the system is very high. The first such result was published by John Kingman who showed that when the utilisation parameter of an M/M/1 queue is near 1 a scaled version of the queue length process can be accurately approximated by a reflected Brownian motion.

Heavy traffic condition

Heavy traffic approximations are arrived at by considering the limiting behaviour of a queue. In order for this limit to be finite time and space must both be scaled. If we consider a series of queueing models indexed by n with $\lambda _{n}$ and $\mu _{n}$ the inter-arrival rate and the service rate for queue n respectively, then the heavy traffic condition is given by

${\sqrt {n}}[\lambda _{n}-\mu _{n}]\rightarrow \theta ,{\text{ as }}n\rightarrow \infty .$

Results for a G/G/1 queue

Theorem 1. Consider a sequence of G/G/1 queues indexed by $j$.
For queue $j$
let $T_{j}$ denote the random inter-arrival time, $S_{j}$ denote the random service time; let $\rho _{j}={\frac {\lambda _{j}}{\mu _{j}}}$ denote the traffic intensity with ${\frac {1}{\lambda _{j}}}=E(T_{j})$ and ${\frac {1}{\mu _{j}}}=E(S_{j})$; let $W_{q,j}$ denote the waiting time in queue for a customer in steady state; Let $\alpha _{j}=-E[S_{j}-T_{j}]$ and $\beta _{j}^{2}=\operatorname {var} [S_{j}-T_{j}];$

Suppose that $T_{j}{\xrightarrow {d}}T$, $S_{j}{\xrightarrow {d}}S$, and $\rho _{j}\rightarrow 1$. then

${\frac {2\alpha _{j}}{\beta _{j}^{2}}}W_{q,j}{\xrightarrow {d}}\exp(1)$

provided that:

(a) $\operatorname {Var} [S-T]>0$ (b) for some $\delta >0$, $E[S_{j}^{2+\delta }]$ and $E[T_{j}^{2+\delta }]$ are both less than some constant $C$ for all $j$.

Heuristic argument

• Waiting time in queue

Let $U^{(n)}=S^{(n)}-T^{(n)}$ be the difference between the nth service time and the nth inter-arrival time; Let $W_{q}^{(n)}$ be the waiting time in queue of the nth customer;

Then by definition:

$W_{q}^{(n)}=\max(W_{q}^{(n-1)}+U^{(n-1)},0)$

After recursive calculation, we have:

$W_{q}^{(n)}=\max(U^{(1)}+\cdots +U^{(n-1)},U^{(2)}+\cdots +U^{(n-1)},\ldots ,U^{(n-1)},0)$

• Random walk

Let $P^{(k)}=\sum _{i=1}^{k}U^{(n-i)}$, with $U^{(i)}$ are i.i.d; Define $\alpha =-E[U^{(i)}]$ and $\beta ^{2}=\operatorname {var} [U^{(i)}]$;

Then we have

$E[P^{(k)}]=-k\alpha$

$\operatorname {var} [P^{(k)}]=k\beta ^{2}$

$W_{q}^{(n)}=\max _{n-1\geq k\geq 0}P^{(k)};$

we get $W_{q}^{(\infty )}=\sup _{k\geq 0}P^{(k)}$ by taking limit over $n$.

Thus the waiting time in queue of the nth customer $W_{q}^{(n)}$ is the supremum of a random walk with a negative drift.

• Brownian motion approximation

Random walk can be approximated by a Brownian motion when the jump sizes approach 0 and the times between the jump approach 0.

We have $P^{(0)}=0$ and $P^{(k)}$ has independent and stationary increments. When the traffic intensity $\rho$ approaches 1 and k approach to $\infty$, we have $P^{(t)}\ \sim \ \mathbb {N} (-\alpha t,\beta ^{2}t)$ after replaced k with continuous value t according to functional central limit theorem. Thus the waiting time in queue of the nth customer can be approximated by the supremum of a Brownian motion with a negative drift.

• Supremum of Brownian motion

Theorem 2. Let $X$ be a Brownian motion with drift $\mu$ and standard deviation $\sigma$ starting at the origin, and let $M_{t}\sup _{0\leq s\leq t}X(s)$

if $\mu \leq 0$

$\lim _{t\rightarrow \infty }P(M_{t}>x)=\exp(2\mu x/\sigma ^{2}),x\geq 0;$

otherwise

$\lim _{t\rightarrow \infty }P(M_{t}\geq x)=1,x\geq 0.$

Conclusion

$W_{q}^{(\infty )}\thicksim \exp \left({\frac {2\alpha }{\beta ^{2}}}\right)$ under heavy traffic condition

Thus, the heavy traffic limit theorem (Theorem 1) is heuristically argued. Formal proofs usually follow a different approach which involve characteristic functions.

Example

Consider an M/G/1 queue with arrival rate $\lambda$,the mean of the service time $E[S]={\frac {1}{\mu }}$, and the variance of the service time $\operatorname {var} [S]=\sigma _{B}^{2}$. What is average waiting time in queue in the steady state?

The exact average waiting time in queue in steady state is give by:

$W_{q}={\frac {\rho ^{2}+\lambda ^{2}\sigma _{B}^{2}}{2\lambda (1-\rho )}}$

The corresponding heavy traffic approximation:

$W_{q}^{(H)}={\frac {\lambda ({\frac {1}{\lambda ^{2}}}+\sigma _{B}^{2})}{2(1-\rho )}}.$

The relative error of the heavy traffic approximation:

${\frac {W_{q}^{(H)}-W_{q}}{W_{q}}}={\frac {1-\rho ^{2}}{\rho ^{2}+\lambda ^{2}\sigma _{B}^{2}}}$

Thus when $\rho \rightarrow 1$, we have :

${\frac {W_{q}^{(H)}-W_{q}}{W_{q}}}\rightarrow 0.$

External links

• The G/G/1 queue by Sergey Foss