Blocking Probability and Throughput in M/M/c/K

Offered Arrivals, Blocking, and Throughput

In a finite-capacity queue, an arrival can be offered service even when the system cannot admit it. If all $K$ places are occupied, the arrival is rejected; otherwise it joins the system. Thus the rate at which customers request entry need not equal the rate at which customers enter, or the rate at which service is completed. The distinction matters when interpreting a blocking probability or comparing the capacity of different systems.

Consider an M/M/c/K queue with $1\le c\le K$, Poisson offered arrivals at rate $\lambda>0$, and $c$ servers whose independent service times are exponential with rate $\mu>0$. The system capacity $K$ counts all customers in the system, both in service and waiting. On a probability space $(\Omega,\mathcal{F},\mathbb{P})$, let $(X_t)_{t\ge0}$ be the continuous-time Markov chain giving the number of customers in the system, with state space $S=\{0,1,\ldots,K\}$. Use the natural filtration $(\mathcal{F}_t)_{t\ge0}$, which records the arrivals and service completions through time $t$. An offered arrival is admitted when $X_{t-}<K$, and is blocked when $X_{t-}=K$.

Definition: In stationarity, the blocking probability $B$ is the fraction of offered arrivals that find the system full, equivalently the probability that a typical offered arrival is blocked. The effective arrival rate, or admitted throughput, is the mean rate of customers admitted to the system. It is not the offered rate $\lambda$.

Let $\pi_n=\mathbb{P}(X_t=n)$ when the queue is in its stationary distribution. The key quantity is $\pi_K$, the stationary probability of full occupancy. Because arrivals are Poisson and independent of the queue’s past, they do not preferentially occur at times when the queue is unusually full or unusually empty. This is the Poisson-arrivals-see-time-averages property (PASTA). For this finite-state queue, the property implies $B=\pi_K$.

Stationary Probabilities Needed for the Calculation

The birth rates of $X_t$ are $\lambda$ from states $0,\ldots,K-1$, and $0$ from state $K$. From state $n$, the total service-completion rate is $\mu\min(n,c)$. In particular, when $n\ge c$, the rate is $c\mu$, not $n\mu$, because only $c$ servers can be busy.

The stationary probabilities for this finite birth-death chain can be written using unnormalized weights. These weights are the standard stationary-distribution calculation for the M/M/c/K queue:

w_0=1,\qquad w_n= \begin{cases} \dfrac{(\lambda/\mu)^n}{n!},&0\le n\le c,\\[6pt] \dfrac{(\lambda/\mu)^n}{c!\,c^{\,n-c}},&c<n\le K, \end{cases} \qquad \pi_n=\frac{w_n}{\sum_{j=0}^{K}w_j}.

To see the rate relation behind this formula, adjacent states satisfy $\pi_n\lambda=\pi_{n+1}\mu\min(n+1,c)$ for $0\le n<K$. Starting with $w_0=1$, this gives $w_{n+1}=w_n\lambda/(\mu\min(n+1,c))$. Multiplying these successive ratios gives the displayed weights: the denominator accumulates $1,2,\ldots,n$ up to $c$, and then a factor $c$ for each additional state. Normalizing makes the probabilities sum to one. These relations also verify stationarity: at each interior state the incoming and outgoing probability rates balance, and the same adjacent-state relation balances the boundary states.

Theorem (Blocking and throughput): For a stationary M/M/c/K queue with $1\le c\le K$, $\lambda>0$, and $\mu>0$, the blocking probability is $B=\pi_K$. The effective arrival rate is $$ \lambda_{\mathrm{eff}}=\lambda(1-\pi_K), $$ and it also equals the stationary service-completion rate $$ \lambda_{\mathrm{eff}}=\mu\sum_{n=0}^{K}\pi_n\min(n,c). $$

