In queueing theory, a discipline within the mathematical theory of probability, a heavy traffic approximation (sometimes called heavy traffic limit theorem[1] or diffusion approximation) involves the matching of a queueing model with a diffusion process under some limiting conditions on the model's parameters.
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.
[2] Heavy traffic approximations are typically stated for the process X(t) describing the number of customers in the system at time t. They are arrived at by considering the model under the limiting values of some model parameters and therefore for the result to be finite the model must be rescaled by a factor n, denoted[3]: 490 and the limit of this process is considered as n → ∞.
There are three classes of regime under which such approximations are generally considered.
[13] Consider a sequence of G/G/1 queues indexed by
denote the random inter-arrival time,
denote the random service time; let
denote the traffic intensity with
denote the waiting time in queue for a customer in steady state; Let
{\displaystyle \operatorname {Var} [S-T]>0}
be the difference between the nth service time and the nth inter-arrival time; Let
be the waiting time in queue of the nth customer; Then by definition: After recursive calculation, we have: Let
by taking limit over
Thus the waiting time in queue of the nth customer
is the supremum of a random walk with a negative drift.
Random walk can be approximated by a Brownian motion when the jump sizes approach 0 and the times between the jump approach 0.
has independent and stationary increments.
When the traffic intensity
with continuous value
according to functional central limit theorem.
[14]: 110 Thus the waiting time in queue of the
th customer can be approximated by the supremum of a Brownian motion with a negative drift.
be a Brownian motion with drift
and standard deviation
otherwise Thus, the heavy traffic limit theorem (Theorem 1) is heuristically argued.
Formal proofs usually follow a different approach which involve characteristic functions.
[4][16] Consider an M/G/1 queue with arrival rate
, and the variance of the service time
What is average waiting time in queue in the steady state?
The exact average waiting time in queue in steady state is given by: The corresponding heavy traffic approximation: The relative error of the heavy traffic approximation: Thus when