Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-23T18:50:38.391Z Has data issue: false hasContentIssue false
  • English
  • Français

Analysis of separable Markov-modulated rate models for information-handling systems

Published online by Cambridge University Press:  01 July 2016

Thomas E. Stern  and
Anwar I. Elwalid
Thomas E. Stern*
Affiliation:
Columbia University
Anwar I. Elwalid*
Affiliation:
Columbia University
*
∗Postal address for both authors: Department of Electrical Engineering and Center for Telecommunications Research, Columbia University, New York, NY 10027, USA.
∗Postal address for both authors: Department of Electrical Engineering and Center for Telecommunications Research, Columbia University, New York, NY 10027, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

In many communication and computer systems, information arrives to a multiplexer, switch or information processor at a rate which fluctuates randomly, often with a high degree of correlation in time. The information is buffered for service (the server typically being a communication channel or processing unit) and the service rate may also vary randomly. Accurate capture of the statistical properties of these fluctuations is facilitated by modeling the arrival and service rates as superpositions of a number of independent finite state reversible Markov processes. We call such models separable Markov-modulated rate processes (MMRP).

In this work a general mathematical model for separable MMRPs is presented, focusing on Markov-modulated continuous flow models. An efficient procedure for analyzing their performance is derived. It is shown that the ‘state explosion' problem typical of systems composed of a large number of subsystems, can be circumvented because of the separability property, which permits a decomposition of the equations for the equilibrium probabilities of these systems. The decomposition technique (generalizing a method proposed by Kosten) leads to a solution of the equilibrium equations expressed as a sum of terms in Kronecker product form. A key consequence of decomposition is that the computational complexity of the problem is vastly reduced for large systems. Examples are presented to illustrate the power of the solution technique.

Keywords

KRONECKER PRODUCT FORMCONTINUOUS FLOW MODEL
Type
Research Article
Information
Advances in Applied Probability , Volume 23 , Issue 1 , March 1991 , pp. 105 - 139
Copyright
Copyright © Applied Probability Trust 1991 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Part of this work was performed when the first author was on sabbatical leave at INRIA Centre de Sophia Antipolis 06565 Valbonne, France. This work was partially supported by the National Science Foundation under grant CDR-84-21402, and the office of Naval Research under grant N00014-85-k0371.

References

1. Anick, D., Mitra, D. and Sondhi, M. M. (1982) Stochastic theory of a data-handling system with multiple sources. Bell System Tech. J. 61, 1871–1894.Google Scholar
2. Bellman, R. (1960) Introduction to Matrix Analysis. McGraw-Hill, New York.Google Scholar
3. Brewer, J. W. (1978) Kronecker products and matrix calculus in system theory. IEEE Trans. Circuits Syst. 25, 772–781.Google Scholar
4. Burman, D. Y. and Smith, D. R. (1986) An asymptotic analysis of a queueing system with markov-modulated arrivals. Operat. Res. 34, 05–119.Google Scholar
5. Elwalid, A. E., Mitra, D. and Stern, T. E. (1990) A theory of statistical multiplexing of markovian sources: spectral expansions and algorithms. In Numerical Solution of Markov Chains , ed. Stewart, W. J., Marcel Dekker, New York.Google Scholar
6. Fischer, M. J. (1979) Data performance in a system where data packets are transmitted during voice silent periods—single channel case. IEEE Trans. Comm. 27, 1371–1375.CrossRefGoogle Scholar
7. Franklin, J. N. (1968) Matrix Theory. Prentice Hall, Englewood Cliffs, NJ.Google Scholar
8. Graham, A. (1981) Kronecker Products and Matrix Calculus with Applications. Ellis Horwood, Chichester.Google Scholar
9. Keilson, J. and Rao, S. S. (1970) A process with chain-dependent growth rate. J. Appl. Prob. 7, 699–711.Google Scholar
10. Keilson, J. and Rao, S. S. (1971) A process with chain-dependent growth rate. part II: the ruin and ergodic problems. Adv. Appl. Prob. 3, 315–338.Google Scholar
11. Keilson, J. (1979) Markov Chain Models—Rarity and Exponentiality. Springer-Verlag, New York.Google Scholar
12. Kelly, F. P. (1979) Reversibility and Stochastic Networks. Wiley, Chichester.Google Scholar
13. Kosten, L. (1984) Stochastic theory of data-handling systems with groups of multiple sources. In Performance of Computer-Communication Systems , ed. Ruding, H. and Bux, W., Elsevier, Amsterdam, 321–331.Google Scholar
14. Kosten, L. (1986) Liquid models for a type of information buffer problems. Delft Progress Report 11, 71–86.Google Scholar
15. Mitra, D. (1988) Stochastic theory of a fluid model of producers and consumers coupled by a buffer, Adv. Appl. Prob. 20, 646–676.Google Scholar
16. Mitrani, I. (1968) A many server queue with service interruptions. Operat. Res. 16, 628–638.Google Scholar
17. Morrison, J. (1989) Asymptotic analysis of a data-handling system with many sources, SIAM J. Appl. Math. 49, 617–637.Google Scholar
18. Neuts, M. (1981) Matrix Geometric Solutions in Stochastic Systems. Johns Hopkins University Press, Baltimore.Google Scholar
19. Neuts, M. (1986) The caudal characteristic curve of queues. Adv. Appl. Prob. 18, 221–254.Google Scholar
20. Rellich, F. (1969) Perturbation Theory of Eigenvalue Problems. Gordon and Breach, New York.Google Scholar
21. Schwartz, M. (1987) Telecommunication Networks, Protocols, Modeling and Analysis . Addison-Wesley, Reading, Mass.Google Scholar
22. Stern, T. E. (1983) A queueing analysis of packet voice. Proc. GLOBECOM '83 , 71–76.Google Scholar
23. Stern, T. E. and Elwalid, A. I. (1989) Analysis of separable markov-modulated rate models for information-handling systems. CTR technical report No. 164–89–43, Columbia University.Google Scholar
24. Weiss, A. (1986) A new technique for analyzing large traffic systems. Adv. Appl. Prob. 18, 506–532.Google Scholar