M/D/1 queue

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

In queueing theory, a discipline within the mathematical theory of probability, an M/D/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service times are fixed (deterministic). The model name is written in Kendall's notation.[1] Agner Krarup Erlang first published on this model in 1909, starting the subject of queueing theory.[2][3] An extension of this model with more than one server is the M/D/c queue.

Model definition[edit]

An M/D/1 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 + 1.
  • Service times are deterministic time D (serving at rate μ = 1/D).
  • A single server serves customers one at a time 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.

Stationary distribution[edit]

The number of jobs in the queue can be written as an M/G/1 type Markov chain and the stationary distribution found for state i (written πi) in the case D = 1 to be[4]

\begin{align}\pi_0 &= 1-\lambda \\ 
\pi_1 &= (1-\lambda)(e^\lambda - 1)\\
\pi_n &= (1-\lambda)\left( e^{n\lambda}+\sum_{k=1}^{n-1}e^{k\lambda}(-1)^{n-k}\left[\frac{(k\lambda)^{n-k}}{(n-k)!}+\frac{(k\lambda)^{n-k-1}}{(n-k-1)!}\right]\right) \quad (n>2).\end{align}

Delay[edit]

Define ρ = λ/μ as the utilization; then the mean delay in the system in an M/D/1 queue is[5]

\frac{1}{2\mu}\cdot\frac{2-\rho}{1-\rho}.

and in the queue:

\frac{1}{2\mu}\cdot\frac{\rho}{1-\rho}.

Busy period[edit]

The busy period is the time period measured from the instant a first customer arrives at an empty queue to the time when the queue is again empty. This time period is equal to D times the number of customers served. If ρ < 1, then the number of customers served during a busy period of the queue has a Borel distribution with parameter ρ.[6][7]

Finite capacity[edit]

Stationary distribution[edit]

A stationary distribution for the number of customers in the queue and mean queue length can be computed using probability generating functions.[8]

Transient solution[edit]

The transient solution of an M/D/1 queue of finite capacity N, often written M/D/1/N, was published by Garcia et al in 2002.[9]

References[edit]

  1. ^ Kendall, D. G. (1953). "Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain". The Annals of Mathematical Statistics 24 (3): 338. doi:10.1214/aoms/1177728975. JSTOR 2236285.  edit
  2. ^ Kingman, J. F. C. (2009). "The first Erlang century—and the next". Queueing Systems 63: 3–4. doi:10.1007/s11134-009-9147-4.  edit
  3. ^ Erlang, A. K. (1909). "The theory of probabilities and telephone conversations" (PDF). Nyt Tidsskrift for Matematik B 20: 33–39. 
  4. ^ Nakagawa, Kenji (2005). "On the Series Expansion for the Stationary Probabilities of an M/D/1 queue" (PDF). Journal of the Operations Research Society of Japan 48 (2): 111–122. 
  5. ^ Cahn, Robert S. (1998). Wide Area Network Design:Concepts and Tools for Optimization. Morgan Kaufmann. p. 319. ISBN 1558604588. 
  6. ^ Tanner, J. C. (1961). "A derivation of the Borel distribution". Biometrika 48: 222–224. doi:10.1093/biomet/48.1-2.222. JSTOR 2333154.  edit
  7. ^ Haight, F. A.; Breuer, M. A. (1960). "The Borel-Tanner distribution". Biometrika 47: 143. doi:10.1093/biomet/47.1-2.143. JSTOR 2332966.  edit
  8. ^ Brun, Olivier; Garcia, Jean-Marie (2000). "Analytical Solution of Finite Capacity M/D/1 Queues". Journal of Applied Probability (Applied Probability Trust) 37 (4): 1092–1098. doi:10.1239/jap/1014843086. JSTOR 3215497.  edit
  9. ^ Garcia, Jean-Marie; Brun, Olivier; Gauchard, David (2002). "Transient Analytical Solution of M/D/1/N Queues". Journal of Applied Probability (Applied Probability Trust) 39 (4): 853–864. JSTOR 3216008.  edit