Title :
Exact analysis of a class of GI/G/1-type performability models
Author :
Riska, Alma ; Smirni, Evgenia ; Ciardo, Gianfranco
Author_Institution :
Seagate Res., Pittsburgh, PA, USA
fDate :
6/1/2004 12:00:00 AM
Abstract :
We present an exact decomposition algorithm for the analysis of Markov chains with a GI/G/1-type repetitive structure. Such processes exhibit both M/G/1-type & GI/M/1-type patterns, and cannot be solved using existing techniques. Markov chains with a GI/G/1 pattern result when modeling open systems which accept jobs from multiple exogenous sources, and are subject to failures & repairs; a single failure can empty the system of jobs, while a single batch arrival can add many jobs to the system. Our method provides exact computation of the stationary probabilities, which can then be used to obtain performance measures such as the average queue length or any of its higher moments, as well as the probability of the system being in various failure states, thus performability measures. We formulate the conditions under which our approach is applicable, and illustrate it via the performability analysis of a parallel computer system.
Keywords :
Markov processes; computer network reliability; matrix decomposition; open systems; parallel processing; queueing theory; GI/G/1; GI/M/1; M/G/1; Markov chain; average queue length; exact decomposition algorithm; matrix analytic techniques; multiple exogenous source; open system; parallel computer system; performability; single failure; stationary probability; stochastic complementation; Algorithm design and analysis; Computer science; Hardware; High performance computing; Length measurement; Open systems; Performance analysis; Performance evaluation; Risk analysis; Software quality; GI/G/1; GI/M/1; M/G/1; Markov chains; matrix analytic techniques; performability; stochastic complementation;
Journal_Title :
Reliability, IEEE Transactions on
DOI :
10.1109/TR.2004.829134