Markov-modulated rate processes for modeling, analysis and control of communication networks

Abstract

High speed integrated communication networks such as Broadband ISDN using Asynchronous Transfer Mode (ATM) support multitudes of services of different characteristics. In many applications information is generated in a bursty fashion, resulting in traffic demands on multiplexers, switches, transmission media and processors which fluctuate randomly, often with a high degree of correlation in time. Performance analysis to facilitate design tasks, including buffer dimensioning, bandwidth allocation and specification of control functions requires accurate models and efficient analytical techniques. In this thesis we consider a class of models called Markov-modulated rate processes (MMRP) which capture the time correlation and burstiness of traffic flows in the network. The flow rate in these models depends on the state of a Markov process. The models provide a level of accuracy which depends on the dynamics and the number of states of the underlying Markov process. In some applications the information flow is modeled as a Markov-modulated continuous flow (fluid) process, while in others, a point process model, e.g. Markov-modulated Poisson process, is appropriate. Utilizing the structural properties of the models, we develop efficient analytical techniques for handling buffer systems where the arrival and service processes are superpositions of many MMRP's. We give an efficient algorithm for computing the elements of the spectral expansion of the buffer content distribution, whose complexity is independent of traffic intensity and burstiness. The efficiency of the algorithm is derived from an algebraic theory which gives the (exact) decomposition of the eigenvalue problem of the entire system into many small coupled eigenvalue problems, and expresses the eigenvectors in Kronecker-product form. In systems where the processes are identical or can be grouped into classes, we follow a novel approach which overcomes the limitations of previous work in the area. Our approach consists of two phases. In phase one the analysis is carried out oblivious to source homogeneity whereby the Kronecker product form is preserved. In phase two a transition is made to the aggregated system where source homogeneity is taken into account to arrive at a minimal state representation. The result is that the eigenvalues are given as roots of a family of polynomials of small degree and the eigenvectors are given in closed form. Our results for fluid models represent important extension and generalization of previous works. In point process queueing models described by quasi-birth-death processes, we show that the rate matrix in the matrix geometric solution can be efficiently computed from its spectral decomposition. The models and analytical techniques are applied to the problems of statistical multiplexing and buffer dimensioning, bandwidth allocation and congestion control in high speed networks. The accuracy of the models is validated by computer simulation.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 13 citations exist upstream.