3.9 Conditions for stability

We briefly review the conditions that enable us to assert that the CTMC described by the infinitesimal generator ${\mathbf{Q}}_{M/G/1}$ in Eq.(2.22) is stable, that is, admits a probability vector satisfying $\mbox{\boldmath {$\pi$}}{\mathbf{Q}}_{M/G/1} = {\mathbf{0}}$ and $\mbox{\boldmath {$\pi$}}{\mathbf{1}}^T = 1$.

First observe that the matrix $\widetilde{{\mathbf{Q}}} = {\mathbf{B}}+ \L + \sum_{j=1}^{\infty} {\mathbf{F}}^{(j)}$ is an infinitesimal generator, since it has zero row sums and non-negative off-diagonal entries. The conditions for stability depend on the irreducibility of matrix $\widetilde{{\mathbf{Q}}}$.

If $\widetilde{{\mathbf{Q}}}$ is irreducible then there exists a unique positive vector $\widetilde{\mbox{\boldmath {$\pi$}}}$ that satisfies the equations $\widetilde{\mbox{\boldmath {$\pi$}}} \widetilde{{\mathbf{Q}}} = {\mathbf{0}}$ and $\widetilde{\mbox{\boldmath {$\pi$}}} {\mathbf{1}}^T = 1$. In this case, the stability condition for the M/G/1-type process with infinitesimal generator ${\mathbf{Q}}_{M/G/1}$ [69] is given by the following inequality

$$\widetilde{\mbox{\boldmath {$\pi$}}} (\L + \sum_{j=1}^{\inft... ...}} \sum_{j=1}^{\infty} j {\mathbf{F}}^{(j)} {\mathbf{1}}^T< 0.$$

Since ${\mathbf{B}}+ \L + \sum_{j=1}^{\infty} {\mathbf{F}}^{(j)}$ is an infinitesimal generator, then $({\mathbf{B}}+ \L + \sum_{j=1}^{\infty} {\mathbf{F}}^{(j)}){\mathbf{1}}^T = 0$. By substituting in the condition for stability the term $(\L + \sum_{j=1}^{\infty} {\mathbf{F}}^{(j)}){\mathbf{1}}^T$ with its equal ( $-{\mathbf{B}}{\mathbf{1}}^T$), the condition for stability can be re-written as:

$$\widetilde{\mbox{\boldmath {$\pi$}}} \sum_{j=1}^{\infty} j {... ...idetilde{\mbox{\boldmath {$\pi$}}} {\mathbf{B}}{\mathbf{1}}^T.$$ (3.41)

As in the scalar case, the equality in the above relation results in a null-recurrent CTMC.

In the example of the $BMAP_1/Cox_2/1$ queue depicted in Figure 3.3, the infinitesimal generator $\widetilde{{\mathbf{Q}}}$ and its stationary probability vector are

$$\widetilde{{\mathbf{Q}}} = \left[ \begin{array}{c c} -0.8 \m... ...\gamma}{\gamma+0.8\mu},~~\frac{0.8\mu}{\gamma+0.8\mu} \right],$$

while

$$\sum_{j=1}^{\infty} j{\mathbf{F}}^{(j)} = \left[ \begin{array}{c c} 4\lambda ~&~ 0 \\ 0 ~&~ 4\lambda \end{array}\right].$$

The stability condition is expressed as

$$\left[ \frac{\gamma}{\gamma+0.8\mu},~~\frac{0.8\mu}{\gamma+... ...ht] \cdot \left[ \begin{array}{c} 1\\ 1 \end{array}\right],$$

which can be written in the following compact form

$$4\lambda < \frac{\mu \cdot \gamma}{0.8\mu + \gamma}.$$

If $\widetilde{{\mathbf{Q}}}$ is reducible, then the stability condition is different. By identifying the absorbing states in $\widetilde{{\mathbf{Q}}}$, its state space can be rearranged as follows

$$\widetilde{{\mathbf{Q}}} = \left[ \begin{array}{c c c c c c}... ...ots & {\mathbf{D}}_{k} & {\mathbf{D}}_{0} \end{array}\right],$$ (3.42)

where the blocks ${\mathbf{C}}_{h}$ for $1 \leq h \leq k$ are irreducible and infinitesimal generators. Since the matrices ${\mathbf{B}}$, $\L$ and ${\mathbf{F}}^{(i)}$ for $i \geq 1$ have non-negative off-diagonal elements, they can be restructured similarly and have block components ${\mathbf{B}}_{{\mathbf{C}}_h}$, ${\mathbf{B}}_{{\mathbf{D}}_l}$, $\L _{C_h}$, $\L _{D_l}$, and ${\mathbf{F}}^{(i)}_{C_h}$, ${\mathbf{F}}^{(i)}_{D_l}$ for $1 \leq h \leq k$, $0 \leq l \leq k$, and $i \geq 1$.

This implies that each of the sets ${\cal{S}}^{(i)}$ for $i \geq 1$ is partitioned into subsets that communicate only through the boundary portion of the process, i.e., states in ${\cal{S}}^{(0)}$. The stability condition in Eq.(3.41) should be satisfied by all the irreducible blocks identified in Eq.(3.42) in order for the M/G/1-type process to be stable as summarized below:

$$\widetilde{\mbox{\boldmath {$\pi$}}}^{(h)} \sum_{j=1}^{\inft... ...{\mathbf{C}}_h} {\mathbf{1}}^T ~~~~~~\forall 1 \leq h \leq k .$$ (3.43)