A single-server queue (M/M/1)

We consider what is perhaps the simplest and most tractable queueing model: a single-server queue with Poisson arrivals and exponential service times. This is called the M/M/1 queue.

Customers arrive according to a Poisson process with rate \lambda. Each job has a service requirement that is exponentially distributed with mean \mu^{-1}. The server works at unit speed.

Figure: M/M/1 queue.

Load

We define

\displaystyle \rho := \frac{\lambda}{\mu}

to be the load on the system. Jobs arrive at rate \lambda and require, on average, 1/\mu units of work. Thus, the load represents the amount of work arriving per unit time.

Since the server processes work at unit speed, a natural condition for stability is

\displaystyle \rho < 1

(This works for simple queues like the single-server queue, but more care is needed for networks.)

Kendall’s queueing notation

Kendall introduced a standard notation for queues:

\displaystyle A / B / n / c

where:

  • A — arrival process
  • B — service time distribution
  • n — number of servers
  • c — system capacity (if finite)

The values n and c can be 1, 2, \ldots, \infty.

The symbols A and B describe distributions:

  • M — memoryless (exponential)
  • D — deterministic
  • G — general (i.i.d.)

Kendall notation is widely used, especially for classical models.

M/M/1 queue: stationary distribution

Lemma. The number of jobs in an M/M/1 queue is a reversible Markov chain that is positive recurrent when \rho < 1. Its stationary distribution is geometric:

\displaystyle \pi_n = (1-\rho)\rho^n, \quad n = 0,1,2,\ldots

The expected number of jobs in the system is

\displaystyle \mathbb{E}[Q] = \frac{\rho}{1-\rho}

Proof.

The queue length evolves as a continuous-time Markov chain.

Figure: state transitions with rates \lambda (up) and \mu (down).

Using detailed balance,

\displaystyle \pi_n \mu = \pi_{n-1} \lambda

so

\displaystyle \pi_n = \rho \pi_{n-1} = \rho^2 \pi_{n-2} = \cdots = \rho^n \pi_0

To normalize, we require

\displaystyle \sum_{n=0}^{\infty} \pi_n = 1

so

\displaystyle \pi_0 \sum_{n=0}^{\infty} \rho^n = 1

Since

\displaystyle \sum_{n=0}^{\infty} \rho^n = \frac{1}{1-\rho} \quad \text{if } \rho < 1

we obtain

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

Finally,

\displaystyle \mathbb{E}[Q] = \sum_{n=0}^{\infty} n \pi_n = \frac{\rho}{1-\rho}

\square

Leave a comment