M/M/c queue

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 {{var|λ}} according to a Poisson process and move the process from state {{var|i}} to {{var|i}}+1.
• Service times have an exponential distribution with parameter {{var|μ}}. If there are fewer than {{var|c}} jobs, some of the servers will be idle. If there are more than {{var|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

{{block indent|1=$Q=\backslash 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 {{nowrap|{0, 1, 2, 3, ...}.}} The model is a type of birth–death process. We write {{var|ρ}} = {{var|λ}}/({{var|c μ}}) for the server utilization and require {{var|ρ}} < 1 for the queue to be stable. {{var|ρ}} 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.

{{block indent|1=File:Mmc-statespace.svg}}

If the traffic intensity is greater than one then the queue will grow without bound but if server utilization then the system has a stationary distribution with probability mass function{{cite book |title=Queueing Systems Volume 1: Theory |first1=Leonard |last1=Kleinrock |author-link=Leonard Kleinrock |isbn=0471491101 |date=1975 |pages=101–103, 404}}{{Cite book |first1=G. |last1=Bolch |first2=S. |last2=Greiner |first3=H. |last3=de Meer |first4=K. S. |last4=Trivedi |doi=10.1002/0471200581.ch6 |chapter=Single Station Queueing Systems |title=Queueing Networks and Markov Chains |url= https://archive.org/details/queueingnetworks00bolc_112 |url-access=limited |pages=[https://archive.org/details/queueingnetworks00bolc_112/page/n227 209]–262 |date=1998 |isbn=0471193666}}

{{block indent|1=

$\backslash pi\_0\; =\; \backslash left[\backslash left(\backslash sum\_\{k=0\}^\{c-1\}\backslash frac\{(c\backslash rho)^k\}\{k!\}\; \backslash right)\; +\; \backslash frac\{(c\backslash rho)^c\}\{c!\}\backslash frac\{1\}\{1-\backslash rho\}\backslash right]^\{-1\}$

$\backslash pi\_k\; =\; \backslash begin\{cases\}$

\pi_0\dfrac{(c\rho)^k}{k!}, & \mbox{if }0 < k < c \\[10pt]

\pi_0\dfrac{(c\rho)^k c^{c-k}}{c!}, & \mbox{if } c \le k

\end{cases}

}}

where {{var|π}}_{{var|k}} is the probability that the system contains {{var|k}} customers.

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

{{block indent|1=$\backslash text\{\; C\}(c,\backslash lambda/\backslash mu)=\backslash frac\{\backslash left(\; \backslash frac\{(c\backslash rho)^c\}\{c!\}\backslash right)\; \backslash left(\; \backslash frac\{1\}\{1-\backslash rho\}\; \backslash right)\}\{\backslash sum\_\{k=0\}^\{c-1\}\; \backslash frac\{(c\backslash rho)^k\}\{k!\}\; +\; \backslash left(\; \backslash frac\{(c\backslash rho)^c\}\{c!\}\; \backslash right)\; \backslash left(\; \backslash frac\{1\}\{1-\backslash rho\}\; \backslash right)\}=\backslash frac\{1\}\{1+\backslash left(\; 1-\backslash rho\; \backslash right)\; \backslash left(\; \backslash frac\{c!\}\{(c\backslash rho)^c\}\; \backslash right)\; \backslash sum\_\{k=0\}^\{c-1\}\; \backslash frac\{(c\backslash rho)^k\}\{k!\}\}$}}

which is referred to as Erlang's C formula and is often denoted C({{var|c}}, {{var|λ}}/{{var|μ}}) or E_2,{{var|c}}({{var|λ}}/{{var|μ}}). The average number of customers in the system (in service and in the queue) is given by{{cite book |title=Principles of Ad-hoc Networking |url= https://archive.org/details/principlesadhocn00barb |url-access=limited |page=[https://archive.org/details/principlesadhocn00barb/page/n64 42] |first1=Michel |last1=Barbeau |first2=Evangelos |last2=Kranakis |publisher=John Wiley & Sons |date=2007 |isbn=978-0470032909}}

{{block indent|1=$\backslash frac\{\backslash rho\}\{1-\backslash rho\}\; \backslash text\{\; C\}(c,\backslash lambda/\backslash mu)\; +\; c\; \backslash rho.$}}

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

• full busy period: the time period between an arrival which finds {{var|c}}−1 customers in the system until a departure which leaves the system with {{var|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.{{cite journal |first1=J. R.| last1=Artalejo |first2=M. J. |last2=Lopez-Herrero |date=2001 |title=Analysis of the Busy Period for the M/M/c Queue: An Algorithmic Approach |journal=Journal of Applied Probability |volume=38 |issue=1 |pages=209–222 |jstor=3215752 |doi=10.1239/jap/996986654| s2cid=123361268 }}

Write{{Cite journal |last1=Omahen |first1=K. |last2=Marathe |first2=V. |doi=10.1145/322063.322072 |title=Analysis and Applications of the Delay Cycle for the M/M/c Queueing System |journal=Journal of the ACM |volume=25 |issue=2 |pages=283 |date=1978 |s2cid=16257795 |url= https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1110&context=cstech|doi-access=free }}{{Cite journal |last1=Daley |first1=D. J. |last2=Servi |first2=L. D. |doi=10.1239/jap/1032438390 |title=Idle and busy periods in stable M / M / k queues |journal=Journal of Applied Probability |volume=35 |issue=4 |pages=950 |date=1998|s2cid=121993161 }} {{var|T}}_{{var|k}} = min( t: {{var|k}} jobs in the system at time 0⁺ and {{var|k}} − 1 jobs in the system at time {{var|t}}) and {{var|η}}_{{var|k}}({{var|s}}) for the Laplace–Stieltjes transform of the distribution of {{var|T}}_{{var|k}}. Then

1. For {{var|k}} > {{var|c}}, {{var|T}}_{{var|k}} has the same distribution as {{var|T}}_{{var|c}}.
2. For {{var|k}} = {{var|c}},{{block indent|1=$\backslash eta\_c(s)\; =\; \backslash frac\{c\; \backslash mu\}\{k\; \backslash mu\; +\; s\; +\; \backslash lambda-\backslash lambda\; \backslash eta\_\{c\}(s)\}.$}}
3. For {{var|k}} < {{var|c}},{{block indent|1=$\backslash eta\_k(s)\; =\; \backslash frac\{k\; \backslash mu\}\{k\; \backslash mu\; +\; s\; +\; \backslash lambda-\backslash lambda\; \backslash eta\_\{k+1\}(s)\}.$}}

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

{{block indent|1=$\backslash frac\{\backslash text\{\; C\}(c,\backslash lambda/\backslash mu)\}\{c\; \backslash mu\; -\; \backslash lambda\}\; +\; \backslash frac\{1\}\{\backslash mu\}.$}}

The customer either experiences an immediate exponential service, or must wait for {{var|k}} customers to be served before their own service, thus experiencing an Erlang distribution with shape parameter {{var|k}} + 1.{{cite web |url= http://www.itu.int/ITU-D/study_groups/SGP_1998-2002/SG2/StudyQuestions/Question_16/RapporteursGroupDocs/teletraffic.pdf |title=ITU/ITC Teletraffic Engineering Handbook |first=Villy B. |last=Iversen |date=June 20, 2001 |access-date=August 7, 2012}}

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 {{var|c}} or fewer jobs in the system, each job is serviced at rate {{var|μ}}. However, when there are more than {{var|c}} jobs in the system the service rate of each job decreases and is $\backslash frac\{c\backslash mu\}\{n\}$ where {{var|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.{{Cite journal |last1=Braband |first1=J. |title=Waiting time distributions for M/M/N processor sharing queues |doi=10.1080/15326349408807309 |journal=Communications in Statistics. Stochastic Models |volume=10 |issue=3 |pages=533–548 |date=1994}} An approximation has been offered for the response time distribution.{{Cite journal |last1=Braband |first1=J. |title=Waiting time distributions for closed M/M/N processor sharing queues |doi=10.1007/BF01150417 |journal=Queueing Systems |volume=19 |issue=3 |pages=331–344 |date=1995|s2cid=6284577 }}{{cite book |first1=Jens |last1=Braband |first2=Rolf |last2=Schassberger |chapter=Random Quantum Allocation: A New Approach to Waiting Time Distributions for M/M/N Processor Sharing Queues |title=Messung, Modellierung und Bewertung von Rechen- und Kommunikationssystemen: 7. ITG/GI-Fachtagung |date=21–23 September 1993 |editor-first1=Bernhard H. |editor-last1=Walke |editor-link1=Bernhard H. Walke |editor-first2=Otto |editor-last2=Spaniol |editor-link2=:de:Otto Spaniol |location=Aachen, Germany |publisher=Springer |pages=130–142 |isbn=3540572015}}

In an M/M/{{var|c}}/{{var|K}} queue only {{var|K}} customers can queue at any one time (including those in service). Any further arrivals to the queue are considered "lost". We assume that {{var|K}} ≥ {{var|c}}. The model has transition rate matrix

{{block indent|1=$Q=\backslash 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, ..., {{var|c}}, ..., {{var|K}}}. In the case where {{var|c}} = {{var|K}}, the M/M/{{var|c}}/{{var|c}} queue is also known as the Erlang–B model.{{rp|495}}

See Takács for a transient solution{{cite book |first=L. |last=Takács |author-link=Lajos Takács |title=Introduction to the Theory of Queues |location=London |publisher=Oxford University Press |date=1962 |pages=12–21}} and Stadje for busy period results.{{Cite journal |last1=Stadje |first1=W. |doi=10.1016/0304-4149(94)00032-O |title=The busy periods of some queueing systems |journal=Stochastic Processes and Their Applications |volume=55 |pages=159–167 |date=1995|doi-access=free }}

Stationary probabilities are given by{{cite book |title=Probability, Statistics, and Queueing Theory: With Computer Science Applications |first=Arnold O. |last=Allen |publisher=Gulf Professional Publishing |date=1990 |isbn=0120510510 |pages=[https://archive.org/details/probabilitystati0000alle/page/679 679–680] |url= https://archive.org/details/probabilitystati0000alle/page/679}}

{{block indent|1=$\backslash pi\_0\; =\; \backslash left[\backslash sum\_\{k=0\}^\{c\}\; \backslash frac\{\backslash lambda^k\}\{\backslash mu^k\; k!\}\; +\; \backslash frac\{\backslash lambda^c\}\{\backslash mu^c\; c!\}\backslash sum\_\{k=c+1\}^K\; \backslash frac\{\backslash lambda^\{k-c\}\}\{\backslash mu^\{k-c\}\; c^\{k-c\}\}\backslash right]^\{-1\}$}}

{{block indent|1=$\backslash pi\_k\; =\; \backslash 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

{{block indent|1=$L\; =\; \backslash frac\{\backslash lambda\}\{\backslash mu\}\; +\; \backslash pi\_0\; \backslash frac\{\backslash rho\; (c\backslash rho)^c\}\{(1-\backslash rho)^2\; c!\}$}}

and the average time in the system for a customer is

{{block indent|1=$W\; =\; \backslash frac\{1\}\{\backslash mu\}\; +\; \backslash pi\_0\; \backslash frac\{\backslash rho\; (c\backslash rho)^c\}\{\backslash lambda\; (1-\backslash rho)^2\; c!\}$}}

The average time in the queue for a customer is

{{block indent|1=$W\_q\; =\; \backslash pi\_0\; \backslash frac\{\backslash rho\; (c\backslash rho)^c\}\{\backslash lambda\; (1-\backslash rho)^2\; c!\}$}}

The average number of customers in the queue can be obtained by using the effective arrival rate. The effective arrival rate is calculated by

{{block indent|1=$\backslash mathbb\{\backslash lambda\_a\}\; =\; \backslash lambda(1-p\_K)$}}

Thus we can obtain the average number of customers in the queue by

{{block indent|1=$L\_q\; =\; \backslash lambda\_a\; W\_q$}}

An implementation of the above calculations in Python can be found.{{cite web | url=https://github.com/HankerZheng/Basic-Calculator-for-Queueing-Theory/blob/master/MMcQueue.py | title=Basic Calculator for Queueing Theory | website=GitHub }}

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

{{block indent|1=$\backslash hat\; X\_n(t)\; =\; \backslash frac\{X(nt)\; -\; \backslash mathbb\; E(X(nt))\}\{\backslash sqrt\{n\}\}$}}

converges to a diffusion process.{{rp|490}}

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

and increase {{var|λ}} and {{var|c}} using the scale {{var|n}} = {{var|c}} or {{var|n}} = 1/(1 − {{var|ρ}})². This case is called the Halfin–Whitt regime.{{cite journal |first1=Shlomo |last1=Halfin |first2=Ward |last2=Whitt |author-link2=Ward Whitt |date=1981 |title=Heavy-Traffic Limits for Queues with Many Exponential Servers |journal=Operations Research |volume=29 |issue=3 |pages=567–588 |jstor=170115 |doi=10.1287/opre.29.3.567 |url= http://www.columbia.edu/~ww2040/Halfin81.pdf}}

• Spectral expansion solution
• M/G/k queue

{{Reflist}}

{{Queueing theory}}

{{Stochastic processes}}

{{DEFAULTSORT:M M c queue}}

Category:Single queueing nodes