Waiting-Time Distribution in the M/M/c Queue

What the Waiting-Time Distribution Describes

In an M/M/c queue, an arriving customer may begin service immediately or wait for one or more service completions. The waiting time therefore has two parts in its distribution: a point mass at zero, and a continuous tail for positive times. Under first-come, first-served (FCFS) service, that tail has a particularly simple form in steady state: conditional on having to wait, the waiting time is exponential.

Assume \(c\) is a positive integer, arrivals form a Poisson process of rate \(\lambda>0\), and each of the \(c\) servers provides independent exponential service times of rate \(\mu>0\). Customers are served FCFS, with no abandonment or preemption. We require stability, \(\lambda<c\mu\), and consider the queue in its stationary regime. Let \(W\) denote the time from a typical arrival until service begins; it does not include that customer’s service time. Write \(a=\lambda/\mu\) and \(\eta=\lambda/(c\mu)\), so \(0<\eta<1\).

We use PASTA (Poisson arrivals see time averages): in steady state, the number of customers an arriving Poisson customer finds in the system has the stationary distribution of the system size. This is the standard PASTA result; its proof is not developed here. The stationary M/M/c probabilities, established in the earlier material on the stationary distribution, are proportional to \(a^n/n!\) for \(0\le n<c\), and to \((a^c/c!)\eta^{n-c}\) for \(n\ge c\). Normalizing these probabilities gives the Erlang C probability \(C\) that an arrival must wait:

Here \(C\) is strictly between zero and one under the stated assumptions. The numerator is the stationary probability weight of finding at least \(c\) customers, and the denominator is the total weight of all system sizes.

How Many Customers Are Ahead?

Proof. An arrival waits exactly when it finds at least \(c\) customers in the system. If it finds \(c+k\), then all \(c\) servers are busy and \(k\) customers are already waiting ahead of it. By the stationary probabilities and PASTA, the probability weight of finding \(c+k\) is proportional to \((a^c/c!)\eta^k\). The total weight over all such states is \((a^c/c!)\sum_{\ell=0}^{\infty}\eta^\ell=(a^c/c!)/(1-\eta)\), since \(0<\eta<1\). Dividing the weight for \(k\) by this total gives \((1-\eta)\eta^k\), as claimed. These probabilities sum to \((1-\eta)\sum_{k=0}^{\infty}\eta^k=1\). \(\square\)

The index \(k\) counts customers waiting ahead, not customers in service. When \(K=k\), the new arrival must wait for \(k+1\) service completions before a server becomes available: the \(k\) customers ahead must start service first, and then the tagged customer starts. During this interval all servers remain busy. Because exponential service times are memoryless, the next completion occurs at rate \(c\mu\): it is the minimum of \(c\) independent exponential residual service times of rate \(\mu\). After a completion, a waiting customer immediately takes the freed server, so the same rate applies until the tagged customer begins service. Thus, conditional on \(K=k\), \(W\) is the sum of \(k+1\) independent exponential times of rate \(c\mu\), an Erlang waiting time.

The Waiting-Time Law

Proof. Set \(r=c\mu\). Conditional on \(K=k\), the waiting time is Erlang with \(k+1\) stages of rate \(r\). Its survival probability is \(\mathbb{P}(W>t\mid K=k)=e^{-rt}\sum_{j=0}^{k}(rt)^j/j!\) for \(t\ge0\). To verify this formula, the Erlang density is \(r^{k+1}u^k e^{-ru}/k!\) for \(u\ge0\). For \(k=0\), integrating the density from \(t\) to infinity gives \(e^{-rt}\). For \(k\ge1\), integration by parts gives the survival probability for \(k\) as \(e^{-rt}(rt)^k/k!\) plus the survival probability for \(k-1\). Starting from \(k=0\), this recurrence yields the stated finite sum.

Now condition on the event \(W>0\), for which the proposition gives the probabilities of \(K\). For \(t\ge0\), all terms in the following sums are nonnegative, so their order may be interchanged:

In the third equality, the inner geometric sum is \((1-\eta)\eta^j/(1-\eta)=\eta^j\); in the last, \(r\eta=c\mu\cdot\lambda/(c\mu)=\lambda\). Since the probability of waiting is \(C\), multiplication by \(C\) gives \(\mathbb{P}(W>t)=Ce^{-(c\mu-\lambda)t}\). At \(t=0\), this gives \(\mathbb{P}(W>0)=C\), so the remaining probability \(1-C\) is the mass at zero. Dividing the positive-time tail by \(\mathbb{P}(W>0)=C>0\) gives the conditional exponential law. \(\square\)

Equivalently, the distribution function is zero for \(t<0\) and \(1-Ce^{-(c\mu-\lambda)t}\) for \(t\ge0\). At \(t=0\) it equals \(1-C\), rather than zero, because that value includes the atom for immediate service. For \(t>0\), the density is \(C(c\mu-\lambda)e^{-(c\mu-\lambda)t}\). The atom and density together account for the whole distribution: the atom has mass \(1-C\), and the density integrates over positive times to \(C\).

Worked Calculations

Why the Conditional Rate Is Not \(c\mu\)

A common mistake is to say that, because \(c\) busy servers complete service at combined rate \(c\mu\), the conditional waiting time must be exponential with rate \(c\mu\). This calculation treats every waiting arrival as if it needed only one completion. In fact, the number of customers ahead is random. If there are \(k\) customers waiting ahead, the arrival must wait for \(k+1\) completions; mixing these Erlang waiting times changes the tail.

For the third example, the incorrect rate would be \(c\mu=2\), giving a conditional tail \(e^{-2t}\). The correct rate is \(c\mu-\lambda=1/2\). At \(t=1\), the incorrect conditional tail is \(e^{-2}\), while the correct one is \(e^{-1/2}\); these are different because the former omits the random queueing position. The proof above shows exactly how that random position, with its geometric distribution, produces the correct exponential rate.

The condition \(\lambda>0\) ensures \(C>0\), so conditioning on \(W>0\) is meaningful. If \(\lambda=0\), there are no waiting arrivals in steady state and a conditional distribution given \(W>0\) is undefined. Stability also matters: the formula here is a stationary waiting-time law and requires \(\lambda<c\mu\). It does not describe a queue whose load is at or above its total service capacity.