World Library  
Flag as Inappropriate
Email this Article

M/M/c queue

Article Id: WHEBN0023152853
Reproduction Date:

Title: M/M/c queue  
Author: World Heritage Encyclopedia
Language: English
Subject: M/G/k queue, M/M/∞ queue, Burke's theorem, M/M/1 queue, Queueing theory
Publisher: World Heritage Encyclopedia

M/M/c queue

In queueing theory, a discipline within the mathematical theory of probability, the M/M/c queue (or Erlang–C model[1]:495) is a multi-server queueing model.[2] In Kendall's notation it describes a system where arrivals form a single queue and are governed by a Poisson process, there are c servers and job service times are exponentially distributed.[3] It is a generalisation of the M/M/1 queue which considers only a single server. The model with infinitely many servers is the M/M/∞ queue.

Model definition

An M/M/c queue is a stochastic process whose state space is the set {0, 1, 2, 3, ...} where the value corresponds to the number of customers in the system, including any currently in service.

  • 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 μ in the M/M/c queue.
  • There are c servers, which serve from the front of the queue. If there are less than c jobs, some of the servers will be idle. If there are more than c jobs, the jobs queue in a buffer.
  • The buffer is of infinite size, so there is no limit on the number of customers it can contain.

The model can be described as a continuous time Markov chain with 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\\ &&&&c\mu & -(c\mu+\lambda) & \lambda \\ &&&&&c\mu & -(c\mu+\lambda) & \lambda \\ &&&&&&c\mu & -(c\mu+\lambda) & \lambda \\ &&&&&&&\ddots\\ \end{pmatrix}

on the state space {0, 1, 2, 3, ...}. The model is a type of birth–death process. We write ρ = λ/(c μ) for the server utilization and require ρ < 1 for the queue to be stable. ρ represents the average proportion of time which each of the servers is occupied (assuming jobs finding more than one vacant server choose their servers randomly).

The state space diagram for this chain is as below.

Stationary analysis

Number of customers in the system

If the traffic intensity is greater than one then the queue will grow without bound but if server utilization ρ < 1 then the system has a stationary distribution with probability mass function[4][5]

\pi_0 = \left[\sum_{k=0}^{c-1}\frac{(c\rho)^k}{k!} + \frac{(c\rho)^c}{c!}\frac{1}{1-\rho}\right]^{-1}
\pi_k = \begin{cases} \pi_0\dfrac{(c\rho)^k}{k!}, & \mbox{if }0 < k < c \\[10pt] \pi_0\dfrac{\rho^k c^c}{c!}, & \mbox{if } c \le k \end{cases}

where πk is the probability that the queue has length k.

The probability that an arriving customer is forced to join the queue (all servers are occupied) is given by

\text{ C}(c,\lambda/\mu)=\frac{\left( \frac{(c\rho)^c}{c!}\right) \left( \frac{1}{1-\rho} \right)}{\sum_{k=0}^{c-1} \frac{(c\rho)^k}{k!} + \left( \frac{(c\rho)^c}{c!} \right) \left( \frac{1}{1-\rho} \right)}

which is referred to as Erlang's C formula and is often denoted C(c, λ/μ) or E2,c(λ/μ).[4] The average number of customers in the system (in service and in the queue) is given by[6]

\frac{\rho}{1-\rho} \text{ C}(c,\lambda/\mu) + c \rho.

Busy period of server

The busy period of the M/M/c queue can either refer to

  • full busy period: the time period between an arrival which finds c−1 customers in the system until a departure which leaves the system with c−1 customers
  • partial busy period: the time period between an arrival which finds the system empty until a departure which leaves the system again empty.[7]

Write[8][9] Tk = min( t: k jobs in the system at time 0+ and k − 1 jobs in the system at time t) and ηk(s) for the Laplace–Stieltjes transform of the distribution of Tk. Then[8]

  1. For k > c, Tk has the same distribution as Tc.
  2. For k = c,
\eta_c(s) = \frac{c \mu}{k \mu + s + \lambda-\lambda \eta_{c}(s)}.
  1. For k < c,
\eta_k(s) = \frac{k \mu}{k \mu + s + \lambda-\lambda \eta_{k+1}(s)}.

Response time

The response time is the total amount of time a customer spends in both the queue and in service. The average response time is the same for all work conserving service disciplines and is[6]

\frac{\text{ C}(c,\lambda/\mu)}{c \mu - \lambda} + \frac{1}{\mu}.

Customers in first-come, first-served discipline

The customer either experiences an immediate exponential service, or must wait for k customers to be served before their own service, thus experiencing an Erlang distribution with shape parameter k + 1.[10]

Customers in processor sharing discipline

