Finite and Infinite QBD Chains: A Simple and Unifying Algorithmic Approach

In this paper, we present a novel algorithmic approach, the hybrid matrix geometric/invariant subspace method, for finding the stationary probability distribution of the finite QBD process which arises in performance analysis of computer and communication systems. Assuming that the QBD state space is defined in two dimensions with m phases and K + 1 levels, the solution vector for level k, ß k ; 0 k K is shown to be in a modified matrix geometric form ß k = v 1 R k 1 + v 2 R K \Gammak 2 where R 1 and R 2 are certain solutions to two nonlinear matrix equations and v 1 and v 2 are vectors to be determined using the boundary conditions. We show that the matrix geometric factors R 1 and R 2 can simultaneously be obtained independently of K via finding the sign function of a real matrix by an iterative algorithm with quadratic convergence rates. The time complexity of obtaining the coefficient vectors v 1 and v 2 is shown to be O(m 3 log 2 K) which indicates that the contributi..