M/M/1 Queue

A {M/M/1} queue is a single-server queue with infinite buffer where both the interarrival and service times follow exponential distributions. Let {\{Z(t):t\geqslant0\}} be the number of customers in the system at time {t}, with the assumption that {Z(0)=0} (the system is initially empty). The jump times

\displaystyle X_{n+1} = \inf\{t>X_n:Z(t)\ne \lim_{\tau\uparrow t}Z(\tau) \}

(with {X_0=0}) are exponentially distributed, so {Z(t)} is a continuous-time Markov chain with embedded Markov chain {Z(X_n)}. Let {\lambda} be the arrival rate and {\mu} the service rate, with {\lambda<\mu}. Then the global balance equations for the stationary distribution are

\displaystyle  \begin{aligned} \lambda\pi_0 &= \mu\pi_1\\ (\lambda+\mu)\pi_n &= \lambda\pi_{n-1}+\mu\pi_{n+1}, n\geqslant 1. \end{aligned}

The solution to this recurrence is

\displaystyle  \pi_n = (1-\rho)\rho^n,

where {\rho=\frac\lambda\mu}. From here it follows that the mean number of customers in the system is

\displaystyle \mathbb E[L] = \sum_{n=1}^\infty n(1-\rho)\rho^n = \frac{\rho(1-\rho)}{(1-\rho)^2}=\frac\rho{1-\rho}.

The mean time in system, or mean sojourn time, satisfies

\displaystyle \mathbb E[S]=\frac1\mu(1+\mathbb E[L])= \frac1\mu + \frac\rho{\mu(1-\rho)}=\frac1{\mu(1-\rho)},

as on average there will be {\mathbb E[L]} customers in the queue when a customer arrives, and so the customer is in the system for {\mathbb E[L]+1} service times. Note that

\displaystyle \mathbb E[L] = \frac\rho{1-\rho} = \lambda\left(\frac1{\mu(1-\rho)} \right)=\lambda\mathbb E[S].

This equality is known as Little’s Law.

To compute the distribution of the sojourn time, let {L^a} be the number of customers in the system immediately before an arrival, and {W_k} the service time of the {k^{\mathrm{th}}} customer. It follows that

\displaystyle S=\sum_{k=1}^{L^a+1}W_k.

Conditioning on {L^a} yields

\displaystyle  \begin{aligned} 	\mathbb P(S>t) &= \sum_{n=0}^\infty \mathbb P(S>t\mid L^a=n)\mathbb P(L^a=n)\\ 	&=\sum_{n=0}^\infty \mathbb P\left(\sum_{k=1}^{L^a+1}W_k>t\mid L^a=n \right)\mathbb P(L^a=n)\\ \end{aligned}

PASTA (Poisson Arrivals See Time Average) yields

\displaystyle \mathbb P(L^a = n) = \pi_n = (1-\rho)\rho^n,

and so

\displaystyle  \begin{aligned} \mathbb P(S>t) &= \sum_{n=0}^\infty \sum_{k=0}^n \frac{(\mu t)^k}{k!}e^{-\mu t}(1-\rho)\rho^n\\ &= \sum_{k=0}^\infty \frac{(\mu t)^k}{k!}e^{-\mu t}(1-\rho)\sum_{n=k}^\infty \rho^n\\ &= \sum_{k=0}^\infty \frac{(\mu t)^k}{k!}e^{-\mu t}\rho^k\\ &= e^{-\mu t} \sum_{k=0}^\infty \frac{(\mu\rho t)^k}{k!}\\ &= e^{-\mu(1-\rho)t}. \end{aligned}

It follows that {S\sim\mathrm{Exp}(\mu(1-\rho))}.

To compute the distribution of the time waiting in queue {W_q}, we have

\displaystyle W_q = W_q\mathsf 1_{W_q>0} + W_q\mathsf 1_{W_q=0}.

Since {W_q=0} iff {L^a=0}, it follows that {\mathbb P(W_q=0)=1-\rho}, and that {W_q\mid L^a>0\stackrel d= W}. Therefore the density of {W_q} is

\displaystyle w_q(t) = (1-\rho)\mathsf 1_{L^a=0} + e^{-\mu(1-\rho)t}\mathsf 1_{L^a>0}.

The next item of interest is the busy period of the system. Let {\tau_1=T_1}, {\sigma_1=0} and for {n\geqslant 1}

\displaystyle  \begin{aligned} \sigma_n &= \inf\{t>\tau_n:Z(t)=0 \}\\ \tau_{n+1} &= \inf\{t>\sigma_n:Z(t)=1 \}\\ \end{aligned}

The busy periods are the time intervals where {Z(t)=1}, that is, {(\tau_n, \sigma_n)}, and the idle periods {Z(t)=0} or {(\sigma_n,\tau_{n+1})}. The sequences {\{\tau_n:n\geqslant1 \}}, {\sigma_n\{n\geqslant 1 \}} define an alternating renewal process, and by the renewal reward theorem,

\displaystyle  \lim_{t\rightarrow\infty}\mathbb P(Z(t)=1)=\frac{\mathbb E[\sigma_n-\tau_n]}{\mathbb E[\sigma_n-\tau_n]+\mathbb E[\tau_{n+1}-\sigma_n]}

Now, the mean idle time is simply the mean interarrival time, so {\mathbb E[\tau_{n+1}-\sigma_n]=\frac1\lambda}, and the limit above is equal to the utilization of the server. It follows that

\displaystyle \frac{\mathbb E[\sigma_n-\tau_n]}{\mathbb E[\sigma_n-\tau_n]+\frac1\lambda} =\rho\implies \mathbb E[\sigma_n-\tau_n]=\frac1{\mu(1-\rho)}.

The distribution of the busy period can be written in terms of modified Bessel functions, i.e.

\displaystyle I_k(z) := \sum_{i=0}^\infty \frac{\left(\frac z2\right)^{k+2i}}{i!\Gamma(k+i+1)},

with {\mathbb P(Z(t)=n)} given by

\displaystyle e^{-(\lambda+\mu)t}\left(\rho^{\frac{n-i}2} I_{n-i}(2\sqrt{\lambda\mu t})+\rho^{n-i-1/2}I_{n+i+1}(2\sqrt{\lambda\mu t})\right) +e^{(\lambda+\mu)t}(1-\rho)\rho^n\sum_{k=i+2}^\infty \rho^{-\frac k2}I_k(2\sqrt{\lambda \mu t}).

(See “{M/M/1} Transient Queue length distribution” here for the derivation.)

One final consideration is the departure distribution of the queue. The probability that an arbitrary departing customer leaves behind an empty system is {\pi_1=1-\rho}, and the time until the next departure is the sum of an interarrival time and a service time. Otherwise, the time until the next departure is a service time. It follows that the interdeparture distribution has density

\displaystyle f_D(t) = (1-\rho)\frac{\lambda\mu}{\lambda-\mu}(e^{-\mu t}-e^{-\lambda t}) +\rho\mu e^{-\mu t} = \lambda e^{-\lambda t},

the same as that of the interarrival distribution. In fact, for each {n\geqslant0} we have

\displaystyle  \begin{aligned} \pi_n P_{n,n+1} &= (1-\rho)\rho^n\left(\frac{\lambda}{\lambda+\mu}\right)\\ &= (1-\rho)\rho^{n+1}\left(\frac{\mu}{\lambda+\mu}\right)\\ &= \pi_{n+1} P_{n+1,n}, \end{aligned}

so the M/M/1 queue is a time-reversible stochastic process. Since the arrival times in the original process are the departure times in the reversed process, the departure process is also a Poisson process with rate {\lambda}.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s