M/D/c queue: Difference between revisions

Revision as of 17:08, 6 June 2013

Revision as of 10:51, 14 June 2013

Line 1:

In [[queueing theory]], a discipline within the mathematical [[probability theory|theory of probability]], an '''M/D/c queue''' represents the queue length in a system having ''c'' servers, where arrivals are determined by a [[Poisson process]] and job service times are fixed (deterministic). The model name is written in [[Kendall's notation]].<ref>{{cite doi|10.1214/aoms/1177728975}}</ref> [[Agner Krarup Erlang]] first published on this model in 1909, starting the subject of [[queueing theory]].<ref>{{cite doi|10.1007/s11134-009-9147-4}}</ref><ref>{{cite journal | title = The theory of probabilities and telephone conversations | journal = Nyt Tidsskrift for Matematik B | volume = 20 | pages = 33–39 | url = http://oldwww.com.dtu.dk/teletraffic/erlangbook/pps131-137.pdf | year = 1909}}</ref>

#REDIRECT[[M/D/1 queue]]

==Model definition==

An M/D/''c'' queue is a stochastic process whose [[state space]] is the set {0,1,2,3,...} where the value corresponds to the number of customers in the system, including any currently in service.

* Arrivals occur at rate λ according to a [[Poisson process]] and move the process from state ''i'' to ''i''&nbsp;+&nbsp;1.

* Service times are deterministic time ''D'' (serving at rate ''μ''&nbsp;=&nbsp;1/''D'').

* ''c'' servers serve customers from the front of the queue, according to a [[first-come, first-served]] discipline. When the service is complete the customer leaves the queue and the number of customers in the system reduces by one.

* The buffer is of infinite size, so there is no limit on the number of customers it can contain.

==Waiting time distribution==

Erlang showed that when ''ρ''&nbsp;=&nbsp;''λ''&nbsp;''D''/''c''&nbsp;<&nbsp;1, the waiting time distribution has distribution F(''y'') given by<ref name="franx">{{cite doi|10.1016/S0167-6377(01)00108-0}}</ref>

::<math>F(y) = \int_0^\infty F(x+y-D)\frac{\lambda^c x^{c-1}}{(c-1)!} e^{-\lambda x} \text{d} x, \quad y \geq 0 \quad c \in \mathbb N.</math>

Crommelin showed that, writing ''P''_''n'' for the stationary probability of a system with ''n'' or fewer customers,

<ref>{{cite journal | first = C.D. | last = Crommelin | title = Delay probability formulas when the holding times are constant | journal = P.O. Electr. Engr. J.| volume = 25| year=1932| pages= 41–50}}</ref>

::<math>\mathbb P(W \leq x) = \sum_{n=0}^{c-1} P_n \sum_{k=1}^m \frac{(-\lambda(x-kD))^{(k+1)c-1-n}}{((K+1)c-1-n)!}e^{\lambda(x-kD)}, \quad mD \leq x <(m+1)D.</math>

==References==

{{Reflist}}

{{Queueing theory}}

{{Stochastic processes}}

{{DEFAULTSORT:M D c queue}}

[[Category:Stochastic processes]]

[[Category:Single queueing nodes]]