# 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. 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.

## 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 The state space diagram for this chain is as below. ## Transient solution

The transient distribution can be written using moment generating functions and formulas for transient means and variances computed by solving differential equations. 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:356 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) ### Response time

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

### 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.

### 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 and the Laplace transform can be expressed in terms of Kummer's function.

## Stationary analysis

The stationary probability mass function is a Poisson distribution 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.

## Heavy traffic

Writing Nt for the number of customers in the system at time t as ρ  ∞ the scaled process converges to an Ornstein–Uhlenbeck process with normal distribution and correlation parameter 1, defined by the Itō calculus as 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. 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. 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.