2
$\begingroup$

How do I derive the steady state probabilities for the $M/M/1/k$ queueing systems with finite system capacity $k$?

$\endgroup$
1
  • 2
    $\begingroup$ What you are describing is usually called an $M/M/1/k$ queuing system. (Sometimes a different letter is used in place of $k$.) Here, $k$ refers to the capacity. Most textbooks (and probably most websites) that derive steady-state probabilities for $M/M/1$ will also do the same for $M/M/1/k$. $\endgroup$ – LarrySnyder610 Sep 20 '20 at 13:01
1
$\begingroup$

There are a couple of ways to derive the steady state probabilities for a $M/M/1/k$ queuing system with Markovian* arrivals (the first $M$), exponential service time distribution (the second $M$), a single server (the 1), and a finite total system capacity of $k$. Note this implies the queue can be at most $k-1$.

*Recall a system with $M$ arrivals has exponential interarrivals with rate $\lambda$ and mean interarrival time of $\frac{1}{\lambda}$. Equivalently, arrivals occur according to a homogeneous Poisson process with rate $\lambda$.

One approach
The $M/M/1/k$ queuing system can be thought of as a Continuous Time Markov Chain (CTMC), $\{X(t), t>=0\}$, where $X(t)$ represents the total number of customers in the system. We can take advantage of the system capacity (constraint) being finite.

If the arrivals happen at rate $\lambda$ and the service rate is $\mu$, then the transition rate diagram is given below. Note the finite number of states, with the statespace $\mathcal S = \{0,1,2,3,\ldots,k\}$.

Transition rate diagram

The steady state probabilities, $\mathbf \pi = [\pi_0\; \pi_1\; \pi_2\; \ldots\; \pi_k]$, are obtained by the solution to the steady-state equations (flow out = flow in),

$$ \lambda \pi_0 = \mu \pi_1 \\ (\lambda+\mu) \pi_1 = \lambda \pi_0 + \mu \pi_2 \\ (\lambda+\mu) \pi_2 = \lambda \pi_1 + \mu \pi_3 \\ \vdots \\ \lambda \pi_{k-1} = \mu \pi_k $$

and the normalization equation $\sum_{i=0}^k \pi_k = 1$. The steady-state equations contain the dependency pattern of a Birth-Death Process, with the final equation being modified due to the finite state space (though this will not hamper the solution).

Ignoring the requirement for the $\pi$'s to sum to 1 for now, set $\pi_0 = 1$. Then $\hat \pi_j = \left(\frac{\lambda}{\mu}\right)^j$, or letting $\rho=\frac{\lambda}{\mu}$, then $\hat \pi = \rho^j$.

To normalize the solution, we need to divide the $\hat \pi$'s by the normalization constant $G = \hat \pi_0 + \hat \pi_1 + \hat \pi_2 +\hat \pi_3 + \cdots + \hat \pi_k$, which is a finite sum because we have a finite state space.

Rearranging, $$ \begin{align} G &= \hat \pi_0 + \hat \pi_1 + \hat \pi_2 +\hat \pi_3 + \cdots \hat \pi_k \\ &= 1 + \rho + \rho^2 + \rho^3 + \cdots + \rho^k \\ &= \left(\frac{1-\rho^{k+1}}{1-\rho} \right) \end{align} $$ which gives $$\frac{1}{G} = \frac{1-\rho}{1-\rho^{k+1}}$$ which is valid for any value of $\rho \in [0,1)$ with the special case of $\rho=1$ requiring the trivial $G = k+1$ yielding $$\frac{1}{G}=\frac{1}{k+1}$$ for this exception case.

This implies that $$ \begin{array}{ll} \pi_j = \rho^j\left(\frac{1-\rho}{1-\rho^{k+1}}\right) & \text{for } \rho\ne 1 \tag{Key Result} \\ \pi_j = \frac{1}{k+1} & \text{for } \rho = 1 \\ \end{array} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.