Kalpana Kalpana (Editor)

Heavy traffic approximation

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In queueing theory, a discipline within the mathematical theory of probability, a heavy traffic approximation (sometimes heavy traffic limit theorem or diffusion approximation) is 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.

Contents

Heavy traffic condition

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

and the limit of this process is considered as n → ∞.

There are three classes of regime under which such approximations are generally considered.

  1. The number of servers is fixed and the traffic intensity (utilization) is increased to 1 (from below). The queue length approximation is a reflected Brownian motion.
  2. Traffic intensity is fixed and the number of servers and arrival rate are increased to infinity. Here the queue length limit converges to the normal distribution.
  3. A quantity β is fixed where

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 ρ j = λ j μ j denote the traffic intensity with 1 λ j = E ( T j ) and 1 μ j = E ( S j ) ; let W q , j denote the waiting time in queue for a customer in steady state; Let α j = − E [ S j − T j ] and β j 2 = var ⁡ [ S j − T j ] ;

Suppose that T j → d T , S j → d S , and ρ j → 1 . then

2 α j β j 2 W q , j → d exp ⁡ ( 1 )

provided that:

(a) Var ⁡ [ S − T ] > 0 (b) for some δ > 0 , E [ S j 2 + δ ] and E [ T j 2 + δ ] 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 ) + ⋯ + U ( n − 1 ) , U ( 2 ) + ⋯ + U ( n − 1 ) , … , U ( n − 1 ) , 0 )
  • Random walk

    • Let P ( k ) = ∑ i = 1 k U ( n − i ) , with U ( i ) are i.i.d; Define α = − E [ U ( i ) ] and β 2 = var ⁡ [ U ( i ) ] ;

    Then we have

    E [ P ( k ) ] = − k α var ⁡ [ P ( k ) ] = k β 2 W q ( n ) = max n − 1 ≥ k ≥ 0 P ( k ) ;

    we get W q ( ∞ ) = sup k ≥ 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 ρ approaches 1 and k approach to ∞ , we have P ( t )   ∼   N ( − α t , β 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 μ and standard deviation σ starting at the origin, and let M t sup 0 ≤ s ≤ t X ( s )

    if μ ≤ 0

    lim t → ∞ P ( M t > x ) = exp ⁡ ( 2 μ x / σ 2 ) , x ≥ 0 ;

    otherwise

    lim t → ∞ P ( M t ≥ x ) = 1 , x ≥ 0.

    Conclusion

    W q ( ∞ ) ∼ exp ⁡ ( 2 α β 2 ) 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 λ ,the mean of the service time E [ S ] = 1 μ , and the variance of the service time var ⁡ [ S ] = σ 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 = ρ 2 + λ 2 σ B 2 2 λ ( 1 − ρ )

    The corresponding heavy traffic approximation:

    W q ( H ) = λ ( 1 λ 2 + σ B 2 ) 2 ( 1 − ρ ) .

    The relative error of the heavy traffic approximation:

    W q ( H ) − W q W q = 1 − ρ 2 ρ 2 + λ 2 σ B 2

    Thus when ρ → 1 , we have :

    W q ( H ) − W q W q → 0.

    References

    Heavy traffic approximation Wikipedia
    (Text) CC BY-SA