Heavy traffic approximation

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In queueing theory, a discipline within the mathematical theory of probability, a heavy traffic approximation (sometimes heavy traffic limit theorem[1] 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.[2]

Heavy traffic condition[edit]

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

\hat X_n(t) = \frac{X(nt) - \mathbb E(X(nt))}{\sqrt{n}}

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.[4][5][6]
  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.[7][8][9]
  3. A quantity β is fixed where
\beta = (1-\rho)\sqrt{s}
with ρ representing the traffic intensity and s the number of servers. Traffic intensity and the number of servers are increased to infinity and the limiting process is a hybrid of the above results. This case, first published by Halfin and Whitt is often known as the Halfin–Whitt regime[1][10][11] or quality-and-efficiency-driven (QED) regime.[12]

Results for a G/G/1 queue[edit]

Theorem 1. [13] 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[edit]

  • 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\ \N(-\alpha t, \beta^2 t ) after replaced k with continuous value t according to functional central limit theorem.[14]:110 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.[15]:130 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[edit]

 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.[16][17]

Example[edit]

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[edit]

References[edit]

  1. ^ a b Halfin, S.; Whitt, W. (1981). "Heavy-Traffic Limits for Queues with Many Exponential Servers". Operations Research 29 (3): 567. doi:10.1287/opre.29.3.567.  edit
  2. ^ Kingman, J. F. C.; Atiyah (October 1961). "The single server queue in heavy traffic". Mathematical Proceedings of the Cambridge Philosophical Society 57 (4): 902. doi:10.1017/S0305004100036094. JSTOR 2984229.  edit
  3. ^ Gautam, Natarajan (2012). Analysis of Queues: Methods and Applications. CRC Press. ISBN 9781439806586. 
  4. ^ Kingman, J. F. C. (1962). "On Queues in Heavy Traffic". Journal of the Royal Statistical Society. Series B (Methodological) (Wiley) 24 (2): 383–392. JSTOR 2984229. Retrieved 30 Nov 2012.  edit
  5. ^ Iglehart, Donald L.; Ward, Whitt (1970). "Multiple Channel Queues in Heavy Traffic. II: Sequences, Networks, and Batches". Advances in Applied Probability (Applied Probability Trust) 2 (2): 355–369. JSTOR 1426324. Retrieved 30 Nov 2012.  edit
  6. ^ Köllerström, Julian (1974). "Heavy Traffic Theory for Queues with Several Servers. I". Journal of Applied Probability (Applied Probability Trust) 11 (3): 544–552. JSTOR 3212698.  edit
  7. ^ Iglehart, Donald L. (1965). "Limiting Diffusion Approximations for the Many Server Queue and the Repairman Problem". Journal of Applied Probability (Applied Probability Trust) 2 (2): 429–441. JSTOR 3212203.  edit
  8. ^ Borovkov, A. A. (1967). "On limit laws for service processes in multi-channel systems". Siberian Mathematical Journal 8 (5): 746–763. doi:10.1007/BF01040651.  edit
  9. ^ Iglehart, Donald L. (1973). "Weak Convergence in Queueing Theory". Advances in Applied Probability (Applied Probability Trust) 5 (3): 570–594. JSTOR 1425835.  edit
  10. ^ Puhalskii, A. A.; Reiman, M. I. (2000). "The multiclass GI/PH/N queue in the Halfin-Whitt regime". Advances in Applied Probability 32 (2): 564. doi:10.1239/aap/1013540179.  edit
  11. ^ Reed, J. (2009). "The G/GI/N queue in the Halfin–Whitt regime". The Annals of Applied Probability 19 (6): 2211. doi:10.1214/09-AAP609.  edit
  12. ^ Whitt, W. (2004). "Efficiency-Driven Heavy-Traffic Approximations for Many-Server Queues with Abandonments". Management Science 50 (10): 1449–1461. doi:10.1287/mnsc.1040.0279. JSTOR 30046186.  edit
  13. ^ Gross, D.; Shortie, J. F.; Thompson, J. M.; Harris, C. M. (2013). "Bounds and Approximations". "Fundamentals of Queueing Theory". pp. 329–368. doi:10.1002/9781118625651.ch7. ISBN 9781118625651.  edit
  14. ^ Chen, H.; Yao, D. D. (2001). "Technical Desiderata". "Fundamentals of Queueing Networks". Stochastic Modelling and Applied Probability 46. pp. 97–124. doi:10.1007/978-1-4757-5301-1_5. ISBN 978-1-4419-2896-2.  edit
  15. ^ Chen, H.; Yao, D. D. (2001). "Single-Station Queues". "Fundamentals of Queueing Networks". Stochastic Modelling and Applied Probability 46. pp. 125–158. doi:10.1007/978-1-4757-5301-1_6. ISBN 978-1-4419-2896-2.  edit
  16. ^ Kingman, J. F. C. (1962). "On Queues in Heavy Traffic". Journal of the Royal Statistical Society. Series B (Methodological) (Wiley) 24 (2): 383–392. JSTOR 2984229. Retrieved 30 Nov 2012.  edit
  17. ^ Asmussen, S. R. (2003). "Steady-State Properties of of GI/G/1". "Applied Probability and Queues". Stochastic Modelling and Applied Probability 51. pp. 266–301. doi:10.1007/0-387-21525-5_10. ISBN 978-0-387-00211-8.  edit