3. Matrix-Analytic Methods

Matrix analytic techniques provide a framework that is widely used for the exact analysis of a general and frequently encountered class of queueing models. In these models, the embedded Markov chains are two-dimensional generalizations of elementary GI/M/1 and M/G/1 queues [43], and their intersection, i.e., quasi-birth-death (QBD) processes. GI/M/1 and M/G/1 Markov chains model systems with interarrival and service times characterized, respectively, by general distributions rather than simple exponentials and are often used as the modeling tool of choice in modern computer and communication systems [65,78,101,29,53]. Alternatively, GI/M/1 and M/G/1 Markov chains can be analyzed by means of eigenvalues and eigenvectors [32]. The class of models that can be analyzed using M/G/1-type Markov chains includes the important class of BMAP/G/1 queues, where the arrival process and/or service process can exhibit correlation and long-tail, i.e., salient characteristics of Internet-related systems.

Neuts [67] defines various classes of infinite-state Markov chains with a repetitive structure, whose state space is partitioned into the boundary states ${\cal{S}}^{(0)} = \{s^{(0)}_1,\ldots,s^{(0)}_m\}$ and the sets of states ${\cal{S}}^{(i)} = \{s^{(i)}_1,\ldots,s^{(i)}_n\}$, for $i \geq 1$, that correspond to the repetitive portion of the chain. In Section 2.5, we identified these classes as GI/M/1-type, M/G/1-type, and their intersection, QBD processes. The structure of the infinitesimal generator for these type of processes is shown in Eqs.(2.21), (2.22), and (2.18), respectively.

For systems of the M/G/1-type, matrix analytic methods have been proposed for the solution of the basic equation $\mbox{\boldmath {$\pi$}}\cdot {\mathbf{Q}}_{M/G/1} = {\mathbf{0}}$ [69]. Key to the matrix-analytic methods is the computation of an auxiliary matrix called ${\mathbf{G}}$. Traditional solution methodologies for M/G/1-type processes compute the stationary probability vector with a recursive function based on ${\mathbf{G}}$. Iterative algorithms are used to determine ${\mathbf{G}}$ [60,47].

The solution of GI/M/1-type processes is significantly simpler than the solution of M/G/1-type processes because of the matrix geometric relation [67] that exists among the stationary probabilities of sets ${\cal{S}}^{(i)}$ for $i \geq 1$. This property leads to significant algebraic simplifications resulting in the very elegant matrix-geometric solution technique. Key to the matrix-geometric solution is a matrix called ${\mathbf{R}}$ which is used in the computation of the steady-state probability vector and measures of interest.

Since QBDs are special cases of both M/G/1-type processes and GI/M/1-type processes, either the matrix-analytic method or the matrix-geometric solution can be used for their analysis. The matrix-geometric solution is the preferable one because of its simplicity. Both matrices ${\mathbf{G}}$ and ${\mathbf{R}}$ are defined for QBD processes.

Key to the solution of Markov chains of the M/G/1, GI/M/1, and QBD types, is the existence of the repetitive structure, as illustrated in Eqs. (2.22), (2.21), and (2.18). This special structure allows for a certain recursive procedure to be applied for the computation of the stationary probability vector $\mbox{\boldmath {$\pi$}}^{(i)}$ corresponding to ${\cal{S}}^{(i)}$ for $i \geq 1$. It is this recursive relation that gives elegance to the solution for the case of GI/M/1 (and consequently QBD) Markov chains, but results in unfortunately more complicated mathematics for the case of the M/G/1-type.