This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Riska, A. Articles by Smirni, E. Search for Related Content

ETAQA Solutions for Infinite Markov Processes with Repetitive Structure

Seagate Research, 1251 Waterfront Place, Pittsburgh, Pennsylvania 15222, USA
Department of Computer Science, College of William and Mary, P.O. Box 8795, Williamsburg, Virginia 23187-8795, USA
alma.riska{at}seagate.com
esmirni{at}cs.wm.edu

We describe the ETAQA (efficient technique for the solution of quasi birth-death processes) approach for the exact analysis of M/G/1 and GI/M/1-type processes, and their intersection, i.e., quasi birth-death processes. ETAQA exploits the repetitive structure of the infinite portion of the chain and derives a finite system of linear equations. In contrast to the classic techniques for solution of such systems, the solution of this finite linear system does not provide the entire probability distribution of the state space, but simply allows calculation of the aggregate probability of a finite set of classes of states from the state space, appropriately defined. Nonetheless, these aggregate probabilities allow for computation of a rich set of measures of interest such as the system queue length or any of its higher moments. The proposed solution approach is exact and, for the case of M/G/1-type processes, compares favorably to the classic methods as shown by detailed time and space complexity analysis. Detailed experimentation further corroborates that ETAQA provides significantly less expensive solutions when compared to the classic methods.

Key words: M/G/1-type processes; GI/M/1-type processes; quasi birth-death processes; computer system performance modeling; matrix-analytic methods; Markov chains
History: received December 2003; revised November 2004; accepted July 2005.