5. ETAQA Methodology

In this chapter, we outline ETAQA, the methodology that we propose for solving and computing various measures of interests for GI/M/1-, M/G/1-type processes and their intersection, i.e., QBD processes. ETAQA stands for Efficient Technique for Analyzing QBD processes by Aggregation. Although we present ETAQA as a generalized methodology, it started as a technique to solve a special case of QBD processes [24]. ETAQA has a simple formalization, it is computationally efficient, numerically exact, yet provides enough information to conduct detailed analysis of the given process.

The traditional solution algorithms, described in Chapter 3, compute the stationary probability vector with a recursive function based on ${\mathbf{G}}$ (for the case of M/G/1-type processes) or ${\mathbf{R}}$ (for the case of GI/M/1-type processes), and iterative procedures are used for determining ${\mathbf{G}}$ or ${\mathbf{R}}$. Alternative algorithms for the computation of ${\mathbf{G}}$ or ${\mathbf{R}}$ have been proposed (e.g., the work of Latouche [46] for the efficient computation of ${\mathbf{R}}$ and of Meini [60] for the efficient computation of ${\mathbf{G}}$).

Distinctively from the classic techniques of solving M/G/1-type and GI/M/1-type processes, we recast the problem into solving a finite system of $m + 2n$ linear equations, where $m$ is the number of states in the boundary portion of the process and $n$ is the number of states in each of the repetitive ``levels''. The proposed methodology uses basic, well-known results for Markov chains. Assuming that the state space ${\cal {S}}$ is partitioned into sets ${\cal{S}}^{(j)}$, $j \geq 0$, instead of evaluating the probability distribution of all states in each ${\cal{S}}^{(j)}$, we calculate the aggregate probability distribution of $n$ classes of states ${\cal{T}}^{(i)}$, $1 \le i \le n$, appropriately defined (see Figure 5.1).

Figure 5.1: Aggregation of an infinite ${\cal {S}}$ into a finite number of states.

We note that our approach does not require any restriction on the form of the chain's repeating pattern, thus can be applied to any type of M/G/1, GI/M/1, or QBD chain. The proposed methodology is both efficient and exact, but also numerically stable. ETAQA does not require the calculation of steady state probabilities in explicit recursive form, yet it provides the means for calculating a rich set of measures of interest such as the expected queue length and any of its higher moments. Detailed comparisons with the traditional methods show that the proposed methodology results in significantly more efficient solutions for the case of M/G/1-type and QBD processes. For the case of GI/M/1-type processes, our methodology exhibits the same complexity as the traditional one for the computation of the stationary probability vector, but it results in more complex formulas when computing measures of interest.

This chapter is organized as follows. In Section 5.1, we present ETAQA for M/G/1-type processes, derive the computation of measures of interest, and analyze the complexity of the method with respect to both storage and computation requirements. Section 5.2 outlines ETAQA for GI/M/1-type processes, its computation of measures of interest, and its complexity analysis. In Section 5.3, we present ETAQA for QBD processes, show how to compute measures of interest, and conclude with its complexity analysis. Section 5.4 presents experimental results that demonstrate the computational efficiency of ETAQA for solution of M/G/1-type processes. In Section 5.5, we evaluate the numerical stability of ETAQA for M/G/1-type processes by comparing its performance with numerical stable matrix-analytic algorithms. In Section 5.6, we describe MAMSOLVER, a matrix-analytic methods tool that provides software implementations for ETAQA as well as the other existing state-of-the-art algorithms for the solution of M/G/1-type, GI/M/1-type and QBD processes. We conclude the chapter with a summary of the results.