×

An application of deterministic chaotic maps to model packet traffic. (English) Zbl 0836.60103

Summary: We investigate the application of deterministic chaotic maps to model traffic sources in packet based networks, motivated in part by recent measurement studies which indicate the presence of significant statistical features in packet traffic more characteristic of fractal processes than conventional stochastic processes. We describe one approach whereby traffic sources can be modeled by chaotic maps, and illustrate the traffic characteristics that can be generated by analyzing several classes of maps. We outline a potential performance analysis approach based on chaotic maps that can be used to assess the traffic significance of fractal properties. We show that low order nonlinear maps can capture several of the fractal properties observed in actual data, and show that the source characteristics observed in actual traffic can lead to heavy-tailed queue length distributions. It is our conclusion that while there are considerable analytical difficulties, chaotic maps may allow accurate, yet concise, models of packet traffic, with some potential for transient and steady state analysis.

MSC:

60K25 Queueing theory (aspects of probability theory)
90B18 Communication networks in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Abate, G.L., Choudhury and W. Whitt, Waiting time probability in queues with long-tail service distributions, to appear in Queueing Systems. · Zbl 0805.60097
[2] D. Anick, D. Mitra and M. Sondhi, Stochastic theory of a data handling system with multiple sources, BSTJ 61 (1982) 1871-1894.
[3] J. Banks, J. Brooks, G. Cairns, G. Davis and P. Stacy, On Devaney’s definition of chaos, Amer. Math. Monthly 99 (1992) 332-334. · Zbl 0758.58019
[4] J. Beran, R. Sherman, M.S. Taqqu and W. Willinger, Variable bit rate video traffic and long range dependence, accepted for publication in IEEE/ACM Trans. Networking, subject to revisions.
[5] P. Collet and J.-P. Eckmann, Iterated maps on the interval as dynamical systems, in:Progress in Physics, Vol. 1 (Birkhaeuser, Boston, MA, 1980). · Zbl 0458.58002
[6] R.B. Cooper,Introduction to Queueing Theory, 2nd Ed. (North-Holland, 1981). · Zbl 0486.60002
[7] D. Cox, Long-range dependence: A review, in:Statistics: An Appraisal, eds. David and David (The Iowa State University Press, 1984).
[8] R.L. Devaney,An Introduction to Chaotic Dynamical Systems, 2nd Ed. (Addison-Wesley, 1989). · Zbl 0695.58002
[9] A. Erramilli and L.J. Forys, Oscillations and chaos in a flow model of a switching system, IEEE JSAC (April 1990).
[10] A. Erramilli and L. Forys, Traffic synchronization effects in teletraffic systems,Proc. ITC-13, Copenhagen (1991).
[11] A. Erramilli, D. Gosby, W. Willinger, Engineering for realistic traffic: A fractal analysis of burstiness,Proc. Special ITC Seminar, Bangalore, India (1993).
[12] A. Erramilli and R.P. Singh, Application of deterministic chaotic maps to characterize broadband traffic,7th ITC Specialists Seminar, Morristown (1990).
[13] A. Erramilli, R.P. Singh and P. Pruthi, Modeling packet traffic with chaotic maps, Royal Institute of Technology, ISRN KTH/IT/R-94/18-SE, Stockholm-Kista, Sweden (1994). · Zbl 0836.60103
[14] A. Erramilli and W. Willinger, Fractal properties in packet traffic measurements,Proc. ITC Regional Seminar, St. Petersburg (1993).
[15] A. Erramilli, W. Willinger and P. Pruthi, Fractal traffic flows in high-speed communications networks, Fractals 2(3) (1994). · Zbl 0906.90065
[16] K. Falconer,Fractal Geometry: Mathematical Foundations and Applications (Wiley, 1993).
[17] B. Fontana and A. Guerrero, Packet traffic characterization, arrival laws and waiting times,Proc. ITC-12, Turin, Italy (1988).
[18] H.J. Fowler and W.E. Leland, Local area network traffic characteristics, with implications for broadband network congestion management, IEEE JSAC (1991) 1139-1149.
[19] D. Gulick,Encounters with Chaos (McGraw-Hill, 1992). · Zbl 1253.37001
[20] H. Heffes and D.M. Lucantoni, A Markov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance, IEEE JSAC 6 (1986) 856-868.
[21] F.Y. Hunt and W. Miller, On the approximation of invariant measures, J. Stat. Phys. 66(1, 2) (1992). · Zbl 0892.58048
[22] R. Jain and S. Routhier, Packet trains: Measurements and a new model for computer network traffic, IEEE JSAC 6 (1986) 986-995.
[23] A. Lasota and M.C. Mackey,Chaos, Fractals, and Noise ? Stochastic Aspects of Dynamics, 2nd Ed. (Springer, 1994). · Zbl 0784.58005
[24] G. Latouche and V. Ramaswami, A logarithmic reduction algorithm for quasi birth and death processes, J. Appl. Prob. 30 (1993) 650-674. · Zbl 0789.60055
[25] W.E. Leland, M.S. Taqqu, W. Willinger and D.V. Wilson, On the self-similar nature of Ethernet traffic, IEEE/ACM Trans. Networking 2(1) (1994).
[26] W.E. Leland and D.V. Wilson, High time resolution measurements and analysis of LAN traffic: Implications for LAN interconnection,Proc. IEEE Infocom ’91, Bal Harbor, FL (1991).
[27] T.Y. Li and J.A. Yorke, Ergodic maps on [0,1] and nonlinear pseudorandom number generators, Nonlinear Anal. 2 (1978) 473-481. · Zbl 0407.28011
[28] L.S. Liebovitch and T.I. Toth, Ion channel kinetics: Random or deterministic process?, Biophys. J. 57 (1990) 317a.
[29] B. Mandelbrot,The Fractal Geometry of Nature (Freeman, New York, 1983). · Zbl 1194.30028
[30] M. Martelli,Discrete Dynamical Systems and Chaos (Longman Scientific & Technical, 1992). · Zbl 0819.34001
[31] K. Meier-Hellstern, P. Wirth, Y-L. Yan and D. Hoeflin, Traffic models for ISDN data users: Office automation application,Proc. ITC-13, Copenhagen (1991).
[32] B. Melamed, D. Raychaudhuri, B. Sengupta and J. Zdepski, TES-based traffic modeling for performance evaluation of integrated networks,Proc. Infocom ’92, Florence, Italy (1992).
[33] A.R. Murch and R.H. Bates, Colored noise generation through deterministic chaos, IEEE Trans. Circuits and Syst. 37 (1990) 608-613.
[34] I. Norros, A storage model with self-similar input, to appear in Queueing Systems. · Zbl 0811.68059
[35] H-O. Peitgen, H. Jürgens and D. Saupe,Chaos and Fractals ? New Frontiers of Science (Springer, 1992). · Zbl 0779.58004
[36] V. Ramaswami, Traffic performance modeling for packet communication: Whence, where and whither,Proc. Australian Teletraffic Seminar (1988).
[37] V. Ramaswami and G. Latouche, Modeling packet arrivals from asynchronous input lines,Proc. ITC-12, Turin (1987).
[38] V. Ramaswami, M. Rumsewicz, W. Willinger and T. Eliazov, Comparison of some traffic models for ATM performance studies,Proc. ITC-13, Copenhagen (1991).
[39] M.H. Rossiter, The switched Poisson process and the SPP/G/1 queue,Proc. ITC-12, Turin, Italy (1988).
[40] H.G. Schuster,Deterministic Chaos: An Introduction, 2nd revised Ed. (VCH, 1988). · Zbl 0707.58003
[41] K. Sriram and W. Whitt, Characterizing superposition arrival processes and the performance of multiplexes for voice and data, IEEE JSAC 6 (1986) 833-846.
[42] M.S. Taqqu and J.B. Levy, Using renewal processes to generate long range dependence and high variability,Dependence in Probabilty and Statistics, Progress in Prob, and Vol 11 (Birkhauser; Boston, 1986) pp. 73-89. · Zbl 0601.60085
[43] P. Tran-Gia, A renewal approximation for the generalized Poisson process,Proc. Int. Workshop on App. Math, and Performance/Reliability Models in Computer / Communication Systems, Pisa, Italy (1983).
[44] D. Veitch, Novel models of broadband traffic,Proc. 7th Australian Teletraffic Research Seminar, Murray River, Australia (1992). · Zbl 0776.93031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.