Lévy flights and fractal modeling of internet traffic

ABSTRACT

The relation between burstiness and self-similarity of network traffic was identified in numerous papers in the past decade. These papers suggested that the widely used Poisson based models were not suitable for modeling bursty, local-area and wide-area network traffic. Poisson models were abandoned as unrealistic and simplistic characterizations of network traffic. Recent papers have challenged the accuracy of these results in today's networks. Authors of these papers believe that it is time to reexamine the Poisson traffic assumption. The explanation is that as the amount of Internet traffic grows dramatically, any irregularity of the network traffic, such as burstiness, might cancel out because of the huge number of different multiplexed flows. Some of these results are based on analyses of particular OC48 Internet backbone connections and other historical traffic traces. We analyzed the same traffic traces and applied new methods to characterize them in terms of packet interarrival times and packet lengths. The major contribution of the paper is the application of two new analytical methods. We apply the theory of smoothly truncated Levy flights and the linear fractal model in examining the variability of Internet traffic from self-similar to Poisson. The paper demonstrates that the series of interarrival times is still close to a self-similar process, but the burstiness of the packet lengths decreases significantly compared to earlier traces.

REFERENCES

• 1: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
• 2: 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]
• 3: A. Feldmann , A. C. Gilbert , W. Willinger, Data networks as cascades: investigating the multifractal nature of Internet WAN traffic, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.42-55, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 4: Anja Feldmann , Anna C. Gilbert , Polly Huang , Walter Willinger, Dynamics of IP traffic: a study of the role of variability and the impact of control, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.301-313, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 5: Wei-Bo Gong , Yong Liu , Vishal Misra , Don Towsley, Self-similarity and long range dependence on the internet: a second look at the evidence, origins and implications, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.48 n.3, p.377-399, 21 June 2005 [doi>10.1016/j.comnet.2004.11.026]
• 6: T. Gyires, "Simulation of the harmful consequences of self-similar network traffic," J. Comput. Inf. Syst., pp. 94-111, Summer, 2002.
• 7: Guanghui He , Yuan Gao , Jennifer C. Hou , Kihong Park, A case for exploiting self-similarity of network traffic in TCP congestion control, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.45 n.6, p.743-766, 21 August 2004 [doi>10.1016/j.comnet.2003.12.019]
• 8: Guanghui He , Jennifer C. Hou, On sampling self-similar internet traffic, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.16, p.2919-2936, 14 November 2006 [doi>10.1016/j.commet.2005.11.009]
• 9: Nicolas Hohn , Darryl Veitch , Patrice Abry, Does fractal scaling at the IP level depend on TCP flow arrival processes?, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637208]
• 10: N. Hohn, D. Veitch, and P. Abry, "Cluster processes: a natural language for network traffic," IEEE Trans. Signal Process., vol. 51, no. 8, pp. 2229-2244, Aug. 2003.
• 11: P. Hougaard, "Survival models for heterogeneous populations derived from stable distributions," Biometrika, vol. 73, no. 2, pp. 387-396, 1986.
• 12: E. Iglói and G. Terdik, "Superposition of diffusions with linear generator and its multifractal limit process," ESAIM Probab. Stat., vol. 7, pp. 23-88, 2003, (electronic).
• 13: Hao Jiang , Constantinos Dovrolis, Source-level IP packet bursts: causes and effects, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948245]
• 14: Hao Jiang , Constantinos Dovrolis, Why is the internet traffic bursty in short time scales?, ACM SIGMETRICS Performance Evaluation Review, v.33 n.1, June 2005
• 15: T. Karagiannis, M. Molle, M. Faloutsos, and A. Broido, "A nonstationary Poisson view of Internet traffic," in Proc. IEEE INFOCOM 2004, Hong Kong, Mar. 2004, vol. 3, pp. 1558-1569.
• 16: S. Karlin and H. M. Taylor, A First Course in Stochastic Processes, 2nd ed. New York, London: Academic, 1975.
• 17: M. G. Kendall , A. Stuart , J. K. Ord, Kendall's advanced theory of statistics, Oxford University Press, Inc., New York, NY, 1987
• 18: I. Koponen, "Analytic approach to the problem of convergence of truncated Lévy flights towards the Gaussian stochastic process," Phys. Rev. E., vol. 52, pp. 1197-1199, 1995.
• 19: 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]
• 20: W. E. Leland, M. S. Taqqu, W. Willinger, and D. V. Wilson, "Statistical analysis and stochastic modeling of self-similar data traffic," in The Fundamental Role of Teletraffic in the Evolution of Telecommunications Networks, Proceedings of the 14th International Teletraffic Congress (ITC '94), J. Labetoulle and J. W. Roberts, Eds. Amsterdam: Elsevier Science B.V., 1994, pp. 319-328.
• 21: W. E. Leland and D. W. Wilson, "High time-resolution measurement and analysis of LAN traffic: Implications for LAN interconnection," in Proc. IEEE INFOCOM'91, Bal Harbour, FL, 1991, pp. 1360-1366.
• 22: R. N. Mantegna and H. E. Stanley, "Stochastic processes with ultraslow convergence to a Gaussian: The truncated Lévy flight," Phys. Rev. Lett., vol. 73, pp. 2946-2949, 1994.
• 23: Sandor Molar Molnár , Gyorgy Terdik, A General Fractal Model of Internet Traffic, Proceedings of the 26th Annual IEEE Conference on Local Computer Networks, p.492, November 14-16, 2001
• 24: Kihong Park , Gitae Kim , Mark Crovella, On the relationship between file sizes, transport protocols, and self-similar network traffic, Proceedings of the 1996 International Conference on Network Protocols (ICNP '96), p.171, October 29-November 01, 1996
• 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: J. Rosinski, "Tempering stable processes," Stochast. Process. Applicat., vol. 117, pp. 677-707, 2007.
• 27: G. Samorodnitski and M. S. Taqqu, Stable Non-Gaussian Random Processes. Stochastic Models With Infinite Variance. New York, London: Chapman and Hall, 1994.
• 28: Shriram Sarvotham , Rudolf Riedi , Richard Baraniuk, Connection-level analysis and modeling of network traffic, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505215]
• 29: K. Sato, Lévy Processes and Infinitely Divisible Distributions. Cambridge, U.K.: Cambridge Univ. Press, 1999, vol. 68, Cambridge Studies in Advanced Mathematics, translated from the 1990 Japanese original, revised by the author.
• 30: Y. G. Sinai, "Self-similar probability distributions," Theor. Probab. Appl., vol. 21, pp. 64-84, 1976.
• 31: K. Sriram and W. Whitt, "Characterizing superposition arrival processes in packet multiplexers for voice and data," IEEE J. Sel. Areas Commun., vol. 4, no. 6, pp. 833-846, Sep. 1986.
• 32: M. S. Taqqu, V. Teverovsky, and W. Willinger, "Is network traffic self-similar or multifractal?," Fractals, vol. 5, no. 1, pp. 63-73, 1997.
• 33: G. Terdik, Bilinear Stochastic Models and Related Problems of Non-linear Time Series Analysis; A Frequency Domain Approach. New York: Springer Verlag, 1999, vol. 142, Lecture Notes in Statistics.
• 34: G. Terdik and W. A. Woyczynski, "Rosiñski measures for tempered stable and related Ornstein-Uhlenbeck processes," Probab. Math. Statist., vol. 26, no. 2, pp. 213-243, 2006.
• 35: G. Terdik, W. A. Woyczynski, and A. Piryatinska, "Fractional-and integer-order moments, and multiscaling for smoothly truncated Lévy flights," Phys. Lett. A, vol. 348, pp. 94-109, 2006.
• 36: G. Xiaohu, Z. Guangxi, and Z. Yaoting, "On the testing for alpha-stable distributions of network traffic," Comput. Commun., vol. 27, no. 5, pp. 447-457, Mar. 2004.
• 37: C. Shannon, E. Aben, K. Claffy, D. Andersen, and N. Brownlee, The CAIDA OC48 Traces Dataset. Cooperative Association for Internet Data Analysis (CAIDA), Univ. California San Diego Supercomputer Ctr., La Jolla, CA, Jun. 6, 2008 [Online]. Available: http://www.caida. org/data/passive
• 38: E. Iglói, "Self-similarity and dilative stability," Univ. Debrecen, Hungary, 2005 [Online]. Available: http://www.inf.unideb.hu/valseg/dol-gozok/igloi/2005dilative_stable.pdf

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Linear approximation; Wavelets and fractals
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Theory

Keywords:
Lévy flights, burstiness, fractal modelling, long-range dependence, network traffic