Delay Measures for Accepted Customers in M/M/c/K

From Occupancy to Delay for Admitted Customers

In a finite-capacity queue, an offered arrival may find the system full and be rejected. The delay experienced by admitted customers must therefore be paired with the rate at which customers actually enter, not automatically with the rate at which arrivals are offered. Once this distinction is made, stationary occupancy probabilities give the mean number in the system and in the queue; Little’s law then converts those counts into mean times.

Consider an M/M/c/K queue with $1\le c\le K$, offered arrival rate $\lambda>0$, and service rate $\mu>0$ at each of the $c$ servers. The capacity $K$ counts all customers in the system, both in service and waiting. Arrivals finding $K$ customers are rejected. On a probability space $(\Omega,\mathcal{F},\mathbb{P})$, let $(N_t)_{t\ge0}$ be the continuous-time occupancy process, with state space $S=\{0,1,\ldots,K\}$.

From state $n<K$, an arrival increases occupancy by one at rate $\lambda$. From state $n>0$, a service completion decreases occupancy by one at rate $\min(n,c)\mu$. Thus the generator $Q=(q_{ij})$ has $q_{n,n+1}=\lambda$ for $n<K$, $q_{n,n-1}=\min(n,c)\mu$ for $n>0$, all other off-diagonal entries zero, and diagonal entries chosen so every row sums to zero. In particular, $q_{nn}$ is the negative of the total rate of leaving state $n$.

Definition: Let $p_n=\mathbb{P}(N_t=n)$ in stationarity. The offered arrival rate is $\lambda$, whereas the effective throughput $\lambda_{\mathrm{eff}}$ is the rate of admitted arrivals. The mean system occupancy and mean queue length are $$ L=\sum_{n=0}^{K}n p_n,\qquad L_q=\sum_{n=0}^{K}(n-c)^+p_n, $$ where $(x)^+=\max(x,0)$. The mean number of busy servers is $L_s=\sum_{n=0}^{K}\min(n,c)p_n$. For admitted customers, $W$ denotes mean time in the system, and $W_q$ denotes mean time waiting before service begins.

The stationary probabilities can be written using $a=\lambda/\mu$ and unnormalized weights $$ w_n= \begin{cases} \dfrac{a^n}{n!},&0\le n\le c,\\[4pt] \dfrac{a^n}{c!\,c^{\,n-c}},&c<n\le K, \end{cases} \qquad p_n=\frac{w_n}{\displaystyle\sum_{j=0}^{K}w_j}. $$

This is the finite birth-death stationary distribution: adjacent weights satisfy $p_n\lambda=p_{n+1}\min(n+1,c)\mu$ for $0\le n<K$. These equalities balance the flow between every adjacent pair of states and imply stationarity. For completeness, summing the incoming and outgoing rates at each state shows that these pairwise balances give zero net flow at that state. Conversely, in any stationary distribution the balance equation at state $0$ forces the balance across states $0$ and $1$; successively, the equations at states $1,2,\ldots,K-1$ force the corresponding balances across each next pair. Normalization then determines the probabilities uniquely.

The Throughput and Little’s-Law Identities

An arrival is admitted precisely when the pre-arrival state is less than $K$. Since external arrivals are Poisson and independent of the queue’s service mechanism, PASTA (Poisson arrivals see time averages) gives the stationary probability $p_K$ of finding the system full. Equivalently, the state-dependent arrival rate is $\lambda$ in states $0,\ldots,K-1$ and zero in state $K$. Therefore the admitted-customer throughput is $$ \lambda_{\mathrm{eff}}=\lambda\sum_{n=0}^{K-1}p_n=\lambda(1-p_K). $$

Theorem: For this finite-capacity queue in stationarity, the admitted-customer mean times satisfy $$ L=\lambda_{\mathrm{eff}}W,\qquad L_q=\lambda_{\mathrm{eff}}W_q,\qquad L_s=\lambda_{\mathrm{eff}}/\mu. $$ Consequently, $$ W=\frac{L}{\lambda_{\mathrm{eff}}},\qquad W_q=\frac{L_q}{\lambda_{\mathrm{eff}}},\qquad W=W_q+\frac1\mu. $$ These formulas concern admitted customers only. Since $\lambda>0$ and $p_K<1$, the denominator $\lambda_{\mathrm{eff}}$ is positive.