In a processor sharing queue the service capacity of the queue is split equally between the jobs in the queue. In the M/M/c queue this means that when there are c or fewer jobs in the system, each job is serviced at rate μ. However, when there are more than c jobs in the system the service rate of each job decreases and is \frac{c\mu}{n} where n is the number of jobs in the system. This means that arrivals after a job of interest can impact the service time of the job of interest. The Laplace–Stieltjes transform of the response time distribution has been shown to be a solution to a Volterra integral equation from which moments can be computed.[11] An approximation has been offered for the response time time distribution.[12][13]

Finite capacity

In an M/M/c/K queue (sometimes known as the Erlang–A model[1]:495) only K customers can queue at any one time (including those in service[4]). Any further arrivals to the queue are considered "lost". We assume that K ≥ c. 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\\ &&&&c\mu & -(c\mu+\lambda) & \lambda \\ &&&&&c\mu & -(c\mu+\lambda) & \lambda \\ &&&&&&&\ddots\\ &&&&&&&c\mu & -(c\mu) \\ \end{pmatrix}

on the state space {0, 1, 2, ..., c, ..., K}. In the case where c = K, the M/M/c/c queue is also known as the Erlang–B model.[1]:495

Transient analysis

See Takács for a transient solution[14] and Stadje for busy period results.[15]

Stationary analysis

Stationary probabilities are given by[16]

\pi_0 = \left[\sum_{k=0}^c \frac{\lambda^k}{\mu^k k!} + \frac{\lambda^c}{\mu^c c!}\sum_{k=c+1}^K \frac{\lambda^{k-c}}{\mu^{k-c} c^{k-c}}\right]^{-1}
\pi_k = \begin{cases} \frac{(\lambda/\mu)^k}{k!}\pi_0 & \text{for } k=1,2,\ldots,c \\ \frac{(\lambda/\mu)^k}{c^{k-c} c!}\pi_0 & \text{for } k=c+1,\ldots,K. \end{cases}

The average number of customers in the system is[16]

\frac{\lambda}{\mu} + \pi_0 \frac{\rho (c\rho)^c}{(1-\rho)^2 c!}

and number of average response time for a customer[16]

\frac{1}{\mu} + \pi_0 \frac{\rho (c\rho)^c}{\lambda (1-\rho)^2 c!}.

Heavy traffic limits

Writing X(t) for the number of customers in the system at time t, it can be shown that under three different conditions the process

\hat X_n(t) = \frac{X(nt) - \mathbb E(X(nt))}{\sqrt{n}}

converges to a diffusion process.[1]:490

  1. Fix μ and c, increase λ and scale by n = 1/(1 − ρ)2.
  2. Fix μ and ρ, increase λ and c, and scale by n = c.
  3. Fix as a constant β where
\beta = (1-\rho)\sqrt{s}

and increase λ and c using the scale n = c or n = 1/(1 − ρ)2. This case is called the Halfin–Whitt regime.[17]

See also


  1. ^ a b c d Gautam, Natarajan (2012). Analysis of Queues: Methods and Applications. CRC Press.  
  2. ^  
  3. ^  
  4. ^ a b c  
  5. ^ Bolch, G.; Greiner, S.; de Meer, H.; Trivedi, K. S. (1998). "Queueing Networks and Markov Chains". pp. 209–262.  
  6. ^ a b Barbeau, Michel; Kranakis, Evangelos (2007). Principles of Ad-hoc Networking. John Wiley & Sons. p. 42.  
  7. ^ Artalejo, J. R.; Lopez-Herrero, M. J. (2001). "Analysis of the Busy Period for the M/M/c Queue: An Algorithmic Approach". Journal of Applied Probability 38 (1): 209–222.  
  8. ^ a b Omahen, K.; Marathe, V. (1978). "Analysis and Applications of the Delay Cycle for the M/M/c Queueing System".  
  9. ^ Daley, D. J.; Servi, L. D. (1998). "Idle and busy periods in stable M / M / k queues". Journal of Applied Probability 35 (4): 950.  
  10. ^ Iversen, Villy B. (June 20, 2001). "ITU/ITC Teletraffic Engineering Handbook". Retrieved August 7, 2012. 
  11. ^ Braband, J. (1994). "Waiting time distributions for M/M/N processor sharing queues".  
  12. ^ Braband, J. (1995). "Waiting time distributions for closed M/M/N processor sharing queues".  
  13. ^ Braband, Jens; Schassberger, Rolf (21–23 September 1993). B. Walke and O. Spaniol, ed. "Messung, Modellierung und Bewertung von Rechen- und Kommunikationssystemen: 7. ITG/GI-Fachtagung". Aachen: Springer. pp. 130–142.  
  14. ^  
  15. ^ Stadje, W. (1995). "The busy periods of some queueing systems". Stochastic Processes and their Applications 55: 159–167.  
  16. ^ a b c Allen, Arnold O. (1990). Probability, Statistics, and Queueing Theory: With Computer Science Applications. Gulf Professional Publishing. pp. 679–680.  
  17. ^ Halfin, Shlomo;  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.