Ginno MILLAN
Departamento de Ingeniería Eléctrica, Universidad de Santiago de Chile
Av. Ecuador 3519, Estación Central, Santiago, Chile

Héctor KASCHEL
Departamento de Ingeniería Eléctrica, Universidad de Santiago de Chile
Av. Ecuador 3519, Estación Central, Santiago, Chile

Gastón LEFRANC
Escuela de Ingeniería Eléctrica, Pontificia Universidad Católica de Valparaíso
Av. Brasil 2147, Valparaíso, Chile

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.

>>Full text
CITE THIS PAPER AS:
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.

1. Introduction

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 [1], invades and establishes the omnipresence of unpredictability as a fundamental trait of common experience [2]. 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 [3]. 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) [4].

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 [5]. 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 [6]. A direct result of the above is that very simple systems, even with only one degree of freedom, such as those reported in [7] and [8], can give rise to surprisingly complex behaviors.

The notion of chaos often appears linked to the notion of fractal introduced by Mandelbrot [9], 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 [4], [10]. 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 [11]; 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 [12]-[21]. 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 [22]-[35], transmission technologies [36]-[46], control and signaling protocols [47], [48], and applications, particularly in video [49]-[54].

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) [55], Markov Modulated Poisson Processes (MMPP) [56], Switched Poisson Processes (SPP) [57], Fractal Point Processes (FPP) [58], [59], Alternating Fractal Renewal Processes (AFRP) and their Extended Alternating Fractal Renewal Process (EAFRP) variant [23], [60], those based on intermittent chaotic maps [3], [4], [61]-[63], and the traditional processes of fractional Gaussian noise (fGn) and fractional Brownian motion (fBm) [64]-[67].

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, [68]-[71] 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.

REFERENCES

1. KELLERT, S. H., In the Wake of Chaos. Chicago, IL: The University of Chicago Press, 1993, p. 2.
2. MALE, S., Finding a Horseshoe on the Beaches of Rio, The Mathematical Intelligencer, vol. 20(1), pp. 39-44, 1998.
3. 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.
4. 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.
5. MAHNER, M., M. BUNGE, Fundamentos de Biofilosofía, México, Ed. Siglo Veintiuno, 2000, pp. 220-221.
6. LUENGO, D., Estimación de secuencias caóticas con aplicación en comunicaciones, Ph.D. diss., Dept. Ing. Com., Univ. Cantabria, España, 2006.
7. MAY, R. M., Biological Populations with Nonoverlapping Generations: Stable Points, Stable Cycles and Chaos, Science, vol. 186 (4164), Nov. 1974, pp. 645-647.
8. MAY, R. M., Simple Mathematical Models with Very Complicated Dynamic, Nature, vol. 261(5560), Jun. 1976, pp. 459-467.
9. MANDELBROT, B. B., Les Objets Fractals: Forme, Hasard et Dimension, Paris, France: Flammarion, 1975.
10. 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/.
11. MANDELBROT, B. B., The Fractal Geometry of Nature, New York: W. H. Freeman and Company, 1983.
12. FLOYD, S., V. PAXSON, Difficulties in Simulating the Internet, IEEE/ACM Trans. Netw., vol. 9, Aug. 2001, pp. 392-403.
13. PARK, K., W. WILLINGER, Self-Similar Network Traffic and Performance Evaluation. New York: Wiley, 2000.
14. RESNICK, S. I., Heavy Tail Modeling and Teletraffic Data, Annals Statist., vol. 25, 1997, pp. 1805-1869.
15. 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.
16. WILLINGER, W., V. PAXSON, Where Mathematics Meets the Internet, Notices of the AMS, vol. 45, pp. 961-970, 1998.
17. 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.