3.8 Explicit computation of ${\mathbf{R}}$ for QBDs

QBD processes are defined as the intersection of M/G/1 and GI/M/1-type processes. Hence, both matrix ${\mathbf{G}}$ (characteristic for M/G/1) and matrix ${\mathbf{R}}$ (characteristic for GI/M/1) can be defined for a QBD process as solutions of the following quadratic equations [47]:

$${\mathbf{B}}+ \L {\mathbf{G}}+ {\mathbf{F}}{\mathbf{G}}^2 = ... ...}+ {\mathbf{R}}\L + {\mathbf{R}}^2 {\mathbf{B}}= {\mathbf{0}}.$$

If matrix-geometric is used to solve a QBD process then the relation between $\mbox{\boldmath {$\pi$}}^{(i)}$ and $\mbox{\boldmath {$\pi$}}^{(i-1)}$ for $i > 1$ is expressed in terms of ${\mathbf{R}}$

$$\mbox{\boldmath {$\pi$}}^{(i)} = \mbox{\boldmath {$\pi$}}^{(i-1}{\mathbf{R}},$$

If matrix-analytic is the solution method then the relation between $\mbox{\boldmath {$\pi$}}^{(i)}$ and $\mbox{\boldmath {$\pi$}}^{(i-1)}$ is based on Ramaswami's recursive formula:

$$\mbox{\boldmath {$\pi$}}^{(i)}=-\mbox{\boldmath {$\pi$}}^{(i-1)}\S^{(1)}(\S^{(0)})^{-1},$$

where $\S^{(1)}={\mathbf{F}}$ and $\S^{(0)}=(\L +{\mathbf{F}}{\mathbf{G}})$, i.e., the only auxiliary sums (see Subsection 3.7.1) used in the solution of M/G/1 processes that are defined for a QBD process. The above equations allow the derivation of the fundamental relation between ${\mathbf{R}}$ and ${\mathbf{G}}$ [47, pages 137-8],

$${\mathbf{R}}= -{\mathbf{F}}(\L + {\mathbf{F}}{\mathbf{G}})^{-1}.$$ (3.38)

Obviously, for the case of QBD processes, knowing ${\mathbf{G}}$ (or ${\mathbf{R}}$) implies a direct computation of ${\mathbf{R}}$ (or ${\mathbf{G}}$). Computing ${\mathbf{G}}$ is usually easier than computing ${\mathbf{R}}$: ${\mathbf{G}}$'s computation is a prerequisite to the computation of ${\mathbf{R}}$ in the logarithmic reduction algorithm, the most efficient algorithm to compute ${\mathbf{R}}$ [47]. If ${\mathbf{B}}$ can be expressed as a product of two vectors

$${\mathbf{B}}= \mbox{\boldmath {$\alpha$}}\cdot \mbox{\boldmath {$\beta$}},$$

where, without loss of generality $\mbox{\boldmath {$\beta$}}$ is assumed to be a normalized vector, then ${\mathbf{G}}$ and ${\mathbf{R}}$ can be explicitly obtained as

$${\mathbf{G}}={\mathbf{1}}\cdot\mbox{\boldmath {$\beta$}},~~~... ...{\mathbf{F}}{\mathbf{1}}\cdot\mbox{\boldmath {$\beta$}})^{-1}.$$

Representative examples, where the above condition holds, are the queues $M/Cox/1$, $M/Hr/1$, and $M/Er/1$, whose service process is Coxian, Hyperexponential, and Erlang distribution respectively.

The other case of explicit computation of ${\mathbf{R}}$ in QBD processes is when the matrix ${\mathbf{F}}$ of the infinitesimal generator matrix in Eq.(2.18) is given by

$${\mathbf{F}}= {\mathbf{w}}\cdot \mbox{\boldmath {$\beta$}},$$ (3.39)

where ${\mathbf{w}}$ is a column vector and $\mbox{\boldmath {$\beta$}}$ is a row vector, and without loss of generality it is assumed that $\mbox{\boldmath {$\beta$}}\cdot {\mathbf{1}}^T = 1$. In this case, the rate matrix ${\mathbf{R}}$ can be computed from

$${\mathbf{R}}= - {\mathbf{F}}(\L + \eta{\mathbf{B}})^{-1} = {\mathbf{w}}\cdot \mbox{\boldmath {$\xi$}},$$ (3.40)

where $\mbox{\boldmath {$\xi$}}= -\mbox{\boldmath {$\beta$}}\cdot(\L + \eta{\mathbf{B}})^{-1}$, and $\eta$ is the spectral radius, or the maximal eigenvalue of ${\mathbf{R}}$. There are at least two algorithms to compute $\eta$, one is given by Neuts [67, pages 36-40], and the other which explores the special structure of ${\mathbf{R}}$ is given in [77].