M/G/1 queue

In queueing theory, a discipline within the mathematical theory of probability, an M/G/1 queue is a single server is a model of queue length where arrivals are detemined by a Poisson process and job service times can have an arbitrary distribution. The model name is written in Kendall's notation, an extension of the M/M/1 model, where service times must be exponentially distributed. The classic application of the M/G/1 queue is to model performance of a fixed head hard disk.

Model definition

An M/G/1 queue is a stochastic process on {0,1,2,3...} where transitions from i to i+1 have an exponential distribution with parameter λ, and transitions from i to i-1 have a general distribution function.

Arrival theorem

As the arrivals are modulated by a Poisson process, the arrival theorem holds.

Pollaczek–Khinchine formulae

See main article Pollaczek–Khinchine formula

The Pollaczek-Khinchine formulae gives the mean queue length and mean waiting time in the system.

Queue length distribution

The probability generating function of the queue length is given by the Pollaczek-Khinchine transform equation

$\Pi (z)={\frac {(1-\rho )(1-z)G(z)}{G(z)-z}}$

where $G(z)=B*[\lambda (1-z)]$ and $B*$ is the Laplace-Stieltjes transform of the service time distribution function. This can be found either using by direct computation or using the method of supplementary variables.

M/G/1 type Markov chains

The embedded Markov chain of the M/G/1 queue has probability transition matrix

$P={\begin{pmatrix}a_{0}&a_{1}&a_{2}&a_{3}&a_{4}&\cdots \\a_{0}&a_{1}&a_{2}&a_{3}&a_{4}&\cdots \\0&a_{0}&a_{1}&a_{2}&a_{3}&\cdots \\0&0&a_{0}&a_{1}&a_{2}&\cdots \\0&0&0&a_{1}&a_{2}&\cdots \\\vdots &\vdots &\vdots &\vdots &\vdots &\ddots \end{pmatrix}}$

where

$a_{v}=\int _{0}^{\infty }e^{-\lambda u}{\frac {(\lambda u)^{v}}{v!}}{\text{d}}F(u)~{\text{ for }}v\geq 0$

and F(u) is the service time distribution and λ the Poisson arrival rate of jobs to the queue. Markov chains with generator matrices or block matrices of this form are called M/G/1 type Markov chains.

Variants

Exceptional first service times (the first customer arriving at an empty queue experiences a delay later customers do not), queues with bulk arrivals (where more than one job arrives at a time)