Proof. First, the pairwise stationary balances give $$ \lambda\sum_{n=0}^{K-1}p_n =\sum_{n=0}^{K-1}p_n\lambda =\sum_{n=1}^{K}p_n\min(n,c)\mu =\mu L_s. $$ The first expression is the admitted throughput, so $\lambda_{\mathrm{eff}}=\mu L_s$, proving the third identity.

For the time identities, use the customer-time accounting underlying Little’s law. On any interval $[0,T]$, the area under the system-occupancy curve is the sum, over all customers, of the length of their time in the system that falls inside $[0,T]$: $$ \int_0^T N_t\,dt =\sum_{\text{customers }r} \bigl|[A_r,D_r)\cap[0,T]\bigr|, $$ where $A_r$ and $D_r$ are that customer’s arrival and departure times. The same identity holds for the queue-length curve when each customer’s interval is replaced by the part of their stay before service begins. In a stationary finite-capacity queue, the finite-state irreducible continuous-time Markov-chain ergodic theorem gives the long-run mean occupancy $L$ and queue length $L_q$; the admitted-arrival rate is $\lambda_{\mathrm{eff}}$. Apply the accounting identity over $[0,T]$ and divide by $T$. Customers already present at time $0$, and customers still present at $T$, contribute only boundary terms. There are at most $K$ customers at either endpoint, and their expected remaining or elapsed queue times are finite because the state space is finite and $\mu>0$. Thus the boundary contributions divided by $T$ vanish as $T$ grows. The long-run customer-time per unit time is consequently admitted arrivals per unit time multiplied by mean time per admitted customer. This proves $L=\lambda_{\mathrm{eff}}W$ and, by the queue-interval version of the same accounting, $L_q=\lambda_{\mathrm{eff}}W_q$. Finally $L=L_q+L_s$, so division by the positive throughput gives $W=W_q+L_s/\lambda_{\mathrm{eff}}=W_q+1/\mu$. $\square$

The ergodic theorem used here is the standard finite-state result: a finite irreducible continuous-time Markov chain has long-run state proportions equal to its stationary probabilities. It applies because every state communicates with every other state when $\lambda,\mu>0$. The customer-time argument explains why the relevant arrival rate in Little’s law is the admitted throughput.

Worked Calculations

Worked Example: Two Servers and Capacity Three

Take $c=2$, $K=3$, $\lambda=2$, and $\mu=1$. The generator, in state order $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}. $$ The row sums are $-2+2=0$, $1-3+2=0$, $2-4+2=0$, and $2-2=0$.

Here $a=\lambda/\mu=2$, so 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 $p_0=1/7$, $p_1=2/7$, $p_2=2/7$, and $p_3=2/7$. The probabilities sum to $7/7=1$.

The full-state probability is $p_3=2/7$, so $$ \lambda_{\mathrm{eff}}=2(1-2/7)=10/7. $$ The mean occupancy, queue length, and number of busy servers are $$ L=0(1/7)+1(2/7)+2(2/7)+3(2/7)=12/7, $$ $$ L_q=0(1/7)+0(2/7)+0(2/7)+1(2/7)=2/7, \qquad L_s=0(1/7)+1(2/7)+2(2/7)+2(2/7)=10/7. $$ Therefore $W=(12/7)/(10/7)=6/5$ and $W_q=(2/7)/(10/7)=1/5$. The check $W_q+1/\mu=1/5+1=6/5=W$ agrees, and $\mu L_s=1(10/7)=10/7=\lambda_{\mathrm{eff}}$.

Worked Example: A Single Server with Capacity Two

