A generalization of the matrix M/G/l paradigm for Markov chains with a tree structure

Abstract

Abstract In this paper, we generalize the theory of the M/G/l paradigm to tree-like structures. There are two variables in the Markov chain, one of which takes values on the nodes of a d-ary tree. The other is an auxiliary variable, which takes one of m possible values. For this structure, the steady state probability depends on d matrices, which are solutions of a system of non-linear matrix equations. We also apply the theory to a multiple class last-come-first-served queue in which no preemption is allowed Keywords: Tree structureM/G/l paradigmLCFS servicequeues 1The work of Raymond Yeung was supported in part by the Research Grant Council of Hong Kong under Earmarked Grant CUHK 271/94E 1The work of Raymond Yeung was supported in part by the Research Grant Council of Hong Kong under Earmarked Grant CUHK 271/94E Notes 1The work of Raymond Yeung was supported in part by the Research Grant Council of Hong Kong under Earmarked Grant CUHK 271/94E