Internet Engineering Task Force K. Tan Internet Draft Q. Zhang Document: draft-kun-stoder-00.txt W. Zhu Category: Informational Microsoft Research Asia Expires: February 2005 STODER: A Reliable TCP Spurious Timeout Detection Algorithm using Repacketization Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026 except that the right to produce derivative works is not granted. This document is an Internet-Draft and is NOT offered in accordance with Section 10 of RFC2026, and the author does not provide the IETF with any rights other than to publish as an Internet-Draft Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. 1. Abstract Spurious timeouts are not rare events in wireless wide-area network, e.g. GPRS or EDGE. It has been reported that spurious timeouts greatly decrease TCP's performance in many aspects. It is not only because of the unnecessary retransmission of the last window of data, but also the congestion control is falsely triggered. Existing proposals of detecting spurious timeouts either require additional information on each data packet, e.g., the timestamps option, or heuristically deduce spurious timeouts. These approaches need heuristic feedbacks from the receiver, and hence are vulnerable to misbehaving receivers. In this document, a novel algorithm that reliably detects spurious TCP retransmission timeouts, called STODER, is presented. STODER is a TCP sender algorithm and does not require any information attached on data packets. STODER exploits TCP repacketization to detect false retransmission and is well protected against malicious receivers. Therefore, a more aggressive response algorithm can be safely applied along with the STODER algorithm. 2. Conventions used in this document Expiration: Feburary 2005 [Page 1] draft-kun-stoder-00.txt July, 2004 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC-2119. 3. Introduction It has been widely understood that the Transmission Control Protocol (TCP) [Pos81] may experience premature timeouts in wireless wide-area networks, such as GPRS and EDGE [LK00][TZZ04]. In these cases, the timeout segments are not dropped but just delayed in the network, due to the large delay variances in the wireless network. There are several sources of these delay variances. For example, the local retransmission of the reliable link layer [FW02], the fading on the wireless channel and the channel-state based scheduling [BBKT96]. Spurious timeouts degrade TCP performance mainly in two aspects: 1) outstanding segments are unnecessarily retransmitted, and therefore scare wireless bandwidth are wasted; and 2) the congestion control is falsely triggered. It may possible to refine the retransmission timeout calculation algorithm for better estimation in wireless networks. However, it may not be easy due to the randomness on the wireless network. Therefore, many researches propose more practical ways to mitigate the performance penalty by detecting such spurious timeout events. As a spurious timeout may not indicate congestion, a TCP sender can avoid the unnecessary transmission and undo the congestion control by transmitting with a larger window. Previously, several spurious detection algorithms have been proposed, such as Eifel [LM03], the DSACK-based algorithm [BA04] and F-RTO [SK04]. The Eifel algorithm uses TCP timestamps [BBJ92] carried in every packet to detect a spurious timeout after timeout retransmissions. The DSACK-based algorithm examines the DSACK extension [FMPR00] carried in ACK packet to find out the unnecessary duplicate transmissions after a timeout. These two algorithms require both ends' support for detection. F-RTO is an alternative algorithm that does not require any TCP options and is implemented only on the TCP sender side. F-RTO alternates the TCP retransmission behavior after a timeout and deduces a spurious timeout by monitoring the returned ACK pattern. Nevertheless, the aforementioned schemes require the cooperation of both ends to work well, as all of them need the heuristic feedbacks from the receiver, e.g., echoed timestamps, DSACK blocks or duplicate ACKs. If an aggressive response algorithm is adopted after spurious timeouts, e.g., undo congestion control, the receiver may have incentive to feed false hints to the sender and make genuine retransmits appear to the TCP sender as spurious retransmits. By doing so, a malicious user is able to effectively disable the congestion control and steal more bandwidth. In [LM03], Ludwig, et. al., proposes a secure version of Eifel to protect against the malicious receivers. However, the proposed scheme adds much overhead in implementation, and moreover degrades the ability of detection, as it is very sensitive to ACK loses. Expiration: Feburary 2005 [Page 2] draft-kun-stoder-00.txt July, 2004 In this document, a novel spurious timeout detection algorithm is proposed, called STODER (Spurious TimeOut Detection using Repacketization), which can reliably detect spurious timeouts even facing misbehavior receivers. Similar to F-RTO, STODER is a sender- side only modification to the standard TCP and it does not require additional information carried in data packets, e.g., TCP options. Note that STODER is designed mainly for detecting spurious timeouts, unlike Eifel and DSACK, which can also be applied to detect other duplicate transmissions, for example, due to packet reordering. In the next section, the STODER algorithm is described in details. Section 5 discusses the security issues. Section 6 describes the response actions after the STODER detection. Both behaviors after a genuine timeout as well as a spurious timeout are discussed. 4. The STODER Algorithm The STODER algorithm kicks in only after a retransmission timeout. Upon a timeout, the STODER TCP sender repacketizes a packet which is smaller than the original transmission, which is called "STODER packet". After retransmission of the STODER packet, the sender waits for an acceptable ACK. If the ACK covers more data than the STODER packet, the original transmission must have been received, and hence it may indicate a spurious timeout. Otherwise, if the ACK acknowledges only the right edge of the STODER packet or less, a genuine timeout is claimed. We use the "SpuriousRecovery" variable to indicate whether or not the previous timeout is detected as spurious one. We use redge(i) indicates the right edge of the ith packet that is outstanding. Let's first assume that the TCP sender has stored the boundary information of every outstanding packet in an array. And later, we will show how to reduce this implementation overhead. A TCP sender MAY implement the STODER algorithm, and if it chooses to apply STODER, the following steps MUST be taken after a retransmission timeout. 1) When the retransmission timer expires, the TCP sender SHOULD repacketize a STODER segment which is one-bytes smaller that the original segment and retransmit. The right edge of the STODER segment is kept in a variable named s-redge. That is, s-redge = redge(1)-1. 2) When the acceptable acknowledgement [Pos81] arrives at the sender, the sender compares the acknowledgement field in the packet to s- redge. 3) If the ACK acknowledges more data beyond s-redge, the sender concludes that the original transmission must have been received, and therefore set SpuriousRecovery to SPUR-TO. Expiration: Feburary 2005 [Page 3] draft-kun-stoder-00.txt July, 2004 4) Otherwise, if the ACK acknowledges data less or equal to s-redge, the sender MUST claim a genuine timeout and set SpuriousRecovery to FALSE. If another retransmission timeout occurs before the TCP sender receives an acceptable ACK in Step 2). The same STODER segment SHOULD be retransmitted. We can see that the STODER detection algorithm is rather simple, but highly effective in detecting false retransmission after a timeout. It exploits TCP repacketization to remove the retransmission ambiguity [KP91], which is the origin difficulty for TCP senders to detect spurious retransmissions. 4.1 Reducing the storage overhead of STODER The algorithm described above assumes the availability of the boundary information of every outstanding segments. However, practically, this overhead can be greatly reduced. It is based on the observation that the TCP sender is always trying to send out full- sized segments with the Nagel algorithm turned on [Nag84]. The Nagle algorithm regulates the generation of packets at TCP senders and allows none full-sized packets to be transmitted only when there is no packet outstanding. This implies that only one none full-sized packet is allowed to be outstanding per window. Therefore, with the Nagle algorithm, only one variable is needed to store the boundary of the partial-sized packet. Note that many modern systems do not implement the standard Nagel algorithm, instead they apply other variances of the Nagel algorithm, which may regulate TCP segments on every application message [MM01]. If such variances are implemented, the boundaries of the application messages MUST be stored. However, the number of application messages is usually much less than the number of outstanding segments. Moreover, in many systems, such information is already stored for other reasons, e.g., efficient memory buffer management. 5. Protect against the misbehavior receivers As stated above, the STODER algorithm can well protect against the misbehavior receivers. It is because that STODER exploits the reliable semantics of TCP to conduct spurious timeout detection. In case of genuine timeouts (the original segment transmission is not received), as the STODER packet is smaller than the original segment, the receiver is forced to acknowledge up to the right edge of the STODER packet, and therefore the TCP sender reliably detects the loss. If the receiver chooses to acknowledge above the STODER packet, it may cheat the sender to claim a spurious timeout and follow an fast recovery path (e.g., undo congestion control). However, as the receiver acknowledges data that it does not receive, it violates the reliable semantic of TCP and the missing bytes will never be Expiration: Feburary 2005 [Page 4] draft-kun-stoder-00.txt July, 2004 retransmitted any more. Note that if a receiver chooses to scarify the reliable semantics, it can conduct the same attack to the standard TCP anyway. Therefore, we claim that the STODER detection algorithm retains the same security level as conventional TCP and exposures no new vulnerability 6. Response after the STODER detection If the STODER detection result shows that the original transmission is lost (hence the timeout is genuine), the TCP sender SHOULD fall back to the conventional slow-start recovery phase. In this situation, without SACK information, the TCP sender will normally perform a go- back-N retransmission. Since the STODER packet is smaller than the original segments, it can not fill the sequence hole due to the loss of the original segments. Therefore, it may cause a few segments unnecessarily retransmitted. In the worst case, two full-sized packets are unnecessarily retransmitted comparing to the standard TCP (in this case, only one segment is lost and timeout occurs). However, this behavior can be corrected if SACK is enabled. Since now the TCP sender have clear information of missing segments, unnecessary retransmission can be effectively avoided. Although an additional packet (maybe 1-byte in size) may still need to be sent to fill the gap, the overall throughput of the TCP connection is not affected. Note that there is only one such small packet generated per timeout event. We believe it will only modestly stress the network. Upon detecting a spurious timeout, the TCP sender MAY stop retransmission, as the spurious timeout may indicate that the outstanding packets are still flying in the network. Different response approaches may be applied. Several recovery strategies have discussed in the literature. Eifel [LG03] suggests to directly restore the congestion control states after detection of a spurious timeout; while the authors in [TZZ04] propose a relative conservative way that adaptively adjust congestion control state based on the returning ACKs. This document does not give recommendation on which response algorithm should be applied. Nevertheless, since spurious timeouts may not indicate a congestion event, undo congestion control may greatly improve TCP's performance over wireless networks. As STODER can reliably detect spurious timeouts in all situations, such efficient (yet aggressive) response algorithms can be safely adopted. 8. Security Considerations STODER will not cause security issues as we have discussed in Section 5. 9. IPR Considerations Expiration: Feburary 2005 [Page 5] draft-kun-stoder-00.txt July, 2004 The IETF has been notified of intellectual property rights claimed in regard to some or all of the specification contained in this document. For more information consult the online list of claimed rights at http://www.ietf.org/ipr. The IETF takes no position regarding the validity or scope of any intellectual property or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; neither does it represent that it has made any effort to identify any such rights. Information on the IETF's procedures with respect to rights in standards-track and standards-related documentation can be found in BCP-11. Copies of claims of rights made available for publication and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementors or users of this specification can be obtained from the IETF Secretariat. Expiration: Feburary 2005 [Page 5] draft-kun-stoder-00.txt July, 2004 10. References Normative References [BBJ92] D. Borman, R. Braden, and V. Jacobson. TCP Extensions forHigh Performance. RFC 1323, May 1992. [FMPR00] S. Floyd, J. Mahdavi, M. Mathis, M. Podolsky and A. Romanow. An Extension to the Selective Acknowledgement (SACK) Option for TCP. RFC 2883, July 2000. [Pos81] J. Postel. Transmission Control Protocol. RFC 793, September 1981. [Nag84] J. Nagle. Congestion control in IP/TCP internetworks. RFC 896, Internet Engineering Task Force, Jan. 1984. Informative References [BA04] E. Blanton and M. Allman. Using TCP DSACKs and SCTP TSNs to Detect Spurious Retransmissions. RFC 3708, Feb. 2004. [BBKT96] P. Bhagwat, P. Bhattacharya, A. Krishna, and S. Tripathi. Enhancing Throughput over Wireless LANs Using Channel State Dependent Packet Scheduling. In Proc. IEEE INFOCOMĘ96, pp. 1133-40, March 1996. [FW02] G. Fairhurst and L. Wood. Advice to link designers on link Automatic Repeat reQuest (ARQ). BCP 62, RFC 3366, August 2002. [KP91] P. Karn and C. Partridge. Improving Round-Trip Time Estimates in Reliable Transport Protocols. ACM Transactions on Computer Systems, November 1991. [LG03] R. Ludwig and A. Gurtov. The Eifel Response Algorithm for TCP. Internet draft "draft-ietf-tsvwg-tcp-eifel-response- 04.txt". October 2003. Work in progress. [LK00] R. Ludwig and R. H. Katz. The Eifel Algorithm: Making TCP Robust Against Spurious Retransmissions. ACM Computer Communications Review, Vol. 30, No. 1, January 2000. [LM03] R. Ludwig and M. Meyer. The Eifel Detection Algorithm for TCP. RFC 3522, April 2003. [MM01] J. Mogul and G. Minshall. Rethinking the TCP Nagle Algorithm. ACM SIGCOMM Computer Communication Review, January, 2001. Expiration: Feburary 2005 [Page 6] draft-kun-stoder-00.txt July, 2004 [SK04] P. Sarolahti and M. Kojo. F-RTO: An Algorithm for Detecting Spurious Retransmission Timeouts with TCP and SCTP. Internet draft, draft-ietf-tsvwg-tcp-frto-01.txt Feburary 2004. [TZZ04] K. Tan, Q. Zhang and W. Zhu. STODER: A Robust and Efficient Algorithm for Handling Spurious Retransmit Timeouts in TCP. In submission, 2004. 11. Acknowledgments The authors are grateful to Mr. Hongbin Liao, Dr. Chuanxiong Guo and Dr. Fan Yang for the discussion and feedback contributed to this work. 12. Author's Addresses Kun Tan Microsoft Research Asia 3F Sigma Center No. 49 Zhichun Road. Beijing 100084, P.R.China Email: t-kuntan@microsoft.com Qian Zhang Microsoft Research Asia 3F Sigma Center No. 49 Zhichun Road. Beijing 100084, P.R.China Email: qianz@microsoft.com Wenwu Zhu Microsoft Research Asia 3F Sigma Center No. 49 Zhichun Road. Beijing 100084, P.R.China Expiration: Feburary 2005 [Page 7] draft-kun-stoder-00.txt July, 2004 Full Copyright Statement Copyright (C) The Internet Society (2003). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Expiration: Feburary 2005 [Page 8]