Proof. First consider a time interval $[0,T]$ in stationarity, and count the offered arrivals that are blocked. Divide the interval into $m$ subintervals of length $h=T/m$. In one subinterval, conditional on its starting state, the expected number of blocked arrivals is $\lambda h$ if the starting state is $K$, up to an error bounded by a constant times $h^2$; if the starting state is not $K$, it is $0$ up to such an error. Indeed, an arrival is blocked if the state immediately before it is $K$. A discrepancy from using the state at the subinterval’s start requires at least two events in the subinterval, such as an arrival and a service completion. All event rates are bounded by $\lambda+c\mu$, so the probability of two or more events is bounded by a constant times $h^2$, uniformly over the finite state space. Thus the expected blocked count over one subinterval is $\lambda h\pi_K+O(h^2)$, since the starting state has stationary distribution. Summing over $m$ subintervals gives $\lambda T\pi_K+O(Th)$; letting $m$ increase makes $h$ tend to zero. The expected blocked count on $[0,T]$ is therefore $\lambda T\pi_K$. The expected offered count is $\lambda T$, so the blocked fraction of offered arrivals is $\pi_K$, proving $B=\pi_K$. The expected admitted count is the offered count minus the blocked count, hence its rate is $\lambda-\lambda\pi_K=\lambda(1-\pi_K)$.

For the service-completion identity, let $Q=(q_{ij})$ be the generator of the queue-length chain. For a function $f$ on the state space, $Qf(n)=\sum_j q_{nj}f(j)$. Take $f(n)=n$. A birth increases $f$ by one at rate $\lambda$ when $n<K$; a service completion decreases it by one at rate $\mu\min(n,c)$. Therefore $Qf(n)=\lambda\mathbf{1}_{\{n<K\}}-\mu\min(n,c)$. In stationarity, $\sum_n\pi_nQf(n)=0$: this follows from $\pi Q=0$, the stationary generator equation for a finite-state continuous-time Markov chain. Consequently, $\lambda\sum_{n=0}^{K-1}\pi_n=\mu\sum_{n=0}^{K}\pi_n\min(n,c)$. Since $\sum_{n=0}^{K-1}\pi_n=1-\pi_K$, this is exactly the asserted identity. $\square$

The theorem’s assumptions are important for interpreting the result. The queue is finite and has a stationary distribution; $\lambda>0$ means there are offered arrivals whose blocking fraction can be measured. If $\lambda=0$, there are no offered arrivals, so the fraction blocked among arrivals is not defined, even though a stationary empty system has $\pi_K=0$. Under the stated positive-rate assumptions the finite birth-death chain is irreducible and has a stationary distribution.

Worked Calculations

Worked Example: Two Servers and One Waiting Place

Take $c=2$, $K=3$, $\lambda=2$, and $\mu=1$. There are three states below capacity and one full state. The generator, with rows and columns ordered $0,1,2,3$, is

Q= \begin{bmatrix} -2&2&0&0\\ 1&-3&2&0\\ 0&2&-4&2\\ 0&0&2&-2 \end{bmatrix}.

Its row sums are $-2+2=0$, $1-3+2=0$, $2-4+2=0$, and $2-2=0$, so it is a valid generator. The weights are $w_0=1$, $w_1=2$, $w_2=2^2/2=2$, and $w_3=2^3/(2!\,2)=2$. Their sum is $1+2+2+2=7$, giving $\pi=(1/7,2/7,2/7,2/7)$.

Thus the blocking probability is $B=\pi_3=2/7$. The offered arrival rate is $2$, so the effective arrival rate is $2(1-2/7)=2(5/7)=10/7$.

Check: The service-completion rate is $1(1\cdot\pi_1+2\cdot\pi_2+2\cdot\pi_3)=2/7+4/7+4/7=10/7$, agreeing with the admitted rate. The coefficients are $1,2,2$ because states $1,2,3$ have respectively one, two, and two busy servers.

Worked Example: One Server with Capacity Two

Take $c=1$, $K=2$, $\lambda=1$, and $\mu=2$. The generator in state order $0,1,2$ is

