Estimating loss rates with TCP

ABSTRACT

Estimating loss rates along a network path is a problem that has received much attention within the research community. However, deriving accurate estimates of the loss rate from TCP transfers has been largely unaddressed. In this paper, we first show that using a simple count of the number of retransmissions yields inaccurate estimates of the loss rate in many cases. The mis-estimation stems from flaws in TCP's retransmission schemes that cause the protocol to spuriously retransmit data in a number of cases. Next, we develop techniques for refining the retransmission count to produce a better loss rate estimate for both Reno and SACK variants of TCP. Finally, we explore two SACK-based variants of TCP with an eye towards reducing spurious retransmits, the root cause of the mis-estimation of the loss rate. An additional benefit of reducing the number of needless retransmits is a reduction in the amount of shared network resources used to accomplish no useful work.

REFERENCES

• 1: Mark Allman, Measuring end-to-end bulk transfer capacity, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505220]
• 2: {APS99} Mark Allman, Vern Paxson, and W. Richard Stevens. TCP Congestion Control, April 1999. RFC 2581.
• 3: Ethan Blanton , Mark Allman, On making TCP more robust to packet reordering, ACM SIGCOMM Computer Communication Review, v.32 n.1, p.20-30, January 2002 [doi>10.1145/510726.510728]
• 4: {BAFW03} Ethan Blanton, Mark Allman, Kevin Fall, and Lili Wang. A Conservative Selective Acknowledgment (SACK)-based Loss Recovery Algorithm for TCP, April 2003. RFC 3517.
• 5: Jon C. R. Bennett , Craig Partridge , Nicholas Shectman, Packet reordering is not pathological network behavior, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.789-798, Dec. 1999 [doi>10.1109/90.811445]
• 6: {BV02} Peter Benko and Andras Veres. A Passive Method for Estimating End-to-End TCP Packet Loss. In Proceedings of IEEE Globecom, 2002.
• 7: {EOA03} Wesley Eddy, Shawn Ostermann, and Mark Allman. New Techniques for Making Transport Protocols Robust to Corruption-Based Loss, July 2003. Under submission.
• 8: 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]
• 9: {FH99} Sally Floyd and Tom Henderson. The NewReno Modifi cation to TCP's Fast Recovery Algorithm, April 1999. RFC 2582.
• 10: {Flo95} Sally Floyd. TCP and Successive Fast Retransmits. Technical report, Lawrence Berkeley Laboratory, May 1995.
• 11: {Flo00} Sally Floyd. Congestion Control Principles, September 2000. RFC 2914.
• 12: {FMMP00} Sally Floyd, Jamshid Mahdavi, Matt Mathis, and Matt Podolsky. An Extension to the Selective Acknowledgement (SACK) Option for TCP, July 2000. RFC 2883.
• 13: 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
• 14: {JBB92} Van Jacobson, Robert Braden, and David Borman. TCP Extensions for High Performance, May 1992. RFC 1323.
• 15: Hao Jiang , Constantinos Dovrolis, Passive estimation of TCP round-trip times, ACM SIGCOMM Computer Communication Review, v.32 n.3, p.75-88, July 2002 [doi>10.1145/571697.571725]
• 16: {KAPS02} Rajesh Krishnan, Mark Allman, Craig Partridge, and James P. G. Sterbenz. Explicit Transport Error Notification (ETEN) for Error-Prone Wireless and Satellite Networks. Technical Report TR-8333, BBN Technologies, March 2002.
• 17: {KR02} Rajeev Koodli and Rayadurgam Ravikanth. One-Way Loss Pattern Sample Metrics, August 2002. RFC 3357.
• 18: Reiner Ludwig , Randy H. Katz, The Eifel algorithm: making TCP robust against spurious retransmissions, ACM SIGCOMM Computer Communication Review, v.30 n.1, January 2000 [doi>10.1145/505688.505692]
• 19: {MA01} Matt Mathis and Mark Allman. A Framework for Defining Empirical Bulk Transfer Capacity Metrics, July 2001. RFC 3148.
• 20: {MMFR96} Matt Mathis, Jamshid Mahdavi, Sally Floyd, and Allyn Romanow. TCP Selective Acknowledgement Options, October 1996. RFC 2018.
• 21: 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]
• 22: {PAM00} Vern Paxson, Andrew Adams, and Matt Mathis. Experiences with NIMI. In Proceedings of Passive and Active Measurement, 2000.
• 23: 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
• 24: {PF01} Jitendra Padhye and Sally Floyd. Identifying the TCP Behavior of Web Servers. In ACM SIGCOMM, August 2001.
• 25: Jitendra Padhye , Victor Firoiu , Don Towsley , Jim Kurose, Modeling TCP throughput: a simple model and its empirical validation, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.303-314, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 26: {PMAM98} Vern Paxson, Jamshid Mahdavi, Andrew Adams, and Matt Mathis. An Architecture for Large-Scale Internet Measurement. IEEE Communications, 1998.
• 27: {Pos81} Jon Postel. Transmission Control Protocol, September 1981. RFC 793.
• 28: {Sav99} Stefan Savage. Sting: a TCP-based Network Measurement Tool. In Proceedings of the 1999 USENIX Symposium on Internet Technologies and Systems, October 1999.
• 29: {SKR02} Pasi Sarolahti, Markku Kojo, and Kimmo Raatikainen. FRTO: A New Recovery Algorithm for TCP Retransmission Time-outs. Technical Report C-2002-07, University of Helsinki, February 2002.
• 30: Jeffrey Semke , Jamshid Mahdavi , Matthew Mathis, Automatic TCP buffer tuning, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.315-323, August 31-September 04, 1998, Vancouver, British Columbia, Canada