Bridging ETAQA and Ramaswami’s formula for the solution of M/G/1-type processes

M/G/1-type processes are often evaluated using matrix analytic methods. Specifically, Ramaswami’s recursive formula has been established as the numerically stable solution tool. Additionally, the ETAQA method, proposed previously, offers a more efficient alternative for the exact computation of a general class of metrics for M/G/1-type processes. However, the theoretical stability of ETAQA and its relation to Ramaswami’s method were not well understood. In this paper, we derive a new formulation that improves the numerical stability and computational performance of ETAQA. The resulting new method solves a homogeneous system of equations to obtain the aggregate probability of a finite set of classes of states from the state space of the underlying Markov chain. The new method, constructs this system of linear equations in a way similar to the method of Ramaswami, decoupling the computation of the probabilities of the first two initial classes of states from the computation of the aggregate probability. Because direct methods are used to solve this system, the decoupling implies an often significant speed-up over ETAQA. In addition, we show that the coefficients of the homogeneous system of equations define an M-matrix, which under certain conditions, is also diagonally dominant and thus can be factored stably. More importantly, we show that the new method is just an efficient way to implement Ramaswami’s method. We also discuss alternative normalization conditions for Ramaswami’s method. Our numerical experiments demonstrate the stability of our method for both stiff and well-behaved processes, and for both low and high system utilizations.