On the propagation of long-range dependence in the Internet

ABSTRACT

This paper analyzes how TCP congestion control can propagate self-similarity between distant areas of the Internet. This property of TCP is due to its congestion control algorithm, which adapts to self-similar fluctuations on several timescales. The mechanisms and limitations of this propagation are investigated, and it is demonstrated that if a TCP connection shares a bottleneck link with a self-similar background traffic flow, it propagates the correlation structure of the background traffic flow above a characteristic timescale. The cut-off timescale depends on the end-to-end path properties, e.g., round-trip time and average window size. It is also demonstrated that even short TCP connections can propagate long-range correlations effectively. Our analysis reveals that if congestion periods in a connection's hops are long-range dependent, then the end-user perceived end-to-end traffic is also long-range dependent and it is characterized by the largest Hurst exponent. Furthermore, it is shown that self-similarity of one TCP stream can be passed on to other TCP streams that it is multiplexed with. These mechanisms complement the widespread scaling phenomena reported in a number of recent papers. Our arguments are supported with a combination of analytic techniques, simulations and statistical analyses of real Internet traffic measurements.

REFERENCES

• 1: P. Abry and D. Veitch. Wavelet analysis of long-range-dependent traffic. IEEE/ACM Transactions on Networking, 44(1):2-15, 1998.
• 2: J. Beran, R. Sherman, M. S. Taqqu, and W. Willinger. Long-range dependence in variable-bit-rate video traffi. IEEE Transactions on Communications, 43(2/3/4):1566-1579, Febuary/March/April 1995.
• 3: F. Brichet, J. Roberts, A. Simonian, and D. Veitch. Heavy traffic analysis of a storage model with long range dependent on/o sources. Queuing Systems, 23:197-215, 1996.
• 4: 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]
• 5: Mark E. Crovella , Murad S. Taqqu , Azer Bestavros, Heavy-tailed probability distributions in the World Wide Web, A practical guide to heavy tails: statistical techniques and applications, Birkhauser Boston Inc., Cambridge, MA, 1998
• 6: 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]
• 7: 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
• 8: A. Feldmann , A. C. Gilbert , W. Willinger, Data networks as cascades: investigating the multifractal nature of Internet WAN traffic, ACM SIGCOMM Computer Communication Review, v.28 n.4, p.42-55, Oct. 1998
• 9: Mark W. Garrett , Walter Willinger, Analysis, modeling and generation of self-similar VBR video traffic, Proceedings of the conference on Communications architectures, protocols and applications, p.269-280, August 31-September 02, 1994, London, United Kingdom
• 10: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 11: Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic, Conference proceedings on Communications architectures, protocols and applications, p.183-193, September 13-17, 1993, San Francisco, California, United States
• 12: 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]
• 13: Matthew Mathis , Jeffrey Semke , Jamshid Mahdavi, The macroscopic behavior of the TCP congestion avoidance algorithm, ACM SIGCOMM Computer Communication Review, v.27 n.3, p.67-82, July 1997 [doi>10.1145/263932.264023]
• 14: S. Molnar, T. D. Dang, and A. Vid acs. Heavy tailedness, long-range dependence and self-similarity in data traffic. In Proc. 7th International Conference on Telecommunication Systems Modeling and Analysis, Nashville, Tennessee, USA, March 1999.
• 15: S. Molnar and A. Vid acs. On modeling and shaping self-similar ATM traffic. In Proc. 15th Int. Teletraffic Congress, Washington D.C., 1997.
• 16: I. Norros. A storage model with self-similar input. Queuing Systems, 16:387-396, 1994.
• 17: 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
• 18: K. Park, G. Kim,andM.Crovella. On the effect of traffic self-similarity onnetwork performance. In In Proceedings of the SPIE International Conference on Performance and Control of Network Systems, pages 296-310, November 1997.
• 19: 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]
• 20: M. S. Taqqu, V. Teverovsky, and W. Willinger. Estimators for long-range dependence: an empirical study. Fractals, 3(4):785-788, 1995.
• 21: 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]
• 22: Boris Tsybakov , Nicoals D. Georganas, On self-similar traffic in ATM queues: definitions, overflow probability bound, and cell delay distribution, IEEE/ACM Transactions on Networking (TON), v.5 n.3, p.397-409, June 1997 [doi>10.1109/90.611104]
• 23: A. Veres and M. Boda. The chaotic nature of TCP congestion control. In Proc. IEEE INFOCOM, Tel Aviv, Israel, April 2000.
• 24: 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]
• 25: W. Willinger, M. S. Taqqu, and A. Erramilli. A bibliographical guide to self-similar traffic and performance modeling for modern high-speed networks, In Stochastic networks: Theory and applications, Ed:F. P. Kelly, S. Zachary and I. Ziedins. Clarendon Press, Oxford, 1996.

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
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

          Nouns: TCP/IP

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Control theory

General Terms:
Design, Management, Measurement, Performance, Standardization, Theory

Keywords:
TCP adaptivity, TCP congestion control, long-range dependence, self-similarity