Q= \begin{bmatrix} -1&1&0\\ 2&-3&1\\ 0&2&-2 \end{bmatrix}.

Each row sums to zero: $-1+1=0$, $2-3+1=0$, and $2-2=0$. The weights are $w_0=1$, $w_1=1/2$, and $w_2=(1/2)^2=1/4$. Their sum is $1+1/2+1/4=7/4$, so $\pi_2=(1/4)/(7/4)=1/7$, and $\pi=(4/7,2/7,1/7)$.

The blocking probability is $1/7$, while the effective arrival rate is $1(1-1/7)=6/7$. The server-completion check gives $2(\pi_1+\pi_2)=2(2/7+1/7)=6/7$. State $0$ contributes no service completions; states $1$ and $2$ each have one busy server.

Worked Example: Capacity Equal to the Number of Servers

Take $c=K=2$, $\lambda=3$, and $\mu=2$. There is no waiting room: any arrival finding both servers busy is blocked. The generator in state order $0,1,2$ is

Q= \begin{bmatrix} -3&3&0\\ 2&-5&3\\ 0&4&-4 \end{bmatrix}.

The row sums are $-3+3=0$, $2-5+3=0$, and $4-4=0$. The stationary weights are $w_0=1$, $w_1=3/2$, and $w_2=(3/2)^2/2=9/8$. Their sum is $1+3/2+9/8=8/8+12/8+9/8=29/8$. Therefore $\pi_2=(9/8)/(29/8)=9/29$, and $\pi=(8/29,12/29,9/29)$.

The blocking probability is $9/29$, and the effective rate is $3(1-9/29)=3(20/29)=60/29$. Independently, the completion rate is $2(\pi_1+2\pi_2)=2(12/29+18/29)=60/29$. Both calculations agree.

Interpreting the Rates and Avoiding Common Errors

The offered rate $\lambda$ counts all arrival attempts, including those rejected at capacity. The admitted rate $\lambda_{\mathrm{eff}}$ counts only arrivals that enter. In stationarity, the admitted rate also equals the completion rate: the system cannot accumulate customers at a nonzero average rate while its occupancy distribution remains stationary. This equality does not mean that each admitted arrival is immediately served; some customers may wait, and the identity concerns long-run rates.

Common mistake: treating $\lambda$ as the admitted rate. For the first example, using $\lambda=2$ as the throughput would ignore the $2/7$ of offered arrivals that are blocked. The corrected calculation is $2(1-2/7)=10/7$. A related error is to use $n\mu$ as the completion rate in state $n$ even when $n>c$. In the first example, state $3$ has two busy servers, so its completion rate is $2\mu=2$, not $3\mu=3$. The correct average completion rate uses $\mu\min(n,c)$.

These measures answer different operational questions. The blocking probability describes the chance an offered customer is refused under stationary operation. The effective arrival rate describes the volume successfully admitted per unit time. Neither should be confused with the probability that an admitted customer waits, which is a different performance measure. In particular, a full system is not the same event as an arrival having to wait: a customer can wait when fewer than $K$ customers are present, as long as all $c$ servers are busy.

Check Your Understanding

For each question, distinguish offered arrivals from admitted customers, and verify rate calculations using the service-completion expression.

In a stationary M/M/c/K queue, why does the blocking probability equal $\pi_K$ when arrivals are Poisson and independent of the queue’s past?
If $\lambda=5$ and $\pi_K=1/4$, calculate the effective arrival rate. What does the difference from $\lambda$ represent?
For $c=2$, what is the total service-completion rate when the system contains $n=1$, $n=2$, or $n=4$ customers, assuming capacity permits state $4$?
Explain why the stationary completion rate is $\mu\sum_{n=0}^{K}\pi_n\min(n,c)$, rather than $c\mu$ in every state.
In the worked example with $c=K=2$, verify that the three stationary probabilities sum to one and that the admitted and completion rates both equal $60/29$.

Blocking Probability and Throughput in M/M/c/K

What You'll Learn