On estimating end-to-end network path properties

ABSTRACT

The more information about current network conditions available to a transport protocol, the more efficiently it can use the network to transfer its data. In networks such as the Internet, the transport protocol must often form its own estimates of network properties based on measurements performed by the connection endpoints. We consider two basic transport estimation problems: determining the setting of the retransmission timer (RTO) for a reliable protocol, and estimating the bandwidth available to a connection as it begins. We look at both of these problems in the context of TCP, using a large TCP measurement set [Pax97b] for trace-driven simulations. For RTO estimation, we evaluate a number of different algorithms, finding that the performance of the estimators is dominated by their minimum values, and to a lesser extent, the timer granularity, while being virtually unaffected by how often round-trip time measurements are made or the settings of the parameters in the exponentially-weighted moving average estimators commonly used. For bandwidth estimation, we explore techniques previously sketched in the literature [Hoe96, AD98] and find that in practice they perform less well than anticipated. We then develop a receiver-side algorithm that performs significantly better.

REFERENCES

• AD98: Mohit Aron and Peter Druschel. TCP: Improving Startup Dynamics by Adaptive Timers and Congestion Control. Technical Report TR98-318, Rice University Computer Science, 1998.
• AFP98: Mark Allman, Sally Floyd, and Craig Partridge. Increasing TCP's Initial Window, September 1998. RFC 2414.
• APS99: Mark Allman, Vern Paxson, and W. Richard Stevens. TCP Congestion Control, April 1999. RFC 2581.
• BCC+98: Robert Braden, David Clark, Jon Crowcroft, Bruce Davie, Steve Deering, Deborah Estrin, Sally Floyd, Van Jacobson, Greg Minshall, Craig Partridge, Larry Peterson, K. Ramakrishnan, S. Shenker, J. Wroclawski, and Lixia Zhang. Recommendations on Queue Management and Congestion Avoidance in the Intemet, April 1998. RFC 2309.
• Bra89: Robert Braden. Requirements for Internet Hosts- Communication Layers, October 1989. RFC 1122.
• DDK+90: Wi!libald Doeringer, Doug Dykeman, Matthias Kaiserswerth, Bernd Werner Meister, Harry Rudin, and Robin Williamson. A Survey of Light-Weight Transport Protocols for High-Speed Networks. IEEE Transactions on Communications, 38(11):2025-2039, November 1990.
• FF96: Kevin Fall , Sally Floyd, Simulation-based comparisons of Tahoe, Reno and SACK TCP, ACM SIGCOMM Computer Communication Review, v.26 n.3, p.5-21, July 1996 [doi>10.1145/235160.235162]
• FH99: Sally Floyd and Tom Henderson. The NewReno Modification to TCP's Fast Recovery Algorithm, April 1999. RFC 2582.
• FJ93: Sally Floyd , Van Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.397-413, Aug. 1993 [doi>10.1109/90.251892]
• Hoe96: Janey C. Hoe, Improving the start-up behavior of a congestion control scheme for TCP, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.270-280, August 28-30, 1996, Palo Alto, California, United States
• Jac88: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• Jac90: Van Jacobson. Modified TCP Congestion Avoidance Algorithm, April 1990. Email to the end2end-interest mailing list. URL: ftp://ftp.ee, lbl.gov/email/ vanj.90apr30, txt.
• JBB92: Van Jacobson, Robert Braden, and David Borman. TCP Extensions for High Performance, May 1992. RFC 1323.
• JK92: Van Jacobson and Michael Karels. Congestion Avoidance and Control, 1992. ftp://ftp.ee.lbl.gov/papers/congavoid.ps.Z.
• Kes91: Srinivasan Keshav, A control-theoretic approach to flow control, Proceedings of the conference on Communications architecture & protocols, p.3-15, September 03-06, 1991, Zurich, Switzerland
• KP87: P. Karn , C. Partridge, Improving round-trip time estimates in reliable transport protocols, Proceedings of the ACM workshop on Frontiers in computer communications technology, p.2-7, August 11-13, 1987, Stowe, Vermont, United States
• Lud99: Reiner E. Ludwig, A Case for Flow-Adaptive Wireless Links, University of California at Berkeley, Berkeley, CA, 1999
• Mil83: David Mills. Internet Delay Experiments, December 1983. RFC 889.
• MM96: Matthew Mathis , Jamshid Mahdavi, Forward acknowledgement: refining TCP congestion control, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.281-291, August 28-30, 1996, Palo Alto, California, United States
• MMFR96: Matt Mathis, Jamshid Mahdavi, Sally Floyd, and Allyn Romanow. TCP Selective Acknowledgement Options, October 1996. RFC 2018.
• Mog92: Jeffrey C. Mogul, Observing TCP dynamics in real networks, Conference proceedings on Communications architectures & protocols, p.305-317, August 17-20, 1992, Baltimore, Maryland, United States
• MSMO97: 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]
• Nag84: John Nagle. Congestion Control in IP/TCP Intemetworks, January 1984. RFC 896.
• PAD+99: Vern Paxson, Mark Allman, Scott Dawson, William Fenner, Jim Griner, Ian Heavens, Kevin Lahey, Jeff Semke, and Bernie Volz. Known TCP Implementation Problems, March 1999. RFC 2525.
• Pax97a: Vern Paxson, Automated packet trace analysis of TCP implementations, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.167-179, September 14-18, 1997, Cannes, France
• Pax97b: 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
• Pax97c: Vern Edward Paxson, Measurements and analysis of end-to-end Internet dynamics, University of California at Berkeley, Berkeley, CA, 1998
• Pax98: Vern Paxson, On calibrating measurements of packet transit times, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.11-21, June 22-26, 1998, Madison, Wisconsin, United States
• Pos81: Jon Postel. Transmission Control Protocol, September 198 I. RFC 793.
• Ste97: W. Richard Stevens. TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms, January 1997. RFC 2001.
• TMW97: Kevin Thompson, Gregory Miller, and Rick Wilder. Wide-Area Intemet Traffic Patterns and Characteristics. IEEE Network, 11 (6): 10-23, November/December 1997.
• WS95: W. Richard Stevens , Gary R. Wright, TCP/IP illustrated (vol. 2): the implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• Zha86: L Zhang, Why TCP timers don't work well, Proceedings of the ACM SIGCOMM conference on Communications architectures & protocols, p.397-405, August 05-07, 1986, Stowe, Vermont, United States
• ZSC91: Lixia Zhang , Scott Shenker , Daivd D. Clark, Observations on the dynamics of a congestion control algorithm: the effects of two-way traffic, Proceedings of the conference on Communications architecture & protocols, p.133-147, September 03-06, 1991, Zurich, Switzerland

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

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

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