zbMATH — the first resource for mathematics

Markovian arrival and service communication systems: Spectral expansions, separability and Kronecker-product forms. (English) Zbl 0862.60089
Stewart, William J. (ed.), Computations with Markov chains. Proceedings of the 2nd international workshop on the numerical solution of Markov chains, Raleigh, NC, USA, January 16–18, 1995. Boston, MA: Kluwer Academic Publishers. 507-546 (1995).
Summary: In packet-switched communication networks information generation is bursty, resulting in traffic at multiplexers, switches and transmission channels which fluctuates randomly, often with a high correlation in time. Accurate models and efficient analytical techniques are needed to study these networks. We consider typical statistical multiplexing systems where traffic from many bursty sources is buffered if necessary and transmitted over channels (servers). We focus on models in which the traffic from each source is a Markov-modulated Poisson process and information units (packets) contain exponentially distributed number of bits. The capacity of the channels (servers) may be constant or Markov-modulated to reflect capacity sharing among systems. Utilising the structural properties of the model we derive theory and algorithms for the exact calculation of the spectral expansion of the buffer content distribution and from which performance measures are obtained. The efficiency of the method is derived from an algebraic theory, which gives the (exact) decomposition of the eigenvalue problem into small coupled problems, and expresses the eigenvectors in Kronecker-product form. When the sources/servers are identical or can be grouped into classes, the eigenvalues are given as roots of polynomials of small degree and the eigenvectors are given in closed form. We give a characterization of the dominant eigenvalue in the general setting of heterogeneous sources and servers, which is insightful and considerably reduces the computational burden. The results are useful in deriving bounds and approximations of tail probabilities. The approaches and techniques developed here extend naturally to more general Markovian sources and servers in the family of MAP processes. It is shown that the rate matrix in the matrix-geometric theory can be efficiently computed from our spectral representation regardless of traffic conditions.
For the entire collection see [Zbl 0940.00042].

60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)