Performance Measures for the M/M/c Queue

From Erlang C to Mean Performance

For a multi-server queue, a delay probability alone does not describe the typical customer experience. Two systems can have similar probabilities of delay but different queue lengths, waiting times, and service capacities. In a stable M/M/c queue, the Erlang C probability connects directly to the mean number waiting; Little’s law then converts that mean into waiting time. Keeping the customer flow rate distinct from total service capacity is essential.

Consider a queue on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Arrivals form a Poisson process of rate \(\lambda>0\). There are \(c\ge1\) parallel servers, each with independent exponential service times of rate \(\mu>0\). The queue has unlimited waiting space, and arrivals are served in order of arrival. Let \(N_t\) be the number of customers in the system at time \(t\), with state space \(S=\{0,1,2,\ldots\}\); use the natural filtration \(\mathcal{F}_t=\sigma(N_s:0\le s\le t)\). The model is considered in its stationary regime.

Write \(a=\lambda/\mu\) for the offered load and \(\rho=\lambda/(c\mu)=a/c\) for utilization. The stability condition is \(\rho<1\), equivalently \(\lambda<c\mu\). Let \(\pi_n=\mathbb{P}(N_t=n)\) in stationarity. The stationary probabilities are

These probabilities give the Erlang C delay probability, denoted \(C\): it is the stationary probability that an arriving customer finds all \(c\) servers occupied and must wait. For a Poisson arrival process, arrivals see the stationary state probabilities (the PASTA property), so

In what follows, the mean queue length \(L_q\) counts only customers waiting, and the mean system size \(L\) counts both waiting and in service. The mean waiting time \(W_q\) ends when service begins; the mean time in system \(W\) includes service.

Mean Queue Length and the Geometric Tail

When the system has at least \(c\) customers, every additional customer is waiting. The stationary probability of having \(c+k\) customers is \(\pi_c\rho^k\) for \(k\ge0\). Since \(C=\sum_{k\ge0}\pi_c\rho^k=\pi_c/(1-\rho)\), the conditional excess above \(c\), given that all servers are occupied, has a geometric tail. The mean number waiting is therefore obtained from a weighted geometric sum.

Proof. Put \(S=\sum_{k\ge0}k\rho^k\), which converges because \(0\le\rho<1\). Reindexing the product \(\rho S\) gives \(\rho S=\sum_{k\ge1}(k-1)\rho^k\), so

Thus \(S=\rho/(1-\rho)^2\). In state \(c+k\), the number waiting is \(k\), and in states below \(c\) it is zero. Hence \(L_q=\sum_{k\ge0}k\pi_c\rho^k=\pi_c\rho/(1-\rho)^2\). Substituting \(\pi_c=C(1-\rho)\) yields \(L_q=C\rho/(1-\rho)\).

To find the mean number in service, note that in state \(n\) there are \(\min(n,c)\) busy servers. Stationary flow balance across the set of states \(\{0,\ldots,n\}\) gives \(\pi_n\lambda=\pi_{n+1}\mu\min(n+1,c)\): upward crossings occur from \(n\) at rate \(\lambda\), and downward crossings from \(n+1\) at rate \(\mu\min(n+1,c)\). Summing over \(n\ge0\), and using \(\min(0,c)=0\), gives \(\lambda=\mu\sum_{m\ge0}\pi_m\min(m,c)\). Thus the mean number in service is \(\lambda/\mu=a\), and \(L=L_q+a\).

Finally, Little’s law states that in a stable stationary system with finite mean queue or system size and a well-defined long-run customer flow rate, mean number equals arrival rate times mean time in that part of the system. Applying it to the waiting line and to the whole system gives \(L_q=\lambda W_q\) and \(L=\lambda W\). A customer’s time in the system is their waiting time plus their service time. The exponential service rate \(\mu\) gives mean service time \(1/\mu\); therefore \(W=W_q+1/\mu\). These equations prove the stated formulas. \(\square\)

The restriction \(\rho<1\) matters: it makes the stationary geometric tail summable and gives a finite steady-state mean. At \(\rho\ge1\), these stationary performance formulas do not apply to the unlimited-capacity M/M/c queue.

Rates, Interpretation, and Common Errors

The rate in Little’s law is the rate at which customers enter the system. In this stable, unlimited-capacity queue, every arrival eventually receives service, so the long-run customer throughput equals \(\lambda\). The quantity \(c\mu\) is the maximum total service capacity when all servers are busy; it is not the customer arrival rate. Using it in place of \(\lambda\) when converting \(L_q\) to \(W_q\) gives the wrong answer.

For example, in the two-server calculation above, the incorrect substitution \(W_q=L_q/(c\mu)\) gives \((27/14)/4=27/56\). The correct calculation is \(W_q=L_q/\lambda=(27/14)/3=9/14\). The incorrect value would also fail the defining relation \(L_q=\lambda W_q\), since \(3\cdot27/56=81/56\ne27/14\).

A second frequent error is to confuse mean queue length with mean system size. \(L_q\) excludes customers in service; \(L\) includes them. Their difference is the mean number in service, \(\lambda/\mu=a\), not the number of servers \(c\) in every state. The system may have idle servers, so adding \(c\) to \(L_q\) overcounts service occupancy unless all servers are always busy.

Finally, the Erlang C probability is a probability of waiting, not a mean queue length. The conversion \(L_q=C\rho/(1-\rho)\) uses the geometric tail of the stationary number waiting, and requires \(\rho<1\). As utilization approaches one from below, the factor \(\rho/(1-\rho)\) grows; a modest change in delay probability can therefore accompany a substantial change in expected queue length and waiting time.