M/M/∞ queue

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

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[edit]

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.

Mminfinity-statespace.svg

Transient solution[edit]

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

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[edit]

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[edit]

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[edit]

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]

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

Stationary analysis[edit]

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

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[edit]

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[7][11]

where W is a standard Brownian motion.

References[edit]

  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.