# M/D/1 queue

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

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.

## Delay

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

$\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

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 ρ.[5][6]

## Finite capacity

### Stationary distribution

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

### Transient solution

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.[8]

## References

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". Nyt Tidsskrift for Matematik B 20: 33–39.
4. ^ Cahn, Robert S. (1998). Wide Area Network Design:Concepts and Tools for Optimization. Morgan Kaufmann. p. 319. ISBN 1558604588.
5. ^ 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
6. ^ 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
7. ^ 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
8. ^ 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