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 (for the case of M/G/1-type processes) or (for the case of GI/M/1-type processes), and iterative procedures are used for determining or . Alternative algorithms for the computation of or have been proposed (e.g., the work of Latouche [46] for the efficient computation of and of Meini [60] for the efficient computation of ).

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 linear equations, where is the number of
states in the boundary portion of the process and 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 is partitioned into sets
, , instead of evaluating the probability distribution
of *all* states in each
, we calculate the *aggregate*
probability distribution of classes of states
, , appropriately defined
(see Figure 5.1).

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.

- 5.1 ETAQA-M/G/1

- 5.2 ETAQA-GI/M/1

- 5.3 ETAQA-QBD

- 5.4 Computational efficiency
- 5.5 Numerical stability of the method
- 5.6 MAMSolver

- 5.7 Chapter summary