In queueing theory, a discipline within the mathematical theory of probability, an M/M/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service times have an exponential distribution. The model name is written in Kendall's notation. The model is the most elementary of queueing models[1] and an attractive object of study as closed-form expressions can be obtained for many metrics of interest in this model. An extension of this model with more than one server is the M/M/c queue.
An M/M/1 queue is a stochastic process whose state space is the set where the value corresponds to the number of customers in the system, including any currently in service.
The model can be described as a continuous time Markov chain with transition rate matrix
Q=\begin{pmatrix} -λ&λ\\ \mu&-(\mu+λ)&λ\\ &\mu&-(\mu+λ)&λ\\ &&\mu&-(\mu+λ)&λ&\\ &&&&\ddots \end{pmatrix}
on the state space . This is the same continuous time Markov chain as in a birth–death process. The state space diagram for this chain is as below.
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[2]
| i. | |
| \pi | |
| i=(1-\rho)\rho |
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 − ρ)2. This result holds for any work conserving service regime, such as processor sharing.[3]
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[4] [5] [6] [7]
| f(t)=\begin{cases} | 1 |
| t\sqrt{\rho |
where I1 is a modified Bessel function of the first kind,[8] obtained by using Laplace transforms and inverting the solution.[9]
The Laplace transform of the M/M/1 busy period is given by[10] [11] [12]
E(e-s)=
| 1 | |
| 2λ |
(λ+\mu+s-\sqrt{(λ+\mu+s)2-4λ\mu})
which gives the moments of the busy period, in particular the mean is 1/(μ − λ) and variance is given by
| |||||||||
|
.
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 + μ − λ)[13] and therefore probability density function[14]
f(t)= \begin{cases} (\mu-λ)e-(\mu-λ)t&t>0\\ 0&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.[15] 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.[16] The waiting time distribution (response time less service time) for a customer requiring x amount of service has transform
W\ast(s|x)=
| (1-\rho)(1-\rhor2)e-[λ(1-r)+s]x | |
| (1-\rhor2)-\rho(1-r)2e-(\mu/r-λ |
where r is the smaller root of the equation
λr2-(λ+\mu+s)r+\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 pk(t) for the probability of being in state k at time t. Then[17] [18]
| -(λ+\mu)t | |
| p | |
| k(t)=e |
\left[
| ||||
| \rho |
Ik-i(at)+
| ||||
| \rho |
Ik+i+1(at)+(1-\rho)\rhok
| infty | |
| \sum | |
| j=k+i+2 |
\rho-j/2Ij(at)\right]
where
i
t=0
\rho=λ/\mu
a=2\sqrt{λ\mu}
Ik
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.[20]