Source: https://sic.ici.ro/past-issues/volume19-issue1-2010/millan/
Timestamp: 2019-04-25 19:49:11+00:00

Document:
Abstract: A qualitative and quantitative extension of the chaotic models used to generate self-similar traffic with long range dependence LRD is presented by means of the formulation of a model that considers the use of piecewise affine one-dimensional maps. Based on the disaggregation of the temporal series generated, a valid explanation of the behavior of the values of Hurst’s exponents is proposed and the feasibility of their control from the parameters of the proposed model is shown.
Keywords: Chaos, chaotic maps, Hurst exponent, self-similarity, traffic modeling in computer networks.
Ginno MILLAN, Héctor KASCHEL, Gastón LEFRANC, A Simple Model for the Generation of LRD Self-similar Traffic Using Piecewise Affine Chaotic One-dimensional Maps, Studies in Informatics and Control, ISSN 1220-1766, vol. 19 (1), pp. 67-78, 2010.
The chaotic behavior of systems is an intermediate paradigm between two dogmatic scientific and philosophical concepts of the universe: absolute knowledge upheld by determinism, and total ignorance at the hands of randomness. Paradoxically, and supported by the existence of the above two dogmatic positions, an assertion as natural as the one made points at the main failure in the analysis of systemic behaviors: the extended use of dichotomies to characterize them.
It is in this scenario that the theory of chaos, defined by Kellert as the qualitative study of periodic and unstable behavior in deterministic and nonlinear dynamic systems , invades and establishes the omnipresence of unpredictability as a fundamental trait of common experience . Then, the theory of chaos, instead of trying to understand the behavior of systems in a merely quantitative manner to determine exactly their future states, it concerns with understanding of a long-term behavior, searching for patterns under a holistic philosophy rather than a reductive philosophy.
As can be seen and inferred from the ideas given above, and in full agreement with the spirit of this research, it is neither possible nor practical to approach the problem of the characterization of the behavior of the systems of interest considering the full conceptual extension of the theory of chaos, and for that reason it is accepted that chaos is the phenomenon by which low-order non-linear systems show an apparently random complexity and behavior . These systems are of low order because they can be described correctly by a reduced number of variables and parameters. They are also dynamic systems, i.e., with the variables of interest, which are deterministic, evolve over time, because the values of those variables at any instant of time can be determined only from their previous values given a set of dynamic laws. Finally, those dynamic laws that describe the system evolution in time are nonlinear (they do not fulfill the superposition principle) .
At this point it is convenient to make it clear that chaotic systems differ from conventional dynamic systems in the sense that they are intrinsically unpredictable, a fact that is evident even when its subjacent dynamic laws are of a deterministic character. But the above does not have to lead to the belief that chaos implies unpredictability, since that is only partially true because of the existence of two main sources of unpredictability, namely the inaccuracy of the initial data, and its origin as a characteristic inherent to certain nonlinear relations between numerical variables . Therefore, the definition of chaos as a property of a system refers to its sensitivity to the initial conditions, i.e. that given two trajectories arbitrarily close to one another in the phase space of a chaotic system, they diverge at an exponential rate given by Lyapunov’s global exponent.
Note that it is certainly paradoxical for an essentially deterministic system, with deterministic dynamic laws, to show a chaotic behavior, since the basic premise of dynamic systems is that the knowledge of the initial conditions makes possible the determination of the system’s future behavior at any time. In practice, the initial conditions can only be specified with finite precision. These uncertainties introduced in the initial conditions for the case of chaotic systems increase exponentially, and that explains the unpredictability of their behavior. Strictly, chaos involves the possibility of making good short-term predictions, but it makes impossible any long term prediction of a practical order . A direct result of the above is that very simple systems, even with only one degree of freedom, such as those reported in  and , can give rise to surprisingly complex behaviors.
The notion of chaos often appears linked to the notion of fractal introduced by Mandelbrot , and even though it has not been proved rigorously, fractal properties seem inherent in chaotic processes, so apparently chaos and fractal sets are independent and unrelated concepts , . However, keeping in mind that the fractal dimension concept raises a generalization of the notion of dimension through the introduction of the non-integer values for their specification, an extensively reported fact in its applications ; unexpectedly all chaotic systems tend to evolve asymptotically in their phase space toward a bounded region called strange attractor that has a non-integer dimension, i.e., a fractal. It can thus be argued that very often the strange attractors are fractals in their nature and are capable of exhibiting their complexity over different time or space scales. Because of the above it is therefore possible to state that the concepts of fractal geometry can be used to describe the evolutionary characteristics of chaotic systems, and chaotic systems in turn can be used conveniently as generators of fractal structures, thereby implying self-similarity and therefore its characterization index: Hurst’s exponent (H).
It should be pointed out that since there is no simple definition of fractals, they are generally defined in terms of their attributes, such as, for example, the slow decay of their variances, the hyperbolic tail distribution of the time density between successive arrivals, the infinite order moments or poorly defined statistics, 1/f noise, long range dependence, self-similarity, and the previously mentioned non-integer dimension, among others -. The presence of such characteristics in the traffic flows of actual high speed computer networks is, therefore, the ultimate aim of the whole discussion presented.
Statistically, self-similar behavior of traffic flows in the present settings of high speed computer networks, is a fact that has been extensively reported for the different levels of telematics systems coverage -, transmission technologies -, control and signaling protocols , , and applications, particularly in video -.
Similarly, the problem of the characterization of traffic has received considerable attention in the literature, giving rise to a number of proposals of stochastic models, among which we can name, without the list being exhaustive, Generalized Switched Poisson Processes (GSPP) , Markov Modulated Poisson Processes (MMPP) , Switched Poisson Processes (SPP) , Fractal Point Processes (FPP) , , Alternating Fractal Renewal Processes (AFRP) and their Extended Alternating Fractal Renewal Process (EAFRP) variant , , those based on intermittent chaotic maps , , -, and the traditional processes of fractional Gaussian noise (fGn) and fractional Brownian motion (fBm) -.
However, and in spite of all the efforts underlying the arguments and methodologies stated above, two problem situations inherent in the generation of traffic with long range dependence are ubiquitous, namely the degree of representatives of Hurst’s exponent as a unique parameter for characterizing its effects on the performance of the tails systems in which it appears, and the behavior shown by its value in the self-similar second order series obtained within the interval of interest 0.5 < H < 1.0. In this respect, - show in an isolated way both problems and their implications. Then, the set of both problem situations, and particularly that of their final repercussions on the systems that are being studied, are called locality of Hurst’s exponent.
Putting our attention on the existing set of models that use one-dimensional chaotic maps, this work presents an extension of them with the incorporation of piecewise affine maps to produce a self-similar traffic model with long range dependence that also provides an explanation for the locality of Hurst’s exponent for the generated traffic and mitigates its effects.
In this paper, a qualitative and quantitative extension of the chaotic models used to generate self-similar traffic with long range dependence is presented by means of the formulation of a model considering the use of piecewise affine one-dimensional maps. Based on the disaggregation of the temporal series generated, a valid explanation of the behavior of the values of Hurst’s exponents is proposed and the feasibility of their control from the parameters of the proposed model is shown.
KELLERT, S. H., In the Wake of Chaos. Chicago, IL: The University of Chicago Press, 1993, p. 2.
MALE, S., Finding a Horseshoe on the Beaches of Rio, The Mathematical Intelligencer, vol. 20(1), pp. 39-44, 1998.
ERRAMILLI, A., R. P. SINGH, P. PRUTHI, Chaotic Maps as Models of Packet Traffic, in The Fundamental Role of Teletraffic in the Evolution of Telecommunications Networks, Labetoulle, J., and Roberts, J. W., Eds. Amsterdam: Elsevier, 1994, pp. 329-338.
ERRAMILLI, A., SINGH, R. P., P. PRUTHI, Modeling Packet Traffic with Chaotic Maps, Royal Inst. Tech., Stockholm, Sweden, Tech. Rep. ISRN KTH/IT/R-94/18-SE, Aug. 1994.
MAHNER, M., M. BUNGE, Fundamentos de Biofilosofía, México, Ed. Siglo Veintiuno, 2000, pp. 220-221.
LUENGO, D., Estimación de secuencias caóticas con aplicación en comunicaciones, Ph.D. diss., Dept. Ing. Com., Univ. Cantabria, España, 2006.
MAY, R. M., Biological Populations with Nonoverlapping Generations: Stable Points, Stable Cycles and Chaos, Science, vol. 186 (4164), Nov. 1974, pp. 645-647.
MAY, R. M., Simple Mathematical Models with Very Complicated Dynamic, Nature, vol. 261(5560), Jun. 1976, pp. 459-467.
MANDELBROT, B. B., Les Objets Fractals: Forme, Hasard et Dimension, Paris, France: Flammarion, 1975.
QUINTERO, C. J. (2005, Feb.).Visualización de atractores extraños de sistemas dinámicos caóticos. Univ. Málaga. [Online]. http://www.lcc.uma.es/.
MANDELBROT, B. B., The Fractal Geometry of Nature, New York: W. H. Freeman and Company, 1983.
FLOYD, S., V. PAXSON, Difficulties in Simulating the Internet, IEEE/ACM Trans. Netw., vol. 9, Aug. 2001, pp. 392-403.
PARK, K., W. WILLINGER, Self-Similar Network Traffic and Performance Evaluation. New York: Wiley, 2000.
RESNICK, S. I., Heavy Tail Modeling and Teletraffic Data, Annals Statist., vol. 25, 1997, pp. 1805-1869.
WILLINGER, W., The Discovery of Self-similar Traffic, in Performance Evaluation: Origins and Directions, Haring, G., Lindermann, C., and Reiser, M., Eds. Berlin, Germany: Springer-Verlag, vol. 1769, 2000, pp. 493-505.
WILLINGER, W., V. PAXSON, Where Mathematics Meets the Internet, Notices of the AMS, vol. 45, pp. 961-970, 1998.
WILLINGER, W., V. PAXSON, R. RIEDI, M. S. TAQQU, Long-range dependence and data network traffic, in Long-Range Dependence: Theory and Applications, Doukhan, P., Oppenheim, G., and Taqqu, M. S., Eds. Cambridge, MA: Birkhäuser, 2001.
WILLINGER, W., M. S. TAQQU, A. ERRAMILLI, A bibliographical guid to self-similar traffic and performanc modeling for modern high-speed networks, in Stochastic Networks: Theory and Applications, Kelly, F. P., Zachary, S., and Ziedins, I., Eds. Oxford, U. K.: Claredon Press, 1996, vol. 4, Royal Statistical Society, Lecture Note Series, pp. 339-366.
SHELUHIN, O. I., S. M. SMOLSKIY, A. V. OSIN, Self-Similar Processes in Telecommunications, Chichester, England, Wiley, 2007.
GAO, J. B., Y. CAO, J-M. LEE, Principal Component Analysis of 1/f? Noise, Physics Letters A, vol. 314(5-6), 2003, pp. 392-400.
LOWEN, S. B., M. C. TEICH, Fractal Renewal Processes Generate 1/f Noise, Physical Rev. E, vol. 47(2) 1993, pp. 992-1001.
LELAND, W. E., M. S. TAQQU, W. WILLINGER, D. V. WILSON, On the Self-similar Nature of Ethernet Traffic (extended version), IEEE/ACM Trans. Netw., vol. 2(1), 1994, pp. 1-15.
WILLINGER, W., M. S. TAQQU, R. SHERMAN, D. V. WILSON, Self-similarity through High-variability: Statistical Analysis of Ethernet LAN Traffic at the Source Level, IEEE/ACM Trans. Netw., vol. 5(1), 1997, pp. 71-86.
CINOTTI, M., E. D. MESE, S. GIORDANO, F. RUSSO, Long-range Dependence in Ethernet Traffic Offered to Interconnected DQDB MANs, in Proc. IEEE Int. Conf. Computer Science, Singapore, vol. 2, 1994, pp. 479-484.
KLIVANSKY, S. M., A. MUKHERJEE, C. SONG, On Long-range Dependence in NSFNET Traffic, Georgia Inst. Tech., Atlanta, Tech. Rep. GIT-CC-94-61, 1994.
ADAS, A., A. MUKHERJEE, On Resource Management and QoS Guarantees for Long Range Dependent Traffic, Georgia Inst. Tech., Atlanta, Tech. Rep. GIT-CC-94-60, 1994.
KLIVANSKY, S. M., A. MUKHERJEE, The NFSNET Simulation Platform, Georgia Inst. Tech., Atlanta, Tech. Rep. GIT-CC-95-007, 1995.
PAXSON, V., S. FLOYD, Wide-area Traffic: the Failure of Poisson Modeling, IEEE/ACM Trans. Netw. vol. 3(1), 1995 pp. 226-244.
FELDMANN, A., A. C. GILBERT, W. WILLINGER, T. G. KURTZ, The Changing Nature of Network Traffic: Scaling Phenomena, ACM SIGCOMM Computer Communication Rev., vol. 28(2), 1998, pp. 5-29.
CROVELLA, M. E., BESTAVROS, A., Explaining World Wide Web Traffic Self-similarity, Boston Univ. Boston, Tech. Rep., 1995, pp. 1995-015.
CROVELLA, M. E., M. S. TAQQU, A. BESTAVROS, Heavy-tailed Probability Distributions in the World Wide Web, in A Practical Guide to Heavy Tails: Statistical Techniques and Applications, Adler, R., Feldman, R., and Taqqu, M. S., Eds., Boston: Birkhäuser, 1998, pp. 3-25.
CROVELLA, M. E., A. BESTAVROS, Self-similarity in World Wide Web Traffic: Evidence and Possible Causes, IEEE/ACM Trans. Netw., vol. 5(6), 1997, pp. 835-846.
ARLITT, M., R. FRIEDRICH, T. JIN, Workload Characterization of a Web Proxy in a Cable Model Environments, Performance Evaluation Rev., vol. 27(2), 1999, pp. 25-36.
ARLITT, M., T. JIN, Workload Characterization of the 1998 World Cup Web Site, IEEE Network, vol. 14(3), 2000, pp. 30-37.
BORELLA, M., G. BREWSTER, Measurement and Analysis of Long-range Packet Dependent Behavior of Internet Packet Delays, Proc. IEEE INFOCOM ’98, San Francisco, 1998, pp. 497-504.
ZHONGHUA, M., Analysis of Wireless Data Network Traffic, M.S. thesis, School Eng. Sci., Simon Fraser Univ., Burnaby, Canada, 2000.
BASGEET, D. R., J. IRVINE, A. MUNRO, P. DUGENIE, D. KALESHI, O. LAZARO, Impact of mobility on aggregate traffic in mobile multimedia system, Proc. 5th Int. Symp. on Wireless Personal Multimedia Comm., Honolulu, vol. 2, 2002, pp. 333-337.
LIANG, Q., Ad hoc Wireless Network Traffic-self-similar and Forecasting, IEEE Commun. Lett., vol. 6(7), 2002, pp. 297-299.
JANEVSKI, T., Traffic Analysis and Design of Wireless IP Networks, Norwood, MA: Artech House, Inc., 2003, pp. 135-165.
RIDOUX, J., A. NUCCI, D. VEITCH, Seeing the Difference in IP Traffic: Wireless Versus Wireline, Proc. 25th IEEE Int. Conf. on Computer Comm., Barcelona, Spain, 2006, pp. 1-12.
FANTACCI, R., D. TARCHI, Bridging Solutions for a Heterogeneous WiMAX-WiFi Scenario, J. of Communications and Networks, vol. 8(4), 2006, pp. 369-377.
GIANVITTORIO, J. P., Y. RAHMAT-SAMIL, Fractal Antennas: a Novel Antenna Miniaturization Technique, and Applications, IEEE Antennas Propagat. Mag., vol. 44(1), 2002, pp. 20-36.
AHSON, S., M. ILYAS, WiMAX: Technologies, Performance Analysis and QoS, Boca Raton, FL: CRC Press, 2008, pp. 21-39.
KRAMER, G., Ethernet Passive Optical Networks, New York: McGraw-Hill, 2005.
HUANG, A., B. MUKHERJEE, L. XIE, Z. LI, Time-space Label Switching Protocol (TSL-SP), in High-Performance Packet Switching Architectures, Elhanany, I., and Hamdi, M., Eds., Germany: Springer, 2007, pp. 197-210.
MAIER, M., Optical Switching Networks, New York: Cambridge University Press, 2008.
DUFFY, D. A., A. A. MCINTOSH, M. ROSENSTEIN, W. WILLINGER, Statistical Analysis of CCSN/SS7 Traffic Data from Working CCS Subnetworks, IEEE J. Sel. Areas on Comm., vol. 12(3), 1994, pp. 544-551.
PRUTHI, P., A. ERRAMILLI, Heavy-tailed ON/OFF Source Behavior and Self-similar Traffic, in Proc. 1995 IEEE Int. Conf. Comm., Seattle, pp. 445-450.
ROSE, D., M. R. FRATER, A Comparison of Models for VBR Video Traffic Sources in B-ISDN, Inst. Comp. Sci., Univ. Würzburg, Rep. No. 72, 1993.
BERAN, J., SHERMAN, R., M. S. TAQQU, W. WILLINGER, Long-range Dependence in Variable-bit-rate Video Traffic, IEEE Trans. Comm., vol. 43(2/3/4), 1995, pp. 1566-1579.
GARRETT, M. W., W. WILLINGER, Analysis, Modeling and Generation of Self-similar VBR Video Traffic, ACM SIGCOMM Computer Comm. Rev., vol. 24(4), 1994, pp. 269-280.
TSYBAKOV, B., N. D. GEORGANAS, On Self-similar Traffic in ATM Queues: Definitions, Overflow Probability Bound and Cell Delay Distribution, IEEE/ACM Trans. on Networking, vol. 5(3), 1997, pp. 397-409.
YELLANKI, L., Impact of Short-range and Long-range Dependence on Variable Bit Rate Video Traffic Performance, in Proc. 9th Ann. Graduate Symp. on Computer Science, Dept. Comput. Sci., Univ. Saskatchewan, Saskatoon, Canada, 1997, pp. 1-12.
YELLANKI, L., Performance Evaluation of VBR Video Traffic Models, M.S. thesis, Dept. Comput. Sci., Univ. Saskatchewan, Saskatoon, SK, Canada, 1999.
TRAN-GIA, P., A Renewal Approximation for the Generalized Poisson Process, in Proc. Int. W-shop on Applied Math. and Performance/Reliability Models in Computer/Comm. Syst., Pisa, Italy, 1983, pp. 167-179.
HEFFES, H., M. D. LUCANTONI, A Markov Modulated Characterization of Packetized Voice and Data Traffic and Related Statistical Multiplexer Performance, IEEE J. Sel. Comm., vol. 4(6), 1986, pp. 856-868.
ROSSITER, M. H., The Switched Poisson Process and the SPP/G/1 Queue, Proc. ITC-12, Turin, Italy, 1988.
RYU, B. K., S. B. LOWEN, Point Process Approaches for Modeling and Analysis of Self-similar Traffic: Part I: Model construction, Proc. IEEE INFOCOM ’96, San Francisco, 1996, vol. 3, pp. 1468-1475.
RYU, B. K., S. B. LOWEN, Point Process Approaches for Modeling and Analysis of Self-similar Traffic: Part II: Applications, Int. Conf. Telecomm. Syst., Modeling and Analysis, Nashville, 1997.
YANG, X., Impulsive Self-similar Processes, with Applications in Broadband Communication System Modeling, Ph.D. diss., Dept. Elect. Comp. Eng., Drexel Univ., Philadelphia, 2001.
DING, M., W. YANG, Distribution of the First Return Time in Fractional Brownian Motion and Its Application to the Study of On-off Intermittency, Physical Rev. E, vol. 52(1), 1995, pp. 207-213.
MONDRAGÓN, R. J., J. M. PITTS, D. K. ARROWSMITH, The Chaotic Intermittency-sawtooth Map Model of Aggregate Self-similar Traffic Streams, Electronics Letters, vol. 36(2), 2000, pp. 184-186.
ARROWSMITH, D. K., M. BARENCO, R. J. MONDRAGÓN, M. WOOLF, The Statistics of Intermittency Maps and Dynamical Modeling of Networks, 6th Int. Symp. on Math. Theory of Networks and Systems, Leuven, Belgium, 2004.
MANDELBROT, B. B., W. VAN NESS, Fractional Brownian Motions, Fractional Noises and Applications, SIAM Rev., vol. 10(4), pp. 422-437, 1968.
PAXSON, V., Fast, Approximate Synthesis of Fractional Gaussian Noise for Generating Self-similar Network Traffic, Comm. Rev., vol. 27,(5) , 1997, pp. 5-18.
DAVIES, R. B., D. S. HARTE, Test for Hurst Effect, Biometrika, vol. 74(1), 1987, pp. 95-101.
MANDELBROT, B. B., A Fast Fractional Gaussian Noise Generator, Water Resources Research, vol. 7(3), 1971, pp. 543-553.
RITKE, R., X. HONG, M. GERLA, Contradictory Relationship between Hurst Parameter and Queueing Performance (extended version), Telecomm. Syst., vol. 16(1-2), 2001, pp. 159-175.
NEIDHARDT, A. L., J. L. WANG, The Concept of Relevant Time Scales and Its Application to Queueing Analysis of Self-similar Traffic (or is Hurst Naughty or Nice?), Performance Evaluation Rev., vol. 26(1), 1998, pp. 222-232.
GAO, J. B., I. RUBIN, Multifractal Modeling of Counting Processes of Long-range Dependent Network Traffic, Computer Comm., vol. 24(14), 2001, pp. 1400-1410.
GAO, J. B. I. RUBIN, Multifractal Analysis and Modeling of Long-range Dependent Network Traffic, Proc. 1999 IEEE Int. Conf. Comm., Vancouver, Canada, vol. 1, 1999, pp. 382-386.
WANG, X. J., Statistical Physics of Temporal Intermittency, Physical Rev. A, vol. 40(11), 1989, pp. 6647-6661.
SCHUSTER, H. G., W. JUST, Deterministic Chaos. An Introduction, 4th Ed., Federal Republic of Germany: Wiley-VHC, 2005, pp. 21-27.
SAMUEL, L. G., J. M. PITTS, R. J. MONDRAGÓN, Applications of Non-linear Dynamics to Network Modeling, 15th UK Teletraffic Symp. on Performance Eng. in Information Syst., Manchester, United Kingdom, 1998.
MORITA, S., Bifurcations in Globally Coupled Chaotic Maps, Physics Letters A, vol. 211(5), 1996, pp. 258-264.
KLAGES, R., Comment on “Analysis of Chaotic Motion and Its Shape Dependence in a Generalized Piecewise Linear Map”, Physics Rev. E, vol. 66, pt. 2, no. 1, 2002, pp. 018201.1.-018201.3.
AKLILU, G., J. M. PITTS, R. J. MONDRAGÓN, Modelling the Bounds on LRD behavior for IP Traffic. PGNet 2001 [Online]. http://ww.cms.livjm.ac.uk/ pgnet2001/papers/GAklilu.pdf.
SAMUEL, L. G., J. M. PITTS, R. J. MONDRAGÓN, Fast Self-similar Traffic Generation, Proc. 14th UK Teletraffic Symp. on Perf. Eng. in Information Syst., Manchester, United Kingdom, pp. 8/1-8/4.
MONDRAGÓN, R. J., A Model of Packet Traffic Using a Random Wall Model, Int. J. of Bifurcation and Chaos, vol. 9(7), 1999, pp. 1381-1392.
ROSE, O., Estimation of the Hurst Parameter of Long-range Dependent Time Series, Inst. Comput. Sci., Univ. Würzburg, Würzburg, Germany, Report No. 137, Feb. 1996.
GAO, J. B., Multiplicative Multifractal Modeling of Long-range Dependent (LRD) Traffic in Computer Communications Networks, Ph.D. diss., Dept. Elect. Eng., Univ. California, Los Angeles, 2000.
TAN, P. H., Statistical Analysis of Long-Range Dependent Processes via Stochastic Intensity Approach, with Applications in Networking, Ph.D. diss., Dept. Ind. Eng. Syst., North Carolina State Univ., Raleigh, 1999.
STALLINGS, W., Redes e Internet de Alta Velocidad. Rendimiento y Calidad de Servicio, 2nd Ed. Madrid, España: Pearson-Prentice Hall, 2004, p. 234.
MILLÁN, G., LEFRANC, H., Presentation of an Estimator for the Hurst Parameter for a Self-similar Process Representing the Traffic in IEEE 802.3 Networks, Int. J. of Computer, Comm. & Control, vol. IV, (2) , 2009, pp. 137-147.

References: V. 
 V. 
 V. 
 V. 
 V. 
 V.