192.198.151.43: Spelling change later to latter

2013-10-23T10:05:11Z

Spelling change later to latter

New page

In [[queueing theory]], a discipline within the mathematical [[probability theory|theory of probability]], the '''M/M/c queue''' (or '''Erlang–C model'''<ref name="gautam">{{cite book | first = Natarajan | last = Gautam | title = Analysis of Queues: Methods and Applications | publisher = CRC Press | year = 2012 | isbn = 9781439806586}}</ref>{{rp|495}}) is a multi-server [[queueing model]].<ref name="harrison">{{cite book|first=Peter|last=Harrison|authorlink=Peter G. Harrison|first2=Naresh M.|last2=Patel|title=Performance Modelling of Communication Networks and Computer Architectures|publisher=Addison–Wesley|year=1992|page=173}}</ref> 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.<ref>{{cite doi|10.1214/aoms/1177728975}}</ref> 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]]
:<math>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}</math>

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.

[[File:Mmc-statespace.svg]]

==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]]<ref name="kleinrock">{{cite book | title = Queueing Systems Volume 1: Theory | first1=Leonard | last1=Kleinrock | authorlink = Leonard Kleinrock | isbn = 0471491101 | year=1975 | pages=101–103, 404}}</ref><ref>{{cite doi | 10.1002/0471200581.ch6 }}</ref>
:: <math>\pi_0 = \left[\sum_{k=0}^{c-1}\frac{(c\rho)^k}{k!} + \frac{(c\rho)^c}{c!}\frac{1}{1-\rho}\right]^{-1}</math>
:: <math>\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}</math>

The probability that an arriving customer is forced to join the queue (all servers are occupied) is given by
::<math>\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)}</math>
which is referred to as [[Erlang's C formula]] and is often denoted C(''c'', ''λ''/''μ'') or E2,''c''(''λ''/''μ'').<ref name="kleinrock" /> The average number of customers in the system (in service and in the queue) is given by<ref name="barbeau">{{cite book | title = Principles of Ad-hoc Networking | page = 42 | first1=Michel |last1=Barbeau | first2= Evangelos |last2 =Kranakis | publisher = John Wiley & Sons| year = 2007 | isbn=0470032901}}</ref>
::<math>\frac{\rho}{1-\rho} \text{ C}(c,\lambda/\mu) + c \rho.</math>

===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.<ref>{{cite jstor|3215752}}</ref>

Write<ref name="omahen">{{cite doi|10.1145/322063.322072}}</ref><ref>{{cite doi|10.1239/jap/1032438390}}</ref>
::<math>T_k = \min\left[ t:\begin{align}
(k) \text{ jobs in the system at time } 0^+\\
(k-1) \text{ jobs in the system at time } t
\end{align}\right]</math>
and ''η''''k''(''s'') for the [[Laplace–Stieltjes transform]] of the distribution of ''T''''k''. Then<ref name="omahen" />
# For ''k'' > ''c'', ''T''''k'' has the same distribution as ''T''''c''.
# For ''k'' = ''c'',
::<math>\eta_c(s) = \frac{c \mu}{k \mu + s + \lambda-\lambda \eta_{c}(s)}.</math>
# For ''k'' < ''c'',
::<math>\eta_k(s) = \frac{k \mu}{k \mu + s + \lambda-\lambda \eta_{k+1}(s)}.</math>

===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<ref name="barbeau" />
::<math>\frac{\text{ C}(c,\lambda/\mu)}{c \mu - \lambda} + \frac{1}{\mu}.</math>

====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.<ref>{{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 | accessdate = August 7, 2012 }}</ref>

====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 <math>\frac{c\mu}{n}</math> 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.<ref>{{cite doi|10.1080/15326349408807309}}</ref> An approximation has been offered for the response time time distribution.<ref>{{cite doi|10.1007/BF01150417}}</ref><ref>{{cite journal| first1=Jens | last1= Braband | first2= Rolf |last2 = Schassberger | title= Random Quantum Allocation: A New Approach to Waiting Time Distributions for M/M/N Processor Sharing Queues | booktitle= Messung, Modellierung und Bewertung von Rechen- und Kommunikationssystemen: 7. ITG/GI-Fachtagung | location= Aachen | date=21–23 September 1993 | editor= B. Walke and O. Spaniol | publisher = Springer | pages= 130–142 | isbn=3540572015}}</ref>

==Finite capacity==

In an M/M/''c''/''K'' queue (sometimes known as the Erlang–A model<ref name="gautam" />{{rp|495}}) only ''K'' customers can queue at any one time (including those in service<ref name="kleinrock" />). Any further arrivals to the queue are considered "lost". We assume that ''K'' ≥ ''c''. The model has transition rate matrix
:<math>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}</math>
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.<ref name="gautam" />{{rp|495}}

===Transient analysis===
See Takács for a transient solution<ref>{{cite book | first=L.| last= Takács| authorlink =Lajos Takács| title = Introduction to the Theory of Queues | location= London| publisher= Oxford University Press|year= 1962|pages=12–21}}</ref> and Stadje for busy period results.<ref>{{cite doi|10.1016/0304-4149(94)00032-O}}</ref>

===Stationary analysis===
Stationary probabilities are given by<ref name="allen">{{cite book | title = Probability, Statistics, and Queueing Theory: With Computer Science Applications | first= Arnold O. | last = Allen | publisher= Gulf Professional Publishing | year = 1990 | isbn = 0120510510 | pages=679–680}}</ref>

:: <math>\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}{\mu^k c^k}\right]^{-1}</math>

:: <math>\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}
</math>
The average number of customers in the system is<ref name="allen" />
:: <math> \frac{\lambda}{\mu} + \pi_0 \frac{\rho (c\rho)^c}{(1-\rho)^2 c!}</math>
and number of average response time for a customer<ref name="allen" />
:: <math> \frac{1}{\mu} + \pi_0 \frac{\rho (c\rho)^c}{\lambda (1-\rho)^2 c!}.</math>

==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
::<math>\hat X_n(t) = \frac{X(nt) - \mathbb E(X(nt))}{\sqrt{n}}</math>
converges to a diffusion process.<ref name="gautam" />{{rp|490}}

# Fix ''μ'' and ''c'', increase ''λ'' and scale by ''n'' = 1/(1 − ''ρ'')2.
# Fix ''μ'' and ''ρ'', increase ''λ'' and ''c'', and scale by ''n'' = ''c''.
# Fix as a constant ''β'' where
::<math>\beta = (1-\rho)\sqrt{s}</math>
and increase ''λ'' and ''c'' using the scale ''n'' = ''c'' or ''n'' = 1/(1 − ''ρ'')2. This case is called the Halfin–Whitt regime.<ref>{{cite jstor|170115}}</ref>

==See also==

* [[Spectral expansion solution]]

==References==
{{Reflist}}

{{Queueing theory}}
{{Stochastic processes}}

{{DEFAULTSORT:M M c queue}}
[[Category:Stochastic processes]]
[[Category:Single queueing nodes]]

Induction plasma technology - Revision history

192.198.151.43: Spelling change later to latter