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

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.

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

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)

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

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]

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

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

 \pi_k = \frac{(\lambda/\mu)^k e^{-\lambda/\mu}}{k!} \quad k \geq 0

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

Heavy traffic[edit]

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

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

dX_t = -Xdt+\sqrt{2}dW_t

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". SIAM Journal on Computing 16 (6): 1155. doi:10.1137/0216073.  edit
  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.  edit
  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.  edit
  5. ^ Kulkarni, Vidyadhar G. (1995). Modeling and analysis of stochastic systems (First edition 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. JSTOR 3215073.  edit
  8. ^ Guillemin, Fabrice; Simonian, Alain (1995). "Transient Characteristics of an M/M/∞ System". Advances in Applied Probability (Applied Probability Trust) 27 (3): 862–888. JSTOR Applied Probability Trust.  edit
  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. ^ 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.  edit