From BoykinWiki

EEL6507 Spring 2009, Lecture 23, Wednesday 2009/03/04 (Notes created by Ryan C.W.Wong)

$E_r/M/1 \,\!$ Overview

The $E_r/M/1 \,\!$ system is a queueing system for which the distribution of interarrival time and service time is modeled as

$a(x) = \frac{r\lambda\left(r\lambda x\right)^{r-1}e^{-r\lambda x}}{(r-1)!}\,\!$ and

$b(x) =\ \mu e^{-\mu x}$ , respectively.

The system operates as follows: each customer first pass through r-stages of "arriving" before "actually" joining the queue. Pictorially, it looks like

Stage representation of $E_r/M/1 \,\!$

where $\ \alpha$ and $\ k$ represents the number of stage of next arrival and the number in the system, respectively.

Hence, it is not hard to see that the state $\ s$ of the system is $\ rk+(r-\alpha)$ .

Markov chain representation of $E_r/M/1 \,\!$

State transition diagram of $E_r/M/1 \,\!$

The steady state balance equations are

$r \lambda p_0 = \mu p_1 \,\!$

$r \lambda p_k = r \lambda p_{k-1} + \mu p_{k+r} , 0<k<r \,\!$

$\left (r \lambda + \mu \right) p_k = r \lambda p_{k-1} + \mu p_{k+r} , k \geq r \,\!$

Performing the aforementioned Z-transform technique and letting $\rho = \frac{\lambda}{\mu} \,\!$ , we will get the following expression

$P(z) = \frac{(1 - z^r) \sum_{j=0}^{r-1} p_j z^j}{r \rho z^{r+1}-(1+r \rho)z^r + 1} \,\!$

As usual, the next task is to determine the unknown, namely $p_j, 0 \leq j \leq (r-1) \,\!$ in the above equation.

We will adopt another approach, rather than solving $p_j \,\!$ explicitly.

Before moving on, we need the following fact about $P(z) \,\!$ .

Fact about $P(z) \,\!$

If $z \in \mathbb{C} \,\!$ , then $\left | P(z)\right| \leq 1, \forall |z| \leq 1 \,\!$

Proof:

$\begin{align} \left | P(z)\right| &= \left | \sum_k p_k z^k \right| \\ &\leq \sum_k \left | p_k z^k \right| \\ &= \sum_k p_k \left | z^k \right| \\ &\leq \sum_k p_k \\ &= 1 \\ \end{align}$

Going back to the expression of $P(z) \,\!$ we found for $E_r/M/1 \,\!$ , it means that all roots of denominator in $P(z) \,\!$ must be either outside the unit circle in complex plane or be canceled by the numerator. For example, when $r=1 \,\!$ , we have

$\begin{align} P(z) &= \frac{(1 - z) (1-\rho)}{r \rho z^2-(1+ \rho)z + 1} \\ &= \frac{(1 - z) (1-\rho)}{(1-z) (1- \rho z)} \\ &= \frac{(1-\rho)}{(1- \rho z)} \\ \end{align}$

with roots of the denominator being 1 (which is canceled by the numerator) and $\rho^{-1} \,\!$ (which is greater than 1 for stable system).

Factoring the denominator

$\begin{align} D(z) &= r \rho z^{r+1}-(1+r \rho)z^r + 1 \\ &= r \rho z^r (z-1) + 1 - z^r \\ &= r \rho z^r (z-1) + (1 - z)\sum_{j=0}^{r-1} z^j \\ &= (1-z) \left( \sum_{j=0}^{r-1} z^j - r \rho z^r \right )\\ \end{align}$

Let $G(z) = \left( \sum_{j=0}^{r-1} z^j - r \rho z^r \right )$ and we can prove that there are $r \,\!$ roots in $G(z) \,\!$ , $r-1 \,\!$ out of them are strictly inside the unit circle and the remaining one root is strictly outside the unit circle and we call it $z_0 \,\!$ .

Taking the aforementioned observations into account, we can make the following conclusions.

The $r-1 \,\!$ roots of the denominator of $P(z) \,\!$ , which are strictly inside the unit circle, must be canceled by the numerator.

Since $(1- z^r) \,\!$ have roots exactly on the unit circle, they can not be the term to be used in cancellation.

Hence, the $r-1 \,\!$ roots of the denominator should exactly be the same set of roots of $\sum_{j=0}^{r-1} p_j z^j\,\!$ .

Thus,

$G(z) = K\left(1-\frac{z}{z_0}\right) \left( \sum_{j=0}^{r-1} p_j z^j \right) \,\!$ ,

where $K \,\!$ is some constant to be determined.

Hence, finally we have

$P(z) = \frac{(1-z^r)}{K (1-z) (1-\frac{z}{z_0})} \,\!$

To determine the value of $K \,\!$ , we use the fact that $P(z)|_{z=1} = 1 \,\!$ .

It is not hard to work out that $P(z)|_{z=1} = \frac{r}{K (1-\frac{1}{z_0})} \,\!$ , thus $K = \frac{r}{(1-\frac{1}{z_0})} \,\!$ .

In conclusion, the generating function for $E_r/M/1 \,\!$ is

$P(z) = \frac{(1-z^r)(1-\frac{1}{z_0})}{r (1-z) (1-\frac{z}{z_0})} \,\!$ .

Note: In the above equation, $P(z) \,\!$ does not depend on the value of $\rho \,\!$ explicitly. However, it is expected that $z_0 \,\!$ will be determined by the system parameters $\mu \,\!$ , $\lambda \,\!$ and $r \,\!$ .