A new paradigm in teletraffic analysis of communication networks

A large class of teletraffic analysis problems encountered in communication networks are based on Markov chains of M/G/1 and G/M/1 type, the study of which require numerically efficient and reliable algorithms to solve the nonlinear matrix equations arising in such chains. The traditional transform approach to solve these chains which requires root finding is known to cause problems when some roots are close or identical. The alternative iterative schemes based on matrix analytic methods have in general low linear convergence rates yielding a computation time bottleneck in solving large-scale probability models. We develop a novel algebraic theory for the solution of these chains based on which we propose numerically efficient algorithms. The key to our approach is an invariant subspace computation implemented using the matrix sign function iterations. These algorithms have high convergence rates unlike the linear convergence rates of existing algorithms, they are amenable to parallelization and can easily be implemented using standard linear algebra software packages