M/M/1 queue

An M/M/1 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 rate parameter μ in the M/M/1 queue, where 1/μ is the mean service time.
• All arrival times and services times are (usually) assumed to be independent of one another.
• A single server serves customers one at a time from the front of the queue, according to a first-come, first-served discipline. When the service is complete the customer leaves the queue and the number of customers in the system reduces by one.
• 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=\backslash begin\{pmatrix\}$

-\lambda & \lambda \\

\mu & -(\mu+\lambda) & \lambda \\

&\mu & -(\mu+\lambda) & \lambda \\

&&\mu & -(\mu+\lambda) & \lambda &\\

&&&&\ddots

\end{pmatrix}

on the state space {0,1,2,3,...}. This is the same continuous time Markov chain as in a birth–death process. The state space diagram for this chain is as below.

File:MM1 queue state space.svg

The model is considered stable only if λ < μ. If, on average, arrivals happen faster than service completions the queue will grow indefinitely long and the system will not have a stationary distribution. The stationary distribution is the limiting distribution for large values of t.

Various performance measures can be computed explicitly for the M/M/1 queue. We write ρ = λ/μ for the utilization of the buffer and require ρ < 1 for the queue to be stable. ρ represents the average proportion of time which the server is occupied.

The probability that the stationary process is in state i (contains i customers, including those in service) is{{cite book|first=Peter|last=Harrison|author-link=Peter G. Harrison|first2=Naresh M.|last2=Patel|title=Performance Modelling of Communication Networks and Computer Architectures|url=https://archive.org/details/performancemodel0000harr|url-access=registration|publisher=Addison–Wesley|year=1992}}{{rp|172–173}}

: $\backslash pi\_i=(1-\backslash rho)\backslash rho^i.\backslash ,$

We see that the number of customers in the system is geometrically distributed with parameter 1 − ρ. Thus the average number of customers in the system is ρ/(1 − ρ) and the variance of number of customers in the system is ρ/(1 − ρ)². This result holds for any work conserving service regime, such as processor sharing.{{Cite journal | last1 = Guillemin | first1 = F. | last2 = Boyer | first2 = J. | journal = Queueing Systems | title = Analysis of the M/M/1 Queue with Processor Sharing via Spectral Theory | volume = 39 | issue = 4 | pages = 377 | year = 2001 | doi = 10.1023/A:1013913827667 | url = http://perso.rd.francetelecom.fr/guillemin/PDFfiles/gps.pdf | url-status = dead | archive-url = https://web.archive.org/web/20061129234117/http://perso.rd.francetelecom.fr/guillemin/PDFfiles/gps.pdf | archive-date = 2006-11-29 }}

The busy period is the time period measured between the instant a customer arrives to an empty system until the instant a customer departs leaving behind an empty system. The busy period has probability density function{{Cite journal | last1 = Abate | first1 = J. | last2 = Whitt | first2 = W. | author-link2 = Ward Whitt| doi = 10.1007/BF01157854 | title = Simple spectral representations for the M/M/1 queue | journal = Queueing Systems| volume = 3 | issue = 4 | pages = 321 | year = 1988 | url = http://www.columbia.edu/~ww2040/SimpleSpectralMM1.pdf}}{{cite journal | first1 = J. | last1 = Keilson | first2 = A. | last2 = Kooharian | year = 1960 | title = On Time Dependent Queuing Processes | journal = The Annals of Mathematical Statistics | volume = 31 | issue = 1 | pages = 104–112 | jstor = 2237497 | doi=10.1214/aoms/1177705991| doi-access = free }}{{cite journal | title = Many server queueing processes with Poisson input and exponential service times | journal = Pacific J. Math. | first1= Samuel | last1 = Karlin | author-link1 = Samuel Karlin | first2= James | last2= McGregor | volume = 8 | issue = 1 | year = 1958 | pages = 87–118 | mr = 0097132 | doi = 10.2140/pjm.1958.8.87| url = http://msp.org/pjm/1958/8-1/pjm-v8-n1-p08-s.pdf | doi-access = free }}{{cite book | chapter = 2.12 Busy-Period Analysis | title = Fundamentals of Queueing Theory | publisher=Wiley | first1=Donald | last1=Gross | first2= John F. | last2 = Shortle | first3= James M. | last3=Thompson | first4=Carl M.| last4=Harris| isbn=1118211642| date = 2011-09-23 }}

::$f(t)=\backslash begin\{cases\}$

\frac{1}{t\sqrt{\rho}}e^{-(\lambda+\mu)t}I_1(2t\sqrt{\lambda\mu}) & t>0\\

0 & \text{otherwise}\end{cases}

where I₁ is a modified Bessel function of the first kind,{{cite web|title=Course QUE: Queueing Theory, Fall 2003: The M/M/1 system| first = Ivo | last=Adan | url=http://www.win.tue.nl/~iadan/que/h4.pdf|access-date=2012-08-06}} obtained by using Laplace transforms and inverting the solution.{{cite book|title=Probability, Markov chains, queues, and simulation: the mathematical basis of performance modeling|url=https://archive.org/details/probabilitymarko00stew|url-access=limited|page=[https://archive.org/details/probabilitymarko00stew/page/n548 530]|first=William J.|last=Stewart|publisher=Princeton University Press|year=2009|isbn=978-0-691-14062-9}}

The Laplace transform of the M/M/1 busy period is given by{{Cite book | doi = 10.1007/0-387-21525-5_3 | first1 = S. R. | last1 = Asmussen| chapter = Queueing Theory at the Markovian Level | title = Applied Probability and Queues | series = Stochastic Modelling and Applied Probability | volume = 51 | pages = 60–31 | year = 2003 | isbn = 978-0-387-00211-8 }}{{Cite journal | last1 = Adan | first1 = I. | last2 = Resing | first2 = J. | doi = 10.1007/BF01159399 | title = Simple analysis of a fluid queue driven by an M/M/1 queue | journal = Queueing Systems| volume = 22 | issue = 1–2 | pages = 171–174 | year = 1996 }}{{cite book | title = Queueing Systems: Theory, Volume 1 | url = https://archive.org/details/queueingsystems02klei | url-access = registration | first1 = Leonard | last1 = Kleinrock | author-link1 = Leonard Kleinrock | publisher = Wiley | year = 1975 | isbn = 0471491101 }}{{rp|215}}

::$\backslash mathbb\; E(\; e^\{-s\; F\}\; )=\; \backslash frac\{1\}\{2\; \backslash lambda\}(\backslash lambda\; +\; \backslash mu\; +\; s\; -\; \backslash sqrt\{(\backslash lambda\; +\; \backslash mu\; +\; s)^2\; -\; 4\; \backslash lambda\; \backslash mu\})$

which gives the moments of the busy period, in particular the mean is 1/(μ − λ) and variance is given by

::$\backslash frac\{1\}\{\backslash mu^2(1-\backslash rho)^2\}.$

The average response time or sojourn time (total time a customer spends in the system) does not depend on scheduling discipline and can be computed using Little's law as 1/(μ − λ). The average time spent waiting is 1/(μ − λ) − 1/μ = ρ/(μ − λ). The distribution of response times experienced does depend on scheduling discipline.

For customers who arrive and find the queue as a stationary process, the response time they experience (the sum of both waiting time and service time) has Laplace transform

(μ − λ)/(s + μ − λ){{Cite book | last1 = Harrison | first1 = P. G. | chapter = Response time distributions in queueing network models | doi = 10.1007/BFb0013852 | title = Performance Evaluation of Computer and Communication Systems | series = Lecture Notes in Computer Science | volume = 729 | pages = 147–164 | year = 1993 | isbn = 3-540-57297-X }} and therefore probability density function{{cite book|title=Probability, Markov chains, queues, and simulation: the mathematical basis of performance modeling|url=https://archive.org/details/probabilitymarko00stew|url-access=limited|page=[https://archive.org/details/probabilitymarko00stew/page/n427 409]|first=William J.|last=Stewart|publisher=Princeton University Press|year=2009|isbn=978-0-691-14062-9}}

::$f(t)=$

\begin{cases}

(\mu-\lambda)e^{-(\mu-\lambda)t} & t>0\\

0 & \text{otherwise.}

\end{cases}

In an M/M/1-PS queue there is no waiting line and all jobs receive an equal proportion of the service capacity.{{Cite journal | last1 = Coffman | first1 = E. G. | author-link = Edward G. Coffman, Jr.| last2 = Muntz | first2 = R. R. | last3 = Trotter | first3 = H. | author-link3 = Hale Trotter | title = Waiting Time Distributions for Processor-Sharing Systems | doi = 10.1145/321556.321568 | journal = Journal of the ACM| volume = 17 | pages = 123–130 | year = 1970 | doi-access = free }} Suppose the single server serves at rate 16 and there are 4 jobs in the system, each job will experience service at rate 4. The rate at which jobs receive service changes each time a job arrives at or departs from the system.

For customers who arrive to find the queue as a stationary process, the Laplace transform of the distribution of response times experienced by customers was published in 1970, for which an integral representation is known.{{Cite journal | last1 = Morrison | first1 = J. A. | doi = 10.1137/0145007 | title = Response-Time Distribution for a Processor-Sharing System | journal = SIAM Journal on Applied Mathematics| volume = 45 | issue = 1 | pages = 152–167 | year = 1985 | jstor = 2101088}} The waiting time distribution (response time less service time) for a customer requiring x amount of service has transform{{rp|356}}

:$W^\backslash ast(s|x)\; =\; \backslash frac\{(1-\backslash rho)(1-\backslash rho\; r^2)e^\{-[\backslash lambda(1-r)+s]x\}\}\{(1-\backslash rho\; r^2)-\backslash rho(1-r)^2e^\{-(\backslash mu/r-\backslash lambda\; r)x\}\}$

where r is the smaller root of the equation

:$\backslash lambda\; r^2\; -\; (\backslash lambda\; +\; \backslash mu\; +\; s)r\; +\; \backslash mu\; =\; 0.$

The mean response time for a job arriving and requiring amount x of service can therefore be computed as x μ/(μ − λ). An alternative approach computes the same results using a spectral expansion method.

We can write a probability mass function dependent on t to describe the probability that the M/M/1 queue is in a particular state at a given time. We assume that the queue is initially in state i and write p_k(t) for the probability of being in state k at time t. Then{{cite book | title = Queueing Systems Volume 1: Theory | first1=Leonard | last1=Kleinrock | author-link = Leonard Kleinrock | isbn = 0471491101 | year=1975 | page=77}}{{cite book | last=Robertazzi | first=Thomas G. | title=Computer Networks and Systems | publisher=Springer New York | publication-place=New York, NY | year=2000 |page=72 | isbn=978-1-4612-7029-4 | doi=10.1007/978-1-4612-1164-8}}

::$p\_k(t)=e^\{-(\backslash lambda+\backslash mu)t\}\; \backslash left[\; \backslash rho^\{\backslash frac\{k-i\}\{2\}\}\; I\_\{k-i\}(at)\; +\; \backslash rho^\{\backslash frac\{k-i-1\}\{2\}\}\; I\_\{k+i+1\}(at)\; +\; (1-\backslash rho)\; \backslash rho^\{k\}\; \backslash sum\_\{j=k+i+2\}^\{\backslash infty\}\; \backslash rho^\{-j/2\}I\_j(at)\; \backslash right]$

where $i$ is the initial number of customers in the station at time $t=0$,$\backslash rho=\backslash lambda/\backslash mu$, $a=2\backslash sqrt\{\backslash lambda\backslash mu\}$ and $I\_k$ is the modified Bessel function of the first kind. Moments for the transient solution can be expressed as the sum of two monotone functions.{{Cite journal | last1 = Abate | first1 = J. | last2 = Whitt | first2 = W. | author-link2 = Ward Whitt| doi = 10.1007/BF01182933 | title = Transient behavior of the M/M/l queue: Starting at the origin | journal = Queueing Systems| volume = 2 | pages = 41–65 | year = 1987 | url = http://www.columbia.edu/~ww2040/TransientMM1questa.pdf}}

When the utilization ρ is close to 1 the process can be approximated by a reflected Brownian motion with drift parameter λ – μ and variance parameter λ + μ. This heavy traffic limit was first introduced by John Kingman.{{Cite journal | last1 = Kingman | first1 = J. F. C. | author-link = John Kingman| doi = 10.1017/S0305004100036094 | title = The single server queue in heavy traffic | journal = Mathematical Proceedings of the Cambridge Philosophical Society| volume = 57 | issue = 4 | pages = 902 | date=October 1961 | jstor = 2984229}}

{{Reflist}}

{{Queueing theory}}

{{Stochastic processes}}

{{DEFAULTSORT:M M 1 queue}}

Category:Single queueing nodes