Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-17T19:15:48.386Z Has data issue: false hasContentIssue false
  • English
  • Français

Markov-modulated traffic with nearly complete decomposability characteristics and associated fluid queueing models

Part of: Special processes

Published online by Cambridge University Press:  01 July 2016

Kimon P. Kontovasilis  and
Nikolas M. Mitrou
Kimon P. Kontovasilis*
Affiliation:
National Technical University of Athens
Nikolas M. Mitrou*
Affiliation:
National Technical University of Athens
*
* Postal address: Electrical and Computing Engineering, Computer Science Division, National Technical University of Athens, 9 Iroon Polytechneioy Street, Zografoy G.R. 15773, Greece.
* Postal address: Electrical and Computing Engineering, Computer Science Division, National Technical University of Athens, 9 Iroon Polytechneioy Street, Zografoy G.R. 15773, Greece.
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper considers fluid queuing models of Markov-modulated traffic that, due to large differences in the time-scales of events, possess structural characteristics that yield a nearly completely decomposable (NCD) state-space. Extension of domain decomposition and aggregation techniques that apply to approximating the eigensystem of Markov chains permits the approximate subdivision of the full system to a number of small, independent subsystems (decomposition phase), plus an ‘aggregative' system featuring a state-space that distinguishes only one index per subsystem (aggregation phase). Perturbation analysis reveals that the error incurred by the approximation is of an order of magnitude equal to the weak coupling of the NCD Markov chain.

The study in this paper is then extended to the structure of NCD fluid models describing source superposition (multiplexing). It is shown that efficient spectral factorization techniques that arise from the Kronecker sum form of the global matrices can be applied through and combined with the decomposition and aggregation procedures. All structural characteristics and system parameters are expressible in terms of the individual sources multiplexed together, rendering the construction of the global system unnecessary.

Finally, besides providing efficient computational algorithms, the work in this paper can be recast as a conceptual framework for the better understanding of queueing systems under the presence of events happening in widely differing time-scales.

Keywords

PERTURBATIONMULTIPLEXINGSPECTRAL FACTORIZATIONSOURCE SUPERPOSITION

MSC classification

Primary: 60K25: Queueing theory
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 27 , Issue 4 , December 1995 , pp. 1144 - 1185
Copyright
Copyright © Applied Probability Trust 1995 

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.)

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] Baiocchi, A., Blefari-Melazzi, N., Roveri, A. and Salvatore, F. (1992) Stochastic fluid analysis of an ATM multiplexer loaded with heterogeneous ON-OFF sources: an effective computational approach. In Proc. INFOCOM '92, pp. 3C.3.1–3C.3.10.Google Scholar
[3] Cao, W. L. and Stewart, W. J. (1985) Iterative aggregation/disaggregation techniques for nearly uncoupled Markov chains. J. Assoc. Comput. Mach. 32, 702–719.Google Scholar
[4] Courtois, P. J. (1977) Decomposability: Queueing and Computer System Applications. Academic Press, New York.Google Scholar
[5] Elwalid, A. I., Mitra, D. and Stern, T. E. (1991) Statistical multiplexing of markov modulated sources: theory and computational algorithms. In Proc. 13th ITC, ed. Jensen, A. and Iversen, B. V.. Elsevier, Amsterdam.Google Scholar
[6] Kontovasilis, K. P. and Mitrou, N. M. (1994) Bursty traffic modeling and efficient analysis algorithms via fluid-flow models for ATM-IBCN. Ann. Operat. Res. 49, 279–323. Special Issue in Methodologies for High Speed Networks.Google Scholar
[7] Kosten, L. (1984) Stochastic theory of data-handling systems with groups of multiple sources. In Performance of Computer Communication Systems, ed. Rudin, H. and Bux, W., pp. 321–331. Elsevier, Amsterdam.Google Scholar
[8] Koury, J. R., Mcallister, D. F. and Stewart, W. J. (1984) Iterative methods for computing stationary distributions for nearly completely decomposable Markov chains. SIAM J. Alg. Disc. Meth. 5, 164–186.CrossRefGoogle Scholar
[9] Kröner, H., Theimer, T. H. and Briem, U. (1990) Queueing models for ATM systems-a comparison. In Proc. 7th ITC Seminar, Morristown, NJ, 9-11 October, 1990.Google Scholar
[10] Mcallister, D. F., Stewart, G. W. and Stewart, W. J. (1984) On a Rayleigh-Ritz refinement technique for nearly uncoupled stochastic matrices. Linear Agebra Appl. 60, 1–25.Google Scholar
[11] 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
[12] Norros, I., Roberts, J. W., Simonian, A. and Virtamo, J. T. (1991) The superposition of variable bit rate sources in an ATM multiplexer. IEEE JSAC 9, 378–387.Google Scholar
[13] Schweitzer, P. J. (1984) Aggregation methods for large Markov chains. In Mathematical Computer Performance and Reliability, ed. Iazeolla, G., Courtois, P. J., and Hordijk, A., pp. 275–286. North-Holland, Amsterdam.Google Scholar
[14] Schweitzer, P. J. (1990) Survey of aggregation-disaggregation in large Markov chains. In Proc. 1st International Workshop on the Numerical Solution of Markov Chains, pp. 54–80. NCSU, Raleigh, NC, 8-10 January, 1990.Google Scholar
[15] Simon, H. A. and Ando, A. (1961) Aggregation of variables in dynamic systems. Econometrica 29, 111–138.Google Scholar
[16] Stern, T. E. and Elwalid, A. I. (1991) Analysis of separable Markov-modulated rate models for information-handling systems. Adv. Appl. Prob. 23, 105–139.Google Scholar
[17] Stewart, W. J. and Wei, W. (1992) Numerical experiments with iteration and aggregation for Markov chains. ORSA J. Computing, August.Google Scholar
[18] Takahashi, Y. (1975) A lumping method for numerical calculations of stationary distributions of Markov chains. Technical Report No B-18, Department of Information Sciences, Tokyo Institute of Technology, Tokyo, Japan.Google Scholar
[19] Wilkinson, J. H. (1965) The Algebraic Eigenvalue Problem. Clarendon Press, Oxford.Google Scholar