Take $c=1$, $K=2$, $\lambda=1$, and $\mu=1$. The generator in state order $0,1,2$ is $$ Q= \begin{bmatrix} -1&1&0\\ 1&-2&1\\ 0&1&-1 \end{bmatrix}. $$ Its row sums are $-1+1=0$, $1-2+1=0$, and $1-1=0$.

Since $a=1$, the weights are $w_0=1$, $w_1=1$, and $w_2=1$. Their sum is $3$, so each stationary probability is $1/3$, and their total is $1$. The throughput and occupancy measures are $$ \lambda_{\mathrm{eff}}=1(1-1/3)=2/3,\qquad L=0(1/3)+1(1/3)+2(1/3)=1, $$ $$ L_q=0(1/3)+0(1/3)+1(1/3)=1/3,\qquad L_s=0(1/3)+1(1/3)+1(1/3)=2/3. $$ Thus $W=1/(2/3)=3/2$ and $W_q=(1/3)/(2/3)=1/2$. Substitution checks both identities: $(2/3)(3/2)=1=L$ and $(2/3)(1/2)=1/3=L_q$. Also $W_q+1/\mu=1/2+1=3/2=W$, and $\mu L_s=1(2/3)=\lambda_{\mathrm{eff}}$.

Worked Example: No Waiting Room

Take $c=2$, $K=2$, $\lambda=3$, and $\mu=2$. This is a loss system: an admitted customer enters service immediately. 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$.

Here $a=3/2$; the 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=29/8$, so $p_0=8/29$, $p_1=12/29$, and $p_2=9/29$. These probabilities sum to $29/29=1$. Then $$ \lambda_{\mathrm{eff}}=3(1-9/29)=60/29,\qquad L=0(8/29)+1(12/29)+2(9/29)=30/29. $$ There is no queue, so $L_q=0$. The busy-server mean is $L_s=L=30/29$. Hence $W=(30/29)/(60/29)=1/2$ and $W_q=0$. The service-time check gives $1/\mu=1/2=W$, and the throughput check gives $\mu L_s=2(30/29)=60/29=\lambda_{\mathrm{eff}}$.

Interpretation and a Common Error

For every admitted customer, $W_q$ counts only time spent waiting before service, while $W$ also includes service. Since service times are exponential with rate $\mu$, the mean service time is $1/\mu$; the identity $W=W_q+1/\mu$ is also confirmed by the stationary throughput and busy-server calculation. In a full system, however, an arrival is rejected and has no admitted-customer waiting or system time in these formulas.

Common mistake: using $\lambda$ instead of $\lambda_{\mathrm{eff}}$. In the two-server example, using the offered rate would give $L/\lambda=(12/7)/2=6/7$ as the purported mean time in the system. But the admitted throughput is $10/7$, so the correct value is $L/\lambda_{\mathrm{eff}}=(12/7)/(10/7)=6/5$. Substitution exposes the error: $2(6/7)=12/7$ uses all offered arrivals, including rejected ones, whereas $(10/7)(6/5)=12/7=L$ uses only admitted customers.

As capacity becomes more restrictive, $p_K$ and the difference between offered arrival rate and throughput can become substantial. Always compute the blocking probability and effective throughput before converting occupancy into delay. The formulas also cover $K=c$: then every admitted customer starts service immediately, $L_q=0$, and $W_q=0$.

Check Your Understanding

For each calculation, use admitted throughput when applying Little’s law and check the relevant occupancy identity.

In an M/M/1/2 queue with $\lambda=2$ and $\mu=1$, calculate the stationary probabilities, effective throughput, and mean system time of admitted customers.
Explain why $L_q$, rather than $L$, is the quantity paired with $W_q$.
For an M/M/2/2 queue, what is $W_q$, and why? State the resulting value of $W$ in terms of $\mu$.
Show from the adjacent stationary flow balances that $\lambda_{\mathrm{eff}}=\mu L_s$.
In what way does using the offered rate in place of effective throughput miscount customers in a finite-capacity queue?

Delay Measures for Accepted Customers in M/M/c/K

What You'll Learn