The Eifel algorithm: making TCP robust against spurious retransmissions

ABSTRACT

We propose an enhancement to TCP's error recovery scheme, which we call the Eifel algorithm. It eliminates the retransmission ambiguity, thereby solving the problems caused by spurious timeouts and spurious fast retransmits. It can be incrementally deployed as it is backwards compatible and does not change TCP's congestion control semantics. In environments where spurious retransmissions occur frequently, the algorithm can improve the end-to-end throughput by several tens of percent. An exact quantification is, however, highly dependent on the path characteristics over time. The Eifel algorithm finally makes TCP truly wireless-capable without the need for proxies between the end points. Another key novelty is that the Eifel algorithm provides for the implementation of a more optimistic retransmission timer because it reduces the penalty of a spurious timeout to a single (in the common case) spurious retransmission.

REFERENCES

• 1: M. Allman, V. Paxson, W. Stevens, TCP Congestion Control, RFC 2581, April 1999.
• 2: 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
• 3: S. Baucke, Leistungsbewertung und Optimierung yon TCP fiir den Einsatz im Mobilfunknetz GSM, Diploma Thesis, CS-Dept. 4, Aachen University of Technology, Germany, April 1997.
• 4: 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]
• 5: M. Degermark, B. Nordgren, S. Pink, IP Header Compression, RFC 2507, February 1999.
• 6: S. Floyd, J. Mahdavi, M. Mathis, M. Podolsky, A. Romanow, An Extension to the Selective Acknowledgement (SACK) Option for TCP, work in progress, August 1999.
• 7: ISO/IEC, Information processing systems - Open Systems Interconnection - Connection oriented transport protocol specification, International Standard ISO/IEC 8073, December 1988.
• 8: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 9: V. Jacobson, Modified TCP Congestion Avoidance Algorithm, end2end-interest mailing list (ftp://ftp.isi.edu/end2end/end2end-interest-1990.mail), April 30, 1990.
• 10: V. Jacobson, C. Leres, S. McCanne, tcpdump, available at http://ee.lbl.gov/.
• 11: V. Jacobson, R. Braden, D. Borman, TCP Extensions for High Performance, RFC 1323, May 1992.
• 12: V. Jacobson, Compressing TCP/IP Headers for Low-Speed Serial Links, RFC 1144, February 1990.
• 13: 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
• 14: Reiner Ludwig , Bela Rathonyi , Almudena Konrad , Kimberly Oden , Anthony Joseph, Multi-layer tracing of TCP over a reliable wireless link, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.144-154, May 01-04, 1999, Atlanta, Georgia, United States
• 15: Reiner E. Ludwig, A Case for Flow-Adaptive Wireless Links, University of California at Berkeley, Berkeley, CA, 1999
• 16: Reiner Ludwig , Almudena Konrad , Anthony D. Joseph , Randy H. Katz, Optimizing the end-to-end performance of reliable flows over wireless links, Wireless Networks, v.8 n.2/3, p.289-299, March-May 2002 [doi>10.1023/A:1013750211660]
• 17: R. Ludwig, TCP-Eifel, Patches for FreeBSD, available at http://iceberg.cs.berkeley.edu, October 1999.
• 18: M. Mathis, J. Mahdavi, S. Floyd, A. Romanow, TCP Selective Acknowledgement Options, RFC 2018, October 1996.
• 19: 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]
• 20: S. McCanne, V. Jacobson, The BSD Packet Filter: A New Architecture for User-Level Packet Capture, In Proceedings of the 1993 Winter USENIX Conference.
• 21: Vern Paxson, End-to-end routing behavior in the Internet, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.601-615, Oct. 1997 [doi>10.1109/90.649563]
• 22: J. Postel, Internet Protocol, RFC 791, September 1981.
• 23: J. Postel, Transmission Control Protocol, RFC793, September 1981.
• 24: W. Simpson, The Point-to-Point Protocol, RFC 1661, July 1994.
• 25: W. Richard Stevens, TCP/IP illustrated (vol. 1): the protocols, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
• 26: W. Richard Stevens , Gary R. Wright, TCP/IP illustrated (vol. 2): the implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995