# M/M/∞ queue

In queueing theory, a discipline within the mathematical theory of probability, the M/M/∞ queue is a multi-server queueing model where every arrival experiences immediate service and does not wait.[1] In Kendall's notation it describes a system where arrivals are governed by a Poisson process, there are infinitely many servers, so jobs do not need to wait for a server. Each job has an exponentially distributed service time. It is a limit of the M/M/c queue model where the number of servers c becomes very large.

The model can be used to model bound lazy deletion performance.[2]

## Model definition

An M/M/∞ queue is a stochastic process whose state space is the set {0,1,2,3,...} where the value corresponds to the number of customers currently being served.

• Arrivals occur at rate λ according to a Poisson process and move the process from state i to i + 1.
• Service times have an exponential distribution with parameter μ and there are always sufficient servers such that every arriving job is served immediately. Transitions from state i to i − 1 are at rate

The model has transition rate matrix

${\displaystyle Q={\begin{pmatrix}-\lambda &\lambda \\\mu &-(\mu +\lambda )&\lambda \\&2\mu &-(2\mu +\lambda )&\lambda \\&&3\mu &-(3\mu +\lambda )&\lambda \\&&&&\ddots \end{pmatrix}}.}$

The state space diagram for this chain is as below.

## Transient solution

The transient distribution can be written using moment generating functions[3] and formulas for transient means and variances computed by solving differential equations.[4] Assuming the system starts in state 0 at time 0, then the probability the system is in state j at time t can be written as[5]:356

${\displaystyle p_{0j}(t)=\exp \left(-{\frac {\lambda }{\mu }}(1-e^{-\mu t})\right){\frac {\left({\frac {\lambda }{\mu }}(1-e^{-\mu t})\right)^{j}}{j!}}{\text{ for }}j\geq 0}$

from which the mean queue length at time t can be computed (writing N(t) for the number of customers in the system at time t given the system is empty at time zero)

${\displaystyle \mathbb {E} (N(t)|N(0)=0)={\frac {\lambda }{\mu }}(1-e^{-\mu t}){\text{ for }}t\geq 0.}$

### Response time

The response time for each arriving job is a single exponential distribution with parameter μ. The average response time is therefore 1/μ.[6]

### Maximum queue length

Given the system is in equilibrium at time 0, we can compute the cumulative distribution function of the process maximum over a finite time horizon T in terms of Charlier polynomials.[2]

### Congestion period

The congestion period is the length of time the process spends above a fixed level c, starting timing from the instant the process transitions to state c + 1. This period has mean value[7]

${\displaystyle {\frac {1}{\lambda }}\sum _{i>c}{\frac {c!}{i!}}\left({\frac {\lambda }{\mu }}\right)^{i-c}}$

and the Laplace transform can be expressed in terms of Kummer's function.[8]

## Stationary analysis

The stationary probability mass function is a Poisson distribution[9]

${\displaystyle \pi _{k}={\frac {(\lambda /\mu )^{k}e^{-\lambda /\mu }}{k!}}\quad k\geq 0}$

so the mean number of jobs in the system is λ/μ.

The stationary distribution of the M/G/∞ queue is the same as that of the M/M/∞ queue.[10]

## Heavy traffic

Writing Nt for the number of customers in the system at time t as ρ → ∞ the scaled process

${\displaystyle X_{t}={\frac {N_{t}-\lambda /\mu }{\sqrt {\lambda /\mu }}}}$

converges to an Ornstein–Uhlenbeck process with normal distribution and correlation parameter 1, defined by the Itō calculus as[7][11]

${\displaystyle dX_{t}=-Xdt+{\sqrt {2}}dW_{t}}$

where W is a standard Brownian motion.

## References

1. ^ Harrison, Peter; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison–Wesley. p. 173.
2. ^ a b Morrison, J. A.; Shepp, L. A.; Van Wyk, C. J. (1987). "A Queueing Analysis of Hashing with Lazy Deletion" (PDF). SIAM Journal on Computing. 16 (6): 1155. doi:10.1137/0216073.
3. ^ El-Sherbiny, A. A. (2010). "Transient Solution to an infinite Server Queue with Varying Arrival and Departure Rate". Journal of Mathematics and Statistics. 6: 1–5. doi:10.3844/jmssp.2010.1.3.
4. ^ Ellis, Peter M. (2010). "The Time-Dependent Mean and Variance of the Non-Stationary Markovian Infinite Server System". Journal of Mathematics and Statistics. 6: 68–71. doi:10.3844/jmssp.2010.68.71.
5. ^ Kulkarni, Vidyadhar G. (1995). Modeling and analysis of stochastic systems (First ed.). Chapman & Hall. ISBN 0412049910.
6. ^ Kleinrock, Leonard (1975). Queueing Systems Volume 1: Theory. pp. 101–103, 404. ISBN 0471491101.
7. ^ a b Guillemin, Fabrice M.; Mazumdar, Ravi R.; Simonian, Alain D. (1996). "On Heavy Traffic Approximations for Transient Characteristics of M/M/∞ Queues". Journal of Applied Probability. Applied Probability Trust. 33 (2): 490–506. doi:10.2307/3215073. ISSN 0021-9002. JSTOR 3215073 – via JSTOR. (registration required (help)).
8. ^ Guillemin, Fabrice; Simonian, Alain (1995). "Transient Characteristics of an M/M/∞ System". Advances in Applied Probability. Applied Probability Trust. 27 (3): 862–88. doi:10.2307/1428137. ISSN 0001-8678. JSTOR 1428137 – via JSTOR. (registration required (help)).
9. ^ Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Trivedi, Kishor Shridharbhai (2006). Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications. John Wiley & Sons. p. 249. ISBN 0471791563.
10. ^ Newell, G. F. (1966). "The M/G/∞ Queue". SIAM Journal on Applied Mathematics. Society for Industrial and Applied Mathematics. 14 (1): 86–8. doi:10.1137/0114007. ISSN 0036-1399. JSTOR 2946178 – via JSTOR. (registration required (help)).
11. ^ Knessl, C.; Yang, Y. P. (2001). "Asymptotic Expansions for the Congestion Period for the M/M/∞ Queue". Queueing Systems. 39 (2/3): 213. doi:10.1023/A:1012752719211.