On making TCP more robust to packet reordering

ABSTRACT

Previous research indicates that packet reordering is not a rare event on some Internet paths. Reordering can cause performance problems for TCP's fast retransmission algorithm, which uses the arrival of duplicate acknowledgments to detect segment loss. Duplicate acknowledgments can be caused by the loss of a segment or by the reordering of segments by the network. In this paper we illustrate the impact of reordering on TCP performance. In addition, we show the performance of a conservative approach to "undo" the congestion control state changes made in conjunction with spurious retransmissions. Finally, we propose several alternatives to dynamically make the fast retransmission algorithm more tolerant of the reordering observed in the network and assess these algorithms.

REFERENCES

• 1: {ABF01} Mark Allman, Hari Balakrishnan, and Sally Floyd. Enhancing TCP's Loss Recovery Using Limited Transmit, January 2001. RFC 3042.
• 2: Mark Allman, A web server's view of the transport layer, ACM SIGCOMM Computer Communication Review, v.30 n.5, October 2000 [doi>10.1145/505672.505674]
• 3: Mark Allman , Vern Paxson, On estimating end-to-end network path properties, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.263-274, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 4: {APS99} Mark Allman, Vern Paxson, and W. Richard Stevens. TCP Congestion Control, April 1999. RFC 2581.
• 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: Hari Balakrishnan , Hariharan S. Rahul , Srinivasan Seshan, An integrated congestion management architecture for Internet hosts, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.175-187, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 7: 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]
• 8: Sally Floyd , Kevin Fall, Promoting the use of end-to-end congestion control in the Internet, IEEE/ACM Transactions on Networking (TON), v.7 n.4, p.458-472, Aug. 1999 [doi>10.1109/90.793002]
• 9: {FMMP00} Sally Floyd, Jamshid Mahdavi, Matt Mathis, and Matt Podolsky. An Extension to the Selective Acknowledgement (SACK) Option for TCP, July 2000. RFC 2883.
• 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: {JBB92} Van Jacobson, Robert Braden, and David Borman. TCP Extensions for High Performance, May 1992. RFC 1323.
• 12: 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
• 13: 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]
• 14: {MC00} Sean McCreary and K. Claffy. Trends in Wide Area IP Traffic Patterns A View from Ames Internet Exchange, May 2000. http://www.caida.org/outreach/papers/AIX0005/.
• 15: {MSML99} Matt Mathis, Jeff Semke, Jamshid Mahdavi, and Kevin Lahey. The Rate-Halving Algorithm for TCP Congestion Control, August 1999. Internet-Draft draft-mathis-tcp-ratehalving-00.txt (work in progress).
• 16: {PA00} Vern Paxson and Mark Allman. Computing TCP's Retransmission Timer, November 2000. RFC 2988.
• 17: 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
• 18: {Pos81} Jon Postel. Transmission Control Protocol, September 1981. RFC 793.
• 19: 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
• 20: {TMW97} Kevin Thompson, Gregory Miller, and Rick Wilder. Wide-Area Internet Traffic Patterns and Characteristics. IEEE Network, 11(6):10-23, November/December 1997.
• 21: {Tou97} Joe Touch. TCP Control Block Interdependence, April 1997. RFC 2140.

INDEX TERMS

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

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

General Terms:
Theory