Multifractal Analysis of a Class of Additive Processes with Correlated Non-Stationary Increments
Jacques Lévy Véhel (NRIA Rocquencourt, France)
Abstract
We consider a family of stochastic processes built from infinite sums of independent positive random functions on $R_+$. Each of these functions increases linearly between two consecutive negative jumps, with the jump points following a Poisson point process on $R_+$. The motivation for studying these processes stems from the fact that they constitute simplified models for TCP traffic on the Internet. Such processes bear some analogy with Lévy processes, but they are more complex in the sense that their increments are neither stationary nor independent. Nevertheless, we show that their multifractal behavior is very much the same as that of certain Lévy processes. More precisely, we compute the Hausdorff multifractal spectrum of our processes, and find that it shares the shape of the spectrum of a typical Lévy process. This result yields a theoretical basis to the empirical discovery of the multifractal nature of TCP traffic.
Full Text: Download PDF | View PDF online (requires PDF plugin)
Pages: 508-543
Publication Date: June 9, 2004
DOI: 10.1214/EJP.v9-208
References
- J.-M. Aubry, S. Jaffard. Random wavelet series. Comm. Math. Phys. 227 (2002), no. 3, 483--514. Math. Review 2003g:42054
- F. Baccelli and B. Thomas. Window Flow Control in FIFO Networks with Cross Traffic. Inria Tech. Rep. RR-3434 (1998). Math. Review number not available.
- F. Baccelli and D. Hong. TCP is Max-Plus Linear and what it tells us on its throughput. Inria Tech. Rep. RR-3986 (2000). Math. Review number not available.
- F. Baccelli and D. Hong. AIMD, Fairness and Fractal Scaling of TCP Traffic. INFOCOM (June 2002). Math. Review number not available.
- F. Baccelli and D. Hong. Interaction of TCP Flows as Billiards. Inria Tech. Rep. RR-4437 (2002). Math. Review number not available.
- J. Barral and J. L'evy V'ehel. Large deviation spectrum of a class of additive processes with correlated non-stationary increments. In preparation, (2003). Math. Review number not available.
- J. Barral and J. L'evy V'ehel. Multifractality of TCP explained. Inria Tech. Rep (2004). Math. Review number not available.
- J. Barral and B.B. Mandelbrot. Multifractal products of cylindrical pulses. Probab. Theory Related Fields 124 (2002), no. 3, 409--430. Math. Review 2004g:28005
- J. Bertoin. LÃvy processes. Cambridge Tracts in Mathematics 121. Cambridge University Press, Cambridge, 1996. x+265 pp. ISBN: 0-521-56243-0 Math. Review 98e:60117
- A. Chaintreau, F. Baccelli and C. Diot. Impact of Network Delay Variation on Multicast Session Performance With TCP-like Congestion Control. Inria Tech. Rep. RR-3987 (2000). Math. Review number not available.
- M. Crovella and A.Bestavros. Self-similarity in World Wide Web traffic: Evidence and possible causes. IEEE/ACM Trans. on Networking 5, no. 6 (1997) 835-846. Math. Review number not available.
- R.M. Blumenthal and R.K. Getoor. Sample functions of stochastic processes with stationary independent increments. J. Math. Mech. 10 (1961), 493--516. Math. Review 23 #A689
- T. D. Dang, S. Molnar and I. Maricza. Queuing Performance Estimation for General Multifractal Traffic. International Journal of Communication Systems 16 (2), (2003) 117-1363.
- R. Gaigalas and I. Kaj. Convergence of scaled renewal processes and a packet arrival model. Bernoulli 9 (2003), 671--703. Math. Review 2004d:60226
- C. Houdr'e and J. L'evy V'ehel.Large deviation multifractal spectra of certain stochastic processes. Preprint (2003). Math. Review number not available.
- P. Jacquet. Long term dependences and heavy tails in traffic and queues generated by memoryless ON/OFF sources in series. Inria Tech. Rep. RR-3516 (1998). Math. Review number not available.
- S. Jaffard. Old friends revisited: the multifractal nature of some classical functions. J. Fourier Anal. Appl. 3 (1997), 1--22. Math. Review 98b:28013
- S. Jaffard. The multifractal nature of LÃvy processes. Probab. Theory Related Fields 114 (1999), 207--227. Math. Review 2000g:60079
- S. Jaffard. On lacunary wavelet series. Ann. Appl. Probab. 10(2000), 313--329. Math. Review 2001f:60040
- J.-P.Kahane. Produits de poids alÃatoires indÃpendants et applications. (French) [Products of independent random weights, and applications.] Fractal geometry and analysis (Montreal, PQ, 1989), 277--324, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 346, Kluwer Acad. Publ., Dordrecht, 1991. Math. Review MR1140725
- M. Ledoux and M. Talagrand. Probability in Banach spaces. Isoperimetry and processes. Ergebnisse der Mathematik undihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], 23. Springer-Verlag, Berlin, 1991. xii+480 pp. ISBN: 3-540-52013-9 Math. Review 93c:60001
- W. E. Leland, M. S. Taqqu, W. Willinger and D. V. Wilson. On the self-similar nature of Ethernet traffic (Extended Version). IEEE/ACM Trans. on Networking 2 (1994) pp. 1-15. Math. Review number not available.
- J. L'evy~V'ehel and R. Riedi. Fractional Brownian motion and data traffic modeling: The other end of the spectrum. Fractals in Engineering J. L'evy V'ehel, E. Lutton and C. Tricot, Eds., Springer Verlag, 1997. Math. Review number not available.
- J. L'evy~V'ehel and B. Sikdar. A Multiplicative Multifractal Model for TCP Traffic. Proceedings of IEEE ISCC (2001), 714-719. Math. Review number not available.
- B.B. Mandelbrot. Intermittent turbulence in self-similar cascades: divergence of hight moments and dimension of the carrier. J. fluid. Mech. 62 (1974), 331--358. Math. Review number not available.
- B.B. Mandelbrot. A class of multinomial multifractal measures with negative (latent) values for the ``dimension'' $f(alpha)$. Fractals' Physical Origins and Properties. Proceedings of the Erice Meeting, 1988. L. Pietronero, Ed., Plenum Press, New York, 1989, pp 3--29. Math. Review number not available.
- V. Paxson and S. Floyd. Wide area traffic: The failure of Poisson modeling. IEEE/ACM Trans. on Networking 3 (1995), 226-244. Math. Review number not available.
- V. Pipiras, M.S. Taqqu and J.B. Levy. Slow, fast and arbitrary growth conditions for renewal reward processes when the renewals and the rewards are heavy tailed. Boston University Preprint (2002).
- R. H. Riedi and J. L'evy-V'ehel. TCP Traffic is multifractal: A numerical study. Inria Tech. Rep. RR-3129 (2000). Math. Review number not available.
- L. A.Shepp, L. A. Covering the line with random intervals. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 23 (1972), 163--170. Math. Review 48 #1284
- W. R. Stevens. TCP/IP illustrated volume 1. Addison Wesley, 1994. Math. Review number not available.
- W.F. Stout. Almost sure convergence. Probability and Mathematical Statistics, Vol. 24. Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1974. x+381 pp. Math. Review 56 #13334
This work is licensed under a Creative Commons Attribution 3.0 License.