Erlang Link and The Infinite Server Queue

The Erlang link and M/M/$\infty$ queue are models in which jobs do not wait. In the Erlang link, jobs are lost when all servers are busy, while in the M/M/$\infty$ queue every job begins service immediately.

The Erlang Link

Consider a queueing system with $N$ servers in which a job is lost if all servers are busy. This is called an Erlang link.

We can think of this as a model of telephone lines, where only one call can use each line at a time. Alternatively, we might think of a plumbing company that loses business whenever all its plumbers are busy.

Assuming Poisson arrivals with rate $\lambda$ and independent exponential service times with mean $\mu^{-1}$ , this is an M/M/N/N queue in Kendall’s notation. We write $\rho=\lambda/\mu$ for the offered load.

We are interested in the probability that an arriving job is lost.

Proposition

The stationary distribution of the number of jobs in the M/M/N/N queue is

$\displaystyle \pi_n=\frac{\frac{\rho^n}{n!}}{\displaystyle\sum_{i=0}^{N}\frac{\rho^i}{i!}},\qquad 0\leq n\leq N.$

Thus, the probability that an incoming job is lost is

$\displaystyle E(\rho,N)=\frac{\frac{\rho^N}{N!}}{\displaystyle\sum_{i=0}^{N}\frac{\rho^i}{i!}}.$

This is called the Erlang B formula. The expected number of jobs in the system is

$\displaystyle \mathbb E[Q]=\rho\bigl(1-E(\rho,N)\bigr).$

Proof

The queue-size process is a continuous-time Markov chain. Its state space is $\{0,1,\ldots,N\}$ . The transition rate from state $n$ to state $n+1$ is $\lambda$ for $n<N$ , while the transition rate from state $n$ to state $n-1$ is $n\mu$ .

The detailed balance equations give

$\displaystyle n\mu\pi_n=\lambda\pi_{n-1},\qquad 1\leq n\leq N.$

Therefore,

$\displaystyle \pi_n=\frac{\rho}{n}\pi_{n-1}=\frac{\rho^2}{n(n-1)}\pi_{n-2}=\cdots=\frac{\rho^n}{n!}\pi_0.$

Since the probabilities sum to one,

$\displaystyle \pi_0^{-1}=\sum_{i=0}^{N}\frac{\rho^i}{i!}.$

This gives the stated stationary distribution. By the PASTA property, an arriving job sees the stationary distribution. It is therefore lost with probability $\pi_N$ , which gives the Erlang B formula.

Finally, jobs enter the system at the effective rate $\lambda[1-E(\rho,N)]$ . Since each accepted job has mean service time $1/\mu$ , Little’s Law gives

$\displaystyle \mathbb E[Q]=\frac{\lambda[1-E(\rho,N)]}{\mu}=\rho[1-E(\rho,N)].$

This proves the result.

□

The Infinite-Server Queue (M/M/∞)

We do not need to restrict the number of servers to be finite. Letting the number of servers tend to infinity in the preceding stationary distribution gives the following result.

Corollary

For the M/M/∞ queue, the number of jobs in the system has a Poisson distribution with mean $\rho=\lambda/\mu$ . In particular,

$\displaystyle \mathbb P(Q=n)=e^{-\rho}\frac{\rho^n}{n!},\qquad n=0,1,2,\ldots,$

and

$\displaystyle \mathbb E[Q]=\rho.$

This reflects the fact that every job begins service immediately and then evolves independently of the other jobs.