A Theory of Statistical Multiplexing of Markovian Sources: Spectral Expansions and Algorithms

This paper considers the problem of exactly calculating the stationary-state distribution of a system that statistically multiplexes the output of K sources. Each source is an N-state Markov chain and its Poisson rate of packet generation is determined by its state. Since Broadband ISDN (B-ISDN) will statistically multiplex many bursty sources and the burstiness can be modeled by Markov chains, the efficient analyses of large examples of the model considered here are an essential requirement for B-ISDN design. An algorithm is given for the spectral expansion of the state distribution whose complexity is o (K3(N-1)) for N fixed and K large. The efficiency of the algorithm is derived from an algebraic theory that gives the (exact) decomposition of the eigenvalue problem of the entire system into many small eigenvalue problems, and 224also gives the Kronecker product form to the eigenvectors; another important element is a recursive algorithm for (exact) aggregation.