3.1 Matrix geometric solutions for GI/M/1-type and QBD processes

In this section, we give a brief overview^3.1 of the matrix geometric solution technique for GI/M/1-type and QBD processes. While QBDs fall under both the M/G/1 and the GI/M/1-type cases, they are most commonly associated with GI/M/1 processes because they can be both solved using the well-known matrix geometric approach [67].

Key to the general solution for the generator of Eqs.(2.21) and (2.18) is the assumption that a geometric relation^3.2 holds among the stationary probability vectors $\mbox{\boldmath {$\pi$}}^{(i)}$ of states in ${\cal{S}}^{(i)}$ as follows:

$$\mbox{\boldmath {$\pi$}}^{(i)} = \mbox{\boldmath {$\pi$}}^{(1)} \cdot {\mathbf{R}}^{i-1} ~~~\forall i \geq 1,$$ (3.1)

where, in the GI/M/1-type case, ${\mathbf{R}}$ is the solution of the matrix equation

$${\mathbf{F}}+ {\mathbf{R}}\cdot \L + \sum_{k=1}^{\infty} {\mathbf{R}}^{k+1} \cdot {\mathbf{B}}^{(k)} = {\mathbf{0}},$$ (3.2)

and can be computed using iterative numerical algorithms. The above equation is obtained from the flow balance equations of the repeating portion of the process, i.e., starting from the third column of ${\mathbf{Q}}_{GI/M/1}$. One can solve a GI/M/1-type process starting from the flow balance equations corresponding to the first two columns of ${\mathbf{Q}}_{GI/M/1}$. By substituting $\mbox{\boldmath {$\pi$}}^{(i)}$ for $i \geq 2$ with their equivalents from Eq. (3.1), i.e., $\mbox{\boldmath {$\pi$}}^{(1)} {\mathbf{R}}^{i-1}$, and adding the normalization condition as

$$\begin{eqnarray*} \mbox{\boldmath {$\pi$}}^{(0)} \cdot {\mathbf{1}}^T + \mbox{\b... ...cdot ({\mathbf{I}}- {\mathbf{R}})^{-1} \cdot {\mathbf{1}}^T = 1, \end{eqnarray*}$$

we obtain the following system of linear equations

$$[\mbox{\boldmath {$\pi$}}^{(0)}, \mbox{\boldmath {$\pi$}}^{(1... ... {\mathbf{B}}^{(k)}\\ \end{array}\right] = [1, {\mathbf{0}}],$$ (3.3)

that yields a unique solution for $\mbox{\boldmath {$\pi$}}^{(0)}$ and $\mbox{\boldmath {$\pi$}}^{(1)}$. The symbol ``$^\diamond$'' indicates that we discard one (any) column of the corresponding matrix, since we added a column representing the normalization condition. For $i \geq 2$, $\mbox{\boldmath {$\pi$}}^{(i)}$ can be obtained numerically from Eq.(3.1), but many useful performance metrics such as expected system utilization, throughput, or queue length can be expressed explicitly in closed-form using $\mbox{\boldmath {$\pi$}}^{(0)}$, $\mbox{\boldmath {$\pi$}}^{(1)}$, and ${\mathbf{R}}$ only (e.g., the average queue length is simply given by $\mbox{\boldmath {$\pi$}}^{(1)} \cdot ({\mathbf{I}}- {\mathbf{R}})^{-2} \cdot {\mathbf{1}}^T$) [64].

In the case of QBD processes, Eq.(3.2) simply reduces to the matrix quadratic equation

$${\mathbf{F}}+ {\mathbf{R}}\cdot \L + {\mathbf{R}}^2 \cdot {\mathbf{B}}= {\mathbf{0}},$$

while $\mbox{\boldmath {$\pi$}}^{(0)}$ and $\mbox{\boldmath {$\pi$}}^{(1)}$ are obtained as the solution of the following system of linear equations [65]:

$$[\mbox{\boldmath {$\pi$}}^{(0)}, \mbox{\boldmath {$\pi$}}^{(1... ...}\cdot {\mathbf{B}}\\ \end{array}\right] = [1, {\mathbf{0}}].$$ (3.4)