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]