Evidence for long-tailed distributions in the internet

ABSTRACT

We review evidence that Internet traffic is characterized by long-tailed distributions of interarrival times, transfer times, burst sizes, and burst lengths. We propose a new statistical technique for identifying long-tailed distributions, and apply it to a variety of datasets collected on the Internet. We find that there is little evidence that interarrival times and transfer times are long-tailed, but that there is some evidence for long-tailed burst sizes. We speculate on the causes of long-tailed bursts.

REFERENCES

• 1: Kihong Park and Walter Willinger, "Self-similar network traffic: An overview," in Self-Similar Network Traffic and Performance Com- Evaluation, chapter 1. Wiley-Interscience, 2000, Preprint.
• 2: 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]
• 3: M. Parulekar and A. M. Makowski, "M/G/co input process: a versatile class of models for network traffic," Tech. Rep. T.R. 96-59, Institute for Systems Research, 1996.
• 4: 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, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.100-113, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 5: 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
• 6: Kihong Park , Gitae Kim , Mark Crovella, On the relationship between file sizes, transport protocols, and self-similar network traffic, Boston University, Boston, MA, 1996
• 7: Mark E. Crovella, Murad S. Taqqu, and Azer Bestavros, "Heavytailed probability distributions in the World Wide Web," in A Practical Guide To Heavy Tails, pp. 3326. Chapman & Hall, 1998.
• 8: Allen B. Downey, The Structural Cause of File Size Distributions, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.361, August 15-18, 2001
• 9: Martin F. Arlitt , Carey L. Williamson, Web server workload characterization: the search for invariants, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.126-137, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• 10: Paul Barford , Mark Crovella, Generating representative Web workloads for network and server performance evaluation, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.151-160, June 22-26, 1998, Madison, Wisconsin, United States
• 11: 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]
• 12: Jon M. Peha, "Retransmission mechanisms and self-similar traffic models," in IEEE/ACM/SCS Communication Networks and Distributed Systems Modeling and Simulation Conference, January 1997, pp. 47-52.
• 13: Andras Veres and Miklos Boda, "The chaotic nature of TCP congestion control," in IEEE INFOCOM'00, March 2000.
• 14: Wu-chun Feng , Peerapol Tinnakornsrisuphap, The Adverse Impact of the TCP Congestion-Control Mechanism in Heterogeneous Computing Systems, Proceedings of the Proceedings of the 2000 International Conference on Parallel Processing, p.299, August 21-24, 2000
• 15: Liang Guo, Mark Crovella, and Ibrahim Matta, "TCP congestion control and heavy tails," in IEEE INFOCOMM'01, 2001.
• 16: Mark E. Crovella , Murad S. Taqqu, Estimating the heavy tail index from scaling properties, Methodology and Computing in Applied Probability, v.1 n.1, p.55-79, July 1999 [doi>10.1023/A:1010012224103]
• 17: Anja Feldmann , Ward Whitt, Fitting Mixtures of Exponentials to Long-Tail Distributions to Analyze Network Performance Models, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1096, April 09-11, 1997
• 18: Jean M. Carlson and John Doyle, "Highly optimized tolerance: a mechanism for power laws in designed systems," Physics Review E, vol. 60, no. 2, August 1999.
• 19: Xiaoyun Zhu, Jie Yu, and John Doyle, "Heavy tails, generalized coding, and optimal web layout," in IEEE INFOCOM'01, April 2001.
• 20: Murad S. Taqqu , Walter Willinger , Robert Sherman, Proof of a fundamental result in self-similar traffic modeling, ACM SIGCOMM Computer Communication Review, v.27 n.2, p.5-23, Apr. 1997 [doi>10.1145/263876.263879]
• 21: Anja Feldmann, "Characteristics of TCP connection arrivals," Tech. Rep., AT&T Labs-Research, 1998.
• 22: Norman Johnson, Samuel Kotz, and N. Balakrishnan, Continuous univariate distributions, Vol. 1 & 2, John Wiley and Sons, New York, 1994.
• 23: Mark Crovella , Azer Bestavros, Explaining World Wide Web Traffic Self-Similarity, Boston University, Boston, MA, 1995
• 24: Shuang Deng, "Empirical model of WWW document arivals at access links," in IEEE International Conference on Communication, June 1996.
• 25: 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
• 26: Vern Paxson, Empirically derived analytic models of wide-area TCP connections, IEEE/ACM Transactions on Networking (TON), v.2 n.4, p.316-336, Aug. 1994 [doi>10.1109/90.330413]
• 27: Joachim Charzinksi, HTTP/TCP connection and flow characteristics, Performance Evaluation, v.42 n.2-3, p.149-162, Oct. 2000 [doi>10.1016/S0166-5316(00)00028-6]

INDEX TERMS

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

          Nouns: Internet

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

General Terms:
Performance