Network Working Group Y. Swami Internet-Draft K. Le Expires: August 31, 2006 Nokia Research Center, Dallas February 27, 2006 Decorrelated Loss Recovery (DCLOR) Using SACK Option for Spurious Timeouts draft-swami-tsvwg-tcp-dclor-07 Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. 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. This Internet-Draft will expire on August 31, 2006. Copyright Notice Copyright (C) The Internet Society (2006). Abstract A spurious timeout in TCP forces the sender to unnecessarily retransmit one complete congestion window of data into the network. In addition, the congestion state of the network could change substantially after a spurious timeout. In this draft we propose a conservative congestion response algorithm afert spurious timeout that takes network state into account. Swami & Le Expires August 31, 2006 [Page 1] Internet-Draft TCP DCLOR February 2006 1. Introduction The response of a TCP sender after a retransmission timeout is governed by the underlying assumption that a mid-stream timeout can occur only if there is heavy congestion--manifested as packet loss--in the network. TCP therefore assumes that a timeout is a sufficient indication to a) recover all the packets in flight, and b) to initiate a congestion response (slow start in this case) suited for heavy congestion scenarios. Although the assumption that a timeout can occur only if there is severe congestion is valid for traditional wireline networks, it does not hold good for some other types of networks--networks where packets can be stalled "in the network" for a significant duration without being discarded. In cellular networks, for example, the link layer can experience a relatively long disruption due to errors, and the link layer protocol can keep all packets buffered as long as the link layer disruption lasts. In this document we present an alternative approach to loss recovery and congestion control that "De-Correlates" Loss Recovery from congestion after a spurious. The algorithm described here follows the congestion control principle of [1] [3] and [5], but unlike the present go-back-N loss recovery algorithm after timeout, DCLOR only sends those segments that were actually lost in the network. Swami & Le Expires August 31, 2006 [Page 2] Internet-Draft TCP DCLOR February 2006 2. Terminology The key words "MUST," "MUST NOT," "REQUIRED," "SHALL," "SHALL NOT," "SHOULD," "SHOULD NOT," "RECOMMENDED," "MAY," "OPTIONAL," and "silently ignore" in this document are to be interpreted as described in RFC 2119. Swami & Le Expires August 31, 2006 [Page 3] Internet-Draft TCP DCLOR February 2006 3. Problem Description Let us assume that a TCP sender has sent N packets, p(1) ... p(N), into the network and it's waiting for the ACK of p(1). Due to bad network conditions or some other problem, these packets are excessively delayed at some intermediary node RTR-1. This excessive delay forces the TCP sender to timeout and enter slow start. As far as the sender is concerned, a timeout is always interpreted as heavy congestion. The TCP sender therefore makes the assumption that all packets between p(1) and p(N) were lost in the network. To recover from this misconstrued loss, the sender retransmits P1(1) and waits for the ACK a(1) ( where Px(k) represents the xth retransmission of packet with sequence number k). After some period of time when the network conditions at RTR-1 improve, the queued in packets are finally dispatched to their intended recipient. In response, TCP receiver generates the ACK a(1). When the TCP sender receives a(1), it's fooled into believing that a(1) was generated in response to the retransmitted packet p1(1), while in reality a(1) was generated in response to the originally transmitted packet p(1). When the sender receives a(1), it increases its congestion window to two, and retransmits p1(2) and p1(3). As the sender receives more acknowledgments, it continues with retransmissions and finally starts sending new data. Here we only analyze the congestion control behavior after a spurious timeout. Our scheme can be used in conjunction with the detection schemes in [6] and [9]. To analyze network congestion after spurious timeout, we compute the worst case scenario packet loss in the system--assuming only TCP connections to be present. After the timeout (real or spurious), the TCP sender sets its SS_THRESH to N/2. Therefore, for the first N/2 ACKs received (i.e., ACK a(1) to a(N/2)), the TCP sender will grow its congestion window by one and reach the SS_THRESH value of N/2. For each ACK received, the TCP sender sends 2 packets. Therefore, by the end of the slow start, the TCP sender would have sent 2*(N/2) packets into the network. For the remaining N/2 ACKs (i.e., ACKs between a(N/2+1) to a(N)) the TCP sender will remain in the congestion avoidance phase and send one packet for each ACK received--sending N/2 more data segments. The net amount of data sent is therefore N/2 + N = 3N/2. Please note that the entire 3N/2 packets are injected into the network within a time period less than or equal to RTT in most cases. The number of data segments that left the network during this time is only N. Therefore, the conservation of packet principle has been compromised, and of the 3N/2 packets injected in the network, N/2 Swami & Le Expires August 31, 2006 [Page 4] Internet-Draft TCP DCLOR February 2006 packets will be lost with a very high probability. These N/2 lost packets, however, need not come from the same connection, and such a data-burst will unnecessarily penalize all the competing TCP connections that share the same bottleneck router. Now let's assume there are M competing TCP connections that share the same bottleneck router(s) with C(0) (each connection is numbered C(0) ... C(M-1)). During the period of time while C(0) is stalled, the TCP sender does not use its network resources--the buffer space--on the bottleneck router(s). The competing connections, C(1)... C(M), however see this lack of activity as resource availability and start growing their window by at least one segment per RTT during this time period (by virtue of linear window increase during congestion avoidance phase). For simplicity reasons, we assume that each of these connections has the same round trip time of RTT, and the idle time for C(0) is k*RTT (where k > RTO/RTT). Under these assumptions, each of these competing connections will increase their congestion window by k segments. Therefore the amount of packets lost in the network due to slow start following a spurious timeout can be as high as: N/2 + M*k. The Eifel response algorithm [7] solves the problem of N/2 packet loss, by restoring the congestion window to an old value immediately before the spurious timeout. Based on the above equation, however, we note that the congestion state of the network not only depends upon the old window size, but also upon the duration of spurious timeout. In our response algorithm, we therefore take the time duration of spurious timeout into account by reducing the data rate by half every RTO. Please note that this scheme works well only when the number of competing connections M does not vary too much while C(0) was stalled. A more conservative response algorithm should reduce the data rate to INIT_WINDOW if M is not bounded. In addition to the above congestion and packet loss issues, the current response after spurious timeouts is inefficient, in the sense that it unnecessarily retransmits data that is not lost, but simply stalled. Such unnecessary retransmission is an issue when bandwidth resources are at a premium, like over a cellular link, where spectrum is scarce and expensive. Swami & Le Expires August 31, 2006 [Page 5] Internet-Draft TCP DCLOR February 2006 4. DCLOR Response Algorithm A TCP sender should follow [6] or [9] (or any other algorithm) to detect a spurious timeout. If the spurious timeout is confirmed and the TCP SACK option [4] is enabled, only then it SHOULD follow the DCLOR algorithm. The basic idea of this algorithm is that the ACKs received for the stalled packets don't provide sufficient information about the end- to-end congestion state of the network. Therefore, the sender reduces the congestion window by 1/2 every RTO, and waits for the ACK or SACK of a new data packet before increasing it's congestion window. Additionally, while the sender is waiting for the ACK/SACK of new data, it's allowed to send cwnd (the updated cwnd) worth of new data into the network. 1. The TCP sender MUST record the time when the first timeout took place, and when the first ACK after the timeout was received. Based on these times (or through some other means) it should compute the number of unbacked-off timeouts that must have taken place during this time period. Let's call this number N-RTO. The sender should also keep the highest sequence number of data packet that was sent in a variable called SS_PTR. The sender should also keep a counter called dclor_cntr, which allows the sender to send new data while it's waiting for the ACK or SACK of SS_PTR. Additionally, the sender MUST NOT update the SS_TRHESH value due to spurious timeouts (i.e., the spurious timeout algorithm should leave SS_THRESH values unaltered). 2. Once the Spurious Timeout is confirmed, the TCP sender should set cwnd = max( 2, pipe-size/2^N-RTO). ( where pipe-size is the packets in flight at the time when spurious timeout was confirmed.) Additionally, it should set dclor_cntr = 0. 3. For each ACK or SACK < SS_PTR (i.e., a SACK block whose left edge is < SS_PTR), the sender SHOULD send one *new* data packet if it is present and if dclor_cntr < cwnd and (rwnd < SND.NXT - SND.UNA). If (rwnd >= SND.NXT - SND.UNA) or if there is no new data to send, then the sender MUST retransmit no more than one packet per RTO from the tail of the retransmission queue regardless of the value of dclor_cntr. Moreover, for each *new* packet sent, dclor_cntr should be incremented by one. For ACK/ SACK < SS_PTR, the sender MUST not initiate any loss recovery algorithm nor should it update cwnd value. Additionally, the SS_THRESH should be left unchanged for all these ACKs. Swami & Le Expires August 31, 2006 [Page 6] Internet-Draft TCP DCLOR February 2006 4. If the sender receives a pure ACK > SS_PTR, it should update cwnd = cwnd+1, and follow normal TCP behavior. (Note that this means that none of the stalled packets were lost so we don't need to change SS_THRESH value). 5. If the sender receives a SACK block whose left edge is greater than SS_PTR, then it should traverse the retransmission queue from SND.UNA to the left edge of SACK block, and mark all unsacked packets as lost. Additionally, it should set cwnd = cwnd + 1 and reset SS_THRESH to 1/2 the pipe-size. Beyond this point, the sender MUST recover lost packets based on [2]. Swami & Le Expires August 31, 2006 [Page 7] Internet-Draft TCP DCLOR February 2006 5. Data Delivery To Upper Layers If a TCP sender loses its entire congestion window worth of data, sending new data after timeout prevents a TCP receiver from forwarding the new data to the upper layers immediately. However, once the SACK for this new data is received, the TCP sender will send the first lost segment. This essentially means that data delivery to the upper layers could be delayed by at most one RTT when all the packets are lost in the network. This, however, does not affect the throughput of the connection in any way. If a timeout has occurred, then the data delivery to the upper layers has already been excessively delayed. Delaying it by another round trip is not a serious problem. Please note that reliability and timeliness are two conflicting issues and one cannot gain on one without sacrificing something else on the other. Swami & Le Expires August 31, 2006 [Page 8] Internet-Draft TCP DCLOR February 2006 6. SACK reneging The TCP SACK information is meant to be advisory, and a TCP receiver is allowed--though strongly discouraged--to discard data blocks the receiver has already SACKed [4]. Please note however that even if the TCP receiver discards the data block it received, it MUST still send the SACK block for at least the recent most data received. Therefore in spite of SACK reneging, DCLOR will work without any deadlocks. A SACK implementation is also allowed not to send a SACK block even though the TCP sender and receiver might have agreed to SACK- Permitted option at the start of the connection. In these cases, however, if the receiver sends one SACK block, it must send SACK blocks for the rest of the connection. Because of the above mentioned leniency in implementation, its possible that a TCP receiver may agree on SACK-Permitted option, and yet not send any SACK blocks. To make DCLOR robust under these circumstances, DCLOR SHOULD NOT be invoked unless the sender has seen at least one SACK block before timeout. We, however, believe that once the SACK- Permitted option is accepted, the TCP receiver MUST send a SACK block--even though that block might finally be discarded. Otherwise, the SACK-Permitted option is completely redundant and serves little purpose. To the best of our knowledge, almost all SACK implementations send a SACK block if they have accepted the SACK- Permitted option. Swami & Le Expires August 31, 2006 [Page 9] Internet-Draft TCP DCLOR February 2006 7. Security Consideration DCLOR does not open TCP to new attacks. Swami & Le Expires August 31, 2006 [Page 10] Internet-Draft TCP DCLOR February 2006 8. Acknowledgments We would like to thank Shashikant Maheshwari, Pasi Sarolahti, and Mika Liljeberg for their comments and suggestions on a previous version of this draft. Special thanks to Jani Hirsimaki for thoroughly reviewing the document and providing feedback on the algorithm. 9. References [1] Allman, M., Paxson, V., and W. Stevens, "TCP Congestion Control", RFC 2581, April 1999. [2] Blanton, E., Allman, M., Fall, K., and L. Wang, "Conservative SACK-based Loss Recovery Algorithm for TCP", RFC 3517, April 2003. [3] Floyd, S., "Congestion Control Principles", RFC 2914, September 2002. [4] Floyd, S., Mahdavi, J., Mathis, M., and M. Podolsky, "TCP Selective Acknowledgement Options", RFC 2018, July 2000. [5] Handley, M., Padhye, J., and S. Floyd, "TCP Congestion Window Validation", RFC 2861, June 2000. [6] Ludwig, R. and M. Meyer, "The Eifel Detection Algorithm", RFC 3522, April 2003. [7] Ludwig, R. and A. Gurtov, "The Eifel Response Algorithm for TCP.", Internet draft; work in progress, draft-ietf-tsvwg- tcp- eifel-response-05.txt, March 2004. [8] Paxson, V. and M. Allman, "Computing TCP's Retransmission Timer", RFC 2988, November 2000. [9] Sarolahti, P. and M. Kojo, "F-RTO: A TCP RTO Recovery Algorithm for Avoiding Unnecessary Retransmissions.", Internet draft; work in progress, July 2004. Swami & Le Expires August 31, 2006 [Page 11] Internet-Draft TCP DCLOR February 2006 Authors' Addresses Yogesh Prem Swami Nokia Research Center, Dallas 6000 Connection Drive Irving, TX 75039 USA Phone: +1 972 374 0669 Email: yogesh.swami@nokia.com Khiem Le Nokia Research Center, Dallas 6000 Connection Drive Irving, TX 75039 USA Phone: +1 972 894 4882 Email: khiem.le@nokia.com Swami & Le Expires August 31, 2006 [Page 12] Internet-Draft TCP DCLOR February 2006 Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights 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; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat 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 implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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 OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Copyright Statement Copyright (C) The Internet Society (2006). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Swami & Le Expires August 31, 2006 [Page 13]