Computer Science Department
School of Computer Science, Carnegie Mellon University


Analysis of a QBD Process that Depends on
Background QBD Processes

Takayuki Osogami

September 2004

Keywords: Markov chains, multi-dimensional state space, recursive foreground-background QBD process, recursive dimensionality reduction, approximation, analysis, task assignment, cycle stealing, matrix analytic methods.

We define a class of Markov chains that are called recursive foreground-background quasi-birth-and-death (RFBQBD) processes, and describe approximate (nearly exact) analyses of an RFBQBD process. An RFBQBD process consists of a foreground QBD process whose transitions depend on the level of a background QBD process, where the transitions of the background QBD process may depend on the level of another background QBD process, and this dependency may be repeated recursively. We also evaluate the running time and accuracy of the analyses numerically by applying them to analyze the performance of a particular task assignment policy in a multiserver system.

27 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by