Heavy traffic approximation: Difference between revisions
Gareth Jones (talk | contribs) →Heavy traffic condition: add further examples of Halfin-Whitt regime |
Gareth Jones (talk | contribs) use templates for references |
||
Line 17: | Line 17: | ||
==Results for a G/G/1 queue == |
==Results for a G/G/1 queue == |
||
'''Theorem 1.''' <ref> |
'''Theorem 1.''' <ref>{{cite doi|10.1002/9781118625651.ch7}}</ref> Consider a sequence of [[G/G/1 queue]]s indexed by <math>j</math>. |
||
<br> |
<br> |
||
For queue <math>j</math> |
For queue <math>j</math> |
||
Line 60: | Line 60: | ||
[[Random walk]] can be approximated by a [[Brownian motion]] when the jump sizes approach 0 and the times between the jump approach 0.<br /> |
[[Random walk]] can be approximated by a [[Brownian motion]] when the jump sizes approach 0 and the times between the jump approach 0.<br /> |
||
We have <math>P^{(0)}=0</math> and <math>P^{(k)}</math> has independent and stationary increments. When the traffic intensity <math>\rho</math> approaches 1 and k approach to <math>\infty</math>, we have <math>P^{(t)} \ \sim\ \N(-\alpha t, \beta^2 t )</math> after replaced k with continuous value t according to [[functional central limit theorem]].<ref> |
We have <math>P^{(0)}=0</math> and <math>P^{(k)}</math> has independent and stationary increments. When the traffic intensity <math>\rho</math> approaches 1 and k approach to <math>\infty</math>, we have <math>P^{(t)} \ \sim\ \N(-\alpha t, \beta^2 t )</math> after replaced k with continuous value t according to [[functional central limit theorem]].<ref>{{cite doi|10.1007/978-1-4757-5301-1_5}}</ref>{{rp|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''' |
* '''Supremum of Brownian motion''' |
||
'''Theorem 2.'''<ref> |
'''Theorem 2.'''<ref>{{cite doi|10.1007/978-1-4757-5301-1_6}}</ref>{{rp|130}} Let <math>X</math> be a [[Brownian motion]] with drift <math>\mu</math> and standard deviation <math>\sigma</math> starting at the origin, and let <math>M_t\sup_{0\leq s\leq t} X(s)</math> |
||
if <math>\mu \leq 0</math> |
if <math>\mu \leq 0</math> |
Revision as of 17:24, 25 November 2013
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
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 as n → ∞.
There are three classes of regime under which such approximations are generally considered.
- 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]
- 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]
- A quantity β is fixed where
- 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]
Results for a G/G/1 queue
Theorem 1. [12] Consider a sequence of G/G/1 queues indexed by .
For queue
let denote the random inter-arrival time, denote the random service time;
let denote the traffic intensity with and ;
let denote the waiting time in queue for a customer in steady state;
Let and
Suppose that , , and . then
provided that:
(a) (b) for some , and are both less than some constant for all .
Heuristic argument
- Waiting time in queue
Let 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:
- Random walk
Let , with are i.i.d; Define and ;
Then we have
we get 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.
- 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 and has independent and stationary increments. When the traffic intensity approaches 1 and k approach to , we have after replaced k with continuous value t according to functional central limit theorem.[13]: 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.[14]: 130 Let be a Brownian motion with drift and standard deviation starting at the origin, and let
if
otherwise
Conclusion
- 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.[15][16]
Example
Consider an M/G/1 queue with arrival rate ,the mean of the service time , 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 give by:
The corresponding heavy traffic approximation:
The relative error of the heavy traffic approximation:
Thus when , we have :
External links
- The G/G/1 queue by Sergey Foss
References
- ^ a b Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1287/opre.29.3.567, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1287/opre.29.3.567
instead. - ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1017/S0305004100036094, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1017/S0305004100036094
instead. - ^ Gautam, Natarajan (2012). Analysis of Queues: Methods and Applications. CRC Press. ISBN 9781439806586.
- ^ Attention: This template ({{cite jstor}}) is deprecated. To cite the publication identified by jstor:2984229, please use {{cite journal}} with
|jstor=2984229
instead. - ^ Attention: This template ({{cite jstor}}) is deprecated. To cite the publication identified by jstor:1426324, please use {{cite journal}} with
|jstor=1426324
instead. - ^ Attention: This template ({{cite jstor}}) is deprecated. To cite the publication identified by jstor:3212698, please use {{cite journal}} with
|jstor=3212698
instead. - ^ Attention: This template ({{cite jstor}}) is deprecated. To cite the publication identified by jstor:3212203, please use {{cite journal}} with
|jstor=3212203
instead. - ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/BF01040651, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1007/BF01040651
instead. - ^ Attention: This template ({{cite jstor}}) is deprecated. To cite the publication identified by jstor:1425835, please use {{cite journal}} with
|jstor=1425835
instead. - ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1239/aap/1013540179, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1239/aap/1013540179
instead. - ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1214/09-AAP609, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1214/09-AAP609
instead. - ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1002/9781118625651.ch7, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1002/9781118625651.ch7
instead. - ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/978-1-4757-5301-1_5, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1007/978-1-4757-5301-1_5
instead. - ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/978-1-4757-5301-1_6, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1007/978-1-4757-5301-1_6
instead. - ^ Attention: This template ({{cite jstor}}) is deprecated. To cite the publication identified by jstor:2984229, please use {{cite journal}} with
|jstor=2984229
instead. - ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/0-387-21525-5_10, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1007/0-387-21525-5_10
instead.