3.5 Example: a $BMAP_1/Cox_2/1$ queue

Figure 3.3 illustrates a Markov chain that models a $BMAP_1/Cox_2/1$ queue. This chain is very similar with the one depicted in Figure 3.1, the only difference is that the new chain models bulk arrivals of unlimited size.

Figure 3.3: The CTMC that models a $BMAP_1/Cox_2/1$ queue.

The infinitesimal generator ${\mathbf{Q}}_{M/G/1}$ of the process is block partitioned according to the partitioning of the state space ${\cal {S}}$ of this CTMC into subsets ${\cal{S}}^{(0)} = \{(0,0)\}$ and ${\cal{S}}^{(i)} = \{(i,1), (i,2)\}$ for $i \geq 1$. The definition of the component matrices of ${\mathbf{Q}}_{M/G/1}$ is as follows:

$$\begin{array}{c c c} \widehat{{\mathbf{L}}}= \left[ -2\lambd... ... & 0.5^{i-1}\lambda \end{array} \right] ~i \geq 1. \end{array}$$

In the following, we derive the relation between $\mbox{\boldmath {$\pi$}}^{(i)}$ for $i \geq 1$ and the rest of vectors in $\mbox{\boldmath {$\pi$}}$ using stochastic complementation, i.e., similarly to the approach described in Section 3.1. First we partition the state space ${\cal {S}}$ into two partitions ${\cal {A}}= \cup _{j=0}^{j=i} {\cal {S}}^{(j)}$ and $\overline{{\cal{A}}} = \cup_{j=i+1}^{\infty} {\cal{S}}^{(j)}$ and then we construct the stochastic complement of states in ${\cal{A}}$. The Markov chain of the stochastic complement of states in ${\cal{A}}$, (see Figure 3.4), illustrates how transitions from states $(j,1)$ and $(j,2)$ for $j \leq i$ and state $(0,0)$ to states $(l,1)$ and $(l,2)$ for $l >i$ are folded back to state $(i,1)$, which is the single state to enter ${\cal{A}}$ from states in $\overline{{\cal{A}}}$. These ``back-folded'' transitions are marked by $x_{k,h}$ for $k \leq i$ and $h=1,2$ and represent the ``correction'' needed to make the stochastic complement of states in ${\cal{A}}$, a stand-alone process. Because of the single entry state in ${\cal{A}}$ the stochastic complement of states in ${\cal{A}}$ for this example can be explicitly derived (see Lemma on single entry state in Subsection 2.8.2) and the definition of rates $x_{k,h}$ is as follows:

$$x_{k,h} = 2 \cdot 0.5^{i-k}\lambda = 0.5^{i-k-1}\lambda, ~~~i \geq 1, ~~~k \leq i, ~~ h=1,2.$$

The flow balance equations for states $(i,1)$ and $(i,2)$ for the stochastic complement of states in ${\cal{A}}$ are:

$$\begin{array}{c c l} (0.2\mu+0.8\mu)\overline{\mbox{\boldmat... ...mbda\overline{\mbox{\boldmath {$\pi$}}}^{(i-1)}[2] \end{array}$$

and

$$(2\lambda+\gamma)\overline{\mbox{\boldmath {$\pi$}}}^{(i)}[2... ...5^{i-i}\lambda\overline{\mbox{\boldmath {$\pi$}}}^{(i-1)}[2] .$$

Figure 3.4: Stochastic complement of $BMAP_1/Cox_2/1$-type queue at level $i$.

In the above equalities, we group the elements of $\overline{\mbox{\boldmath {$\pi$}}}^{(i)}$ on the left and the rest of the terms on the right in order to express their relation in terms of the block matrices that describe the infinitesimal generator $\overline{{\mathbf{Q}}}$ of the stochastic complement of states in ${\cal{A}}$. By rearranging the terms, the above equations can be re-written as:

$$\begin{array}{c c l} -\mu\overline{\mbox{\boldmath {$\pi$}}}... ...bda\overline{\mbox{\boldmath {$\pi$}}}^{(i-1)}[2]) \end{array}$$

and

$$0.8\mu\overline{\mbox{\boldmath {$\pi$}}}^{(i)}[1] -(2\lambd... ...5^{i-i}\lambda\overline{\mbox{\boldmath {$\pi$}}}^{(i-1)}[2]).$$

We can now re-write the above equations in the following matrix equation form:

$$\begin{array}{c c l} [\overline{\mbox{\boldmath {$\pi$}}}^{(... ...da &~0.5^{i-i}\lambda \end{array}\right] \right). \end{array}$$

By substituting $[\overline{\mbox{\boldmath {$\pi$}}}^{(i)}[1],~\overline{\mbox{\boldmath {$\pi$}}}^{(i)}[2]]$ with $\overline{\mbox{\boldmath {$\pi$}}}^{(i)}$ and expressing the coefficient matrices in the above equation in terms of the component matrices of the infinitesimal generator $\overline{{\mathbf{Q}}}$ of the stochastic complement of states in ${\cal{A}}$, we obtain^3.3:

$$\overline{\mbox{\boldmath {$\pi$}}}^{(i)} \cdot ( \L + \disp... ...laystyle{\sum_{j=1}^{\infty}} {\mathbf{F}}^{(j)}{\mathbf{G}}),$$

where ${\mathbf{G}}$ is a matrix with the following structure:

$${\mathbf{G}}= \left[ \begin{array}{c c} 1~ & ~0 \\ 1~ & ~0 \end{array} \right].$$

Note that at this point, we have introduced a new matrix, ${\mathbf{G}}$, that has an important probabilistic interpretation. In this specific example, the matrix ${{\mathbf{G}}}$ can be explicitly derived [77]. This is a direct outcome of the fact that all states in set ${\cal{S}}^{(i)}$ for $i \geq 1$ return to the same single state in set ${\cal{S}}^{(i-1)}$. Equivalently, the matrix ${\mathbf{B}}$ of the infinitesimal generator ${\mathbf{Q}}_{M/G/1}$ has only a single column different from zero.