A graph-theoretic approach to queueing analysis part i: theory

Abstract

Traditionally, solving a system of linear equations by Gaussian elimination has been formulated as a graph elimination problem. The matrix M is represented by a directed graph (or an undirected graph when M is symmetric). The elimination ordering of variables is found to greatly affect the time complexity of the solution process if M is sparse. As the problem of finding the optimal ordering, i.e., the one which gives the fewest operation counts, is NP-complete, many heuristics have been found to obtain a near-optimal ordering for the problem. All these algorithms do not consider the numerical values of the non-zero entries of M. We refer this approach as the conventional approach. In this paper, it is shown that queueing problem for solving and can also be represented as a graph elimination problem where πis the stationary distribution vector and Q is the rate transition matrix. It is also shown that the elimination speed can be increased substantially if the numerical values are also considered when Q has certain “repeated structures,” which is common in the context of queueing problems with finite buffer. An approach which takes advantage of the repeated structure of Q to construct fast algorithms for the solution of the queueing problem is developed. Application of the approach to solving different complex queueing problems is discussed in part II of this paper.

Keywords:

• Finite-state Markov chain
• Gaussian elimination
• graph elimination
• fast algorithms

¹The work of this author was supported in part by the Research Grant Council of Hong Kong under Earmarked Grant CUHK 271 /94E. Please send all correspondence to this author

¹The work of this author was supported in part by the Research Grant Council of Hong Kong under Earmarked Grant CUHK 271 /94E. Please send all correspondence to this author

Notes

¹The work of this author was supported in part by the Research Grant Council of Hong Kong under Earmarked Grant CUHK 271 /94E. Please send all correspondence to this author