Data networks as cascades: investigating the multifractal nature of Internet WAN traffic

ABSTRACT

In apparent contrast to the well-documented self-similar (i.e., monofractal) scaling behavior of measured LAN traffic, recent studies have suggested that measured TCP/IP and ATM WAN traffic exhibits more complex scaling behavior, consistent with multifractals. To bring multifractals into the realm of networking, this paper provides a simple construction based on cascades (also known as multiplicative processes) that is motivated by the protocol hierarchy of IP data networks. The cascade framework allows for a plausible physical explanation of the observed multifractal scaling behavior of data traffic and suggests that the underlying multiplicative structure is a traffic invariant for WAN traffic that co-exists with self-similarity. In particular, cascades allow us to refine the previously observed self-similar nature of data traffic to account for local irregularities in WAN traffic that are typically associated with networking mechanisms operating on small time scales, such as TCP flow control.To validate our approach, we show that recent measurements of Internet WAN traffic from both an ISP and a corporate environment are consistent with the proposed cascade paradigm and hence with multifractality. We rely on wavelet-based time-scale analysis techniques to visualize and to infer the scaling behavior of the traces, both globally and locally. We also discuss and illustrate with some examples how this cascade-based approach to describing data network traffic suggests novel ways for dealing with networking problems and helps in building intuition and physical understanding about the possible implications of multifractality on issues related to network performance analysis.

REFERENCES

• 1: P. Abry and D. Veitch. Wavelet analysis of long-range dependent traffic. IEEE Transactions on Information Theory 44, pp. 2-15, 1998.
• 2: A. Arneodo, Wavelet analysis of fractals: from the mathematical concepts to experimental reality, Wavelets: theory and applications, Oxford University Press, Inc., New York, NY, 1996
• 3: Andrew Bruce , H. Y. Gao, Applied Wavelet Analysis with S-Plus, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 4: K. C. Claffy, H.-W. Braun, and G. C. Polyzos. A parameterizable methodology for internet traffic flow profiling IEEE Journal on Selected Areas in Communications, vol. 13, pp. 1481-1494, 1995.
• 5: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.160-169, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• 6: Ingrid Daubechies, Ten lectures on wavelets, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 7: Ashok Erramilli , Onuttom Narayan , Walter Willinger, Experimental queueing analysis with long-range dependent packet traffic, IEEE/ACM Transactions on Networking (TON), v.4 n.2, p.209-223, April 1996 [doi>10.1109/90.491008]
• 8: C. J. G. Evertsz and B. B. Mandelbrot. Multifractal measures. In H.-O. Peitgen, H. Jurgens and D. Saupe, editors, Chaos and Fractals: New Frontiers in Science, Springer- Verlag, New York, 1092.
• 9: A. Feldmann , A. C. Gilbert , W. Willinger , T. G. Kurtz, The changing nature of network traffic: scaling phenomena, ACM SIGCOMM Computer Communication Review, v.28 n.2, p.5-29, Apr. 1998 [doi>10.1145/279345.279346]
• 10: A. Feldmann, J. Rexford and R. Caceres. Reducing Overhead in Flow-Switched Networks: An Empirical Study of Web Traffic. Proc. of IEEE INFOCOM'98, 1998 (to appear).
• 11: A. C. Gilbert, W. Willinger and A. Feldmann. Scaling analysis of random cascades in network traffic. Preprint. 1998
• 12: M. Grossglauser , J.-C. Bolot, On the relevance of long-range dependence in network traffic, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.15-24, August 28-30, 1996, Palo Alto, California, United States
• 13: V. K. Gupta and E. C. Waymire. A statistical analysis of mesoscale rainfall as a random cascade. Journal of Applied Meteorology 32, pp. 251-267, 1993.
• 14: R. Holley and E. C. Waymire. Multifractal dimensions and scaling exponents for strongly bounded random cascades. Annals of Applied Probability 2, pp. 819-845, 1992.
• 15: Gerald Kaiser, A friendly guide to wavelets, Birkhauser Boston Inc., Cambridge, MA, 1994
• 16: T. G. Kurtz. Limit theorems for workload input models. In F. P. Kelly, S. Zachary, and I. Ziedins, editors, Stochastic Networks: Theory and Applications. Clarendon Press, Oxford, 1996.
• 17: Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.1-15, Feb. 1994 [doi>10.1109/90.282603]
• 18: J. Levy-Vehel and R. Riedi. Fractional Brownian motion and data traffic modeling: The other end of the spectrum. In FractaIs in Engineering, Springer-Verlag, Berlin, pp. 185- 202, 1997.
• 19: P. Mannersalo and I. Norros. Multifractal analysis of real ATM traffic: A first look. COST257TD, VTT Information Technology, 1997.
• 20: S. McCanne and S. Floyd. NS: Network Simulator. http://www-mash, cs. berkeley, edu/ns/.
• 21: Y. Meyer and R. Coifman. Wavelets: Calderdn-Zygmund and muItitinear operators, Cambridge University Press, New York, pp. 52-54, 1997.
• 22: E. W. Montroll and M. F. Shlesinger. On 1/f noise and other distributions with long tails. Proc. Natl. Acad. Sci. USA 79, pp. 3380-3383, 1982.
• 23: Vern Paxson, End-to-end routing behavior in the Internet, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.25-38, August 28-30, 1996, Palo Alto, California, United States
• 24: Vern Paxson, End-to-end Internet packet dynamics, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.139-152, September 14-18, 1997, Cannes, France
• 25: Vern Paxson , Sally Floyd, Wide area traffic: the failure of Poisson modeling, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.226-244, June 1995 [doi>10.1109/90.392383]
• 26: R. H. Riedi and J. Levy-Vehel. TCP traffic is multifractal: A numerical study. Preprint, 1997.
• 27: Bong K. Ryu , Anwar Elwalid, The importance of long-range dependence of VBR video traffic in ATM traffic engineering: myths and realities, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.3-14, August 28-30, 1996, Palo Alto, California, United States
• 28: M. S. Taqqu, V. Teverovsky and W. Willinger. Is network traffic self-similar or multifractal? Fractats 5, pp. 63-73, 1997.
• 29: A. H. Tewfik and M. Kim. Correlation structure of the discrete wavelet coefficients of fractional Brownian motion. IEEE Trans. or~ In}o. Theory, vo}. 38, 2, pp. 904-909, 1992.
• 30: Walter Willinger , Vern Paxson , Murad S. Taqqu, Self-similarity and heavy tails: structural modeling of network traffic, A practical guide to heavy tails: statistical techniques and applications, Birkhauser Boston Inc., Cambridge, MA, 1998
• 31: Walter Willinger , Murad S. Taqqu , Robert Sherman , Daniel V. Wilson, Self-similarity through high-variability: statistical analysis of Ethernet LAN traffic at the source level, IEEE/ACM Transactions on Networking (TON), v.5 n.1, p.71-86, Feb. 1997 [doi>10.1109/90.554723]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

Additional Classification:
  C. Computer Systems Organization