Internet Engineering Task Force M. Kojo INTERNET-DRAFT University of Helsinki draft-kojo-tcpm-frto-eval-01.txt K. Yamamoto Expires: May 2008 M. Hata NTT Docomo P. Sarolahti Nokia Research Center 19 November 2007 Evaluation of RFC 4138 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 May 2008. Abstract Forward-RTO recovery (F-RTO) specified in RFC 4138 is an algorithm for detecting a spurious retransmission timeout with TCP and SCTP. This document describes the advantages of F-RTO and summarizes the Kojo/Yamamoto/Hata/Sarolahti [Page 1]
INTERNET-DRAFT Expires: May 2008 November 2007 experience in its implementations and the experiments conducted with it. By analyzing the implications of the spurious retransmission timeouts on the regular RTO recovery and Forward-RTO recovery algorithm, including a detailed corner case analysis, it shows that F-RTO does not have negative impact on the network when used with an appropriate response algorithm even in the rare cases where F-RTO falsely declares a retransmission timeout spurious. It concludes with a recommendation that F-RTO is to be advanced to the standards track. Kojo/Yamamoto/Hata/Sarolahti [Page 2]
INTERNET-DRAFT Expires: May 2008 November 2007 Table of Contents 1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Conventions and Terminology. . . . . . . . . . . . . . . 4 2. Problems with the Regular RTO Recovery. . . . . . . . . . . . 4 2.1. Unnecessary Retransmissions. . . . . . . . . . . . . . . 4 2.2. Dishonoring the Packet Conservation Princi- ple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3. Unnecessary Reduction of the Congestion Win- dow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.4. Other Problems . . . . . . . . . . . . . . . . . . . . . 6 3. Advantages and Motivation . . . . . . . . . . . . . . . . . . 7 3.1. Avoiding Unnecessary Retransmissions . . . . . . . . . . 7 3.2. Adhering to the Packet Conservation Princi- ple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.3. Selecting an Appropriate Congestion Control Response. . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.4. Other Advantages . . . . . . . . . . . . . . . . . . . . 8 3.5. Non-spurious RTOs and Undetected Spurious RTOs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4. Experimental Results. . . . . . . . . . . . . . . . . . . . . 9 4.1. Initial trials in an emulated network. . . . . . . . . . 9 4.2. F-RTO Performance over Commercial W-CDMA Networks. . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.3. Impact of Malicious Receiver on Network and Regular TCP Connection. . . . . . . . . . . . . . . . . . . . 11 5. Hidden Packet Losses. . . . . . . . . . . . . . . . . . . . . 11 5.1. Loss of Retransmitted Segments . . . . . . . . . . . . . 12 5.2. Reordering . . . . . . . . . . . . . . . . . . . . . . . 12 5.3. Malicious Receiver . . . . . . . . . . . . . . . . . . . 13 6. Conclusions and Recommendations . . . . . . . . . . . . . . . 14 References . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 AUTHORS' ADDRESSES . . . . . . . . . . . . . . . . . . . . . . . 17 Full Copyright Statement . . . . . . . . . . . . . . . . . . . . 18 Intellectual Property. . . . . . . . . . . . . . . . . . . . . . 18 1. Introduction A temporary delay spike or a more permanent but sudden delay increase in the TCP data or ACK path may result in a spurious retransmission timeout (RTO) that triggers a premature retransmission of the first unacknowledged data segment followed by an unnecessary loss recovery in slow-start. This creates severe problems with the regular RTO recovery algorithm as the late acknowledgments of the original segments trigger unnecessary retransmissions at a high rate. This introduces useless load into the network in the form of a (large) packet burst. In addition, the TCP sender will reduce its transmission rate quite unnecessarily Kojo/Yamamoto/Hata/Sarolahti Section 1. [Page 3]
INTERNET-DRAFT Expires: May 2008 November 2007 because the congestion control algorithms are falsely triggered, resulting in decreased TCP performance. When a spurious RTO occurs, a TCP sender employing the Forward RTO- Recovery (F-RTO) algorithm [RFC4138] is able to avoid the problems encountered with the regular RTO recovery by detecting that the TCP retransmission timer expired spuriously and by avoiding additional unnecessary retransmissions. In addition, the F-RTO sender may elude the unnecessary performance degradation by restoring the congestion control state and/or reduce the risk of falsely triggering TCP's loss recovery and congestion control again in the later phases of the connection by adapting the RTT estimators. This document discusses the problems with the regular TCP RTO recovery when spurious RTOs are encountered and evaluates the F-RTO algorithm as a standards track alternative for the regular RTO recovery. 1.1. Conventions and Terminology 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 [RFC2119]. 2. Problems with the Regular RTO Recovery When a spurious retransmission timeout occurs, the regular RTO recovery is incapable of avoiding unnecessary retransmissions and also fails in adhering to the packet conservation principle [Jac88] by injecting the unnecessary retransmissions into the network at a rate that is higher than the rate at which packets are leaving the network. In addition, after bursting the unnecessary retransmissions into the network the transmission is continued at an unnecessarily low rate. 2.1. Unnecessary Retransmissions After the first unacknowledged segment triggered by a spurious retransmission timeout has been transmitted, the late acknowledgments of the original segments arrive at the sender and trigger further unnecessary retransmissions in slow start. The first late ACK triggers unnecessary retransmission of the next segment(s) which, in turn, will get acknowledged by the next late ACK quite immediately, injecting the next segments from the retransmission queue into the network. Assuming that none of the original segments Kojo/Yamamoto/Hata/Sarolahti Section 2.1. [Page 4]
INTERNET-DRAFT Expires: May 2008 November 2007 and none of the corresponding late ACKs were lost, this chain reaction results in unnecessary retransmission of all outstanding segments. Depending on the flight size at the time when the spurious RTO occurred, a large number of unnecessary retransmissions may get injected into the network as useless load. This often creates a significant problem in network environments where sudden delay spikes tend to appear because such networks often offer a low or moderate transmission capacity and any excess load significantly reduces the available network capacity for delivering useful traffic. In addition, unnecessary transmissions waste the battery power of wireless devices and introduce extra costs when the access link usage is billed per transmission volume. 2.2. Dishonoring the Packet Conservation Principle The purpose of the TCP slow-start algorithm is to (re)start the ACK clock and probe the network for available capacity. However, when the retransmission timeout expires spuriously the TCP sender fails to restart the ACK clock at a correct rate and is not able to probe the available network capacity correctly. This is because the acknowledgements acknowledging the retransmissions do not arrive one round-trip time (RTT) after the retransmission as supposed. Instead, the retransmissions are acknowledged by the late acknowledgements that arrive at the line rate of the bottleneck link on the end-to- end path or, in some cases, at much higher rate. Therefore, the late acknowledgements clock out the unnecessary retransmissions within one RTT using slow start and potentially 50 percent more data segments are transmitted to the network in one RTT than what the TCP sender in steady state would have transmitted if the spurious RTO had not occurred. This violates the packet conservation principle [Jac88]. Assuming no packets are lost and delayed ACKs are in use, each late acknowledgement (except the first one) arriving after a spurious RTO triggers three unnecessary retransmissions into the network until all segments in the retransmission queue have been retransmitted. After this, the TCP sender continues by transmitting three new segments on each late acknowledgement. The number of the new segments triggered by the late acknowledgements equals to the half of the flight size at the time when spurious RTO occurred. This injects 50 percent more segments into the network within one RTT compared to the number of segments injected in one RTT by a TCP sender in steady state, i.e., three segments per ACK instead of two segments per ACK. Kojo/Yamamoto/Hata/Sarolahti Section 2.2. [Page 5]
INTERNET-DRAFT Expires: May 2008 November 2007 Assuming no packets are lost and delayed ACKs are not in use, each late acknowledgement corresponding to the first half of the original flight triggers two unnecessary retransmissions into the network. The late acknowledgements belonging the second half of the original flight trigger a transmission of one new segment each. This means that during the first half of the RTT, the sending rate is doubled compared to the rate at which a TCP sender in steady state would have transmitted if the spurious RTO had not occurred. The new data segments transmitted after the unnecessary retransmissions during the same RTT are likely to experience congestion as the preceding unnecessary retransmission of the whole window of segments is likely to occupy the bottleneck link queue. This may result in serious a performance penalty as the TCP sender is often forced to wait for a backed-off retransmission timer to expire in order to recover the lost segments. A figure depicting an example of such a behavior is available at [http://www.iki.fi/pasi.sarolahti/frto/]. 2.3. Unnecessary Reduction of the Congestion Window When a spurious RTO occurs, the TCP sender enters loss recovery and reduces the congestion window and slow-start threshold. If the RTO was spurious, the reduction is likely to be unnecessary and results in sacrificed TCP performance. The impact of this unnecessary congestion control action is particularly notable in high latency environments where restoring the previous congestion window takes a long time. 2.4. Other Problems Updating the RTO estimate on retransmitted segments is not possible due to the retransmission ambiguity problem [Zh86, KP87]. Therefore, the RTO estimate is not updated for segments that experience the unusually long delay and cause the spurious RTOs. This means that the delayed segments are ignored in updating the RTO estimate and, in the worst case, the temporary delay spikes are never reflected to the RTO estimate, allowing a later delay spike to trigger a new spurious RTO as easily as the previous spurious RTO was triggered. Kojo/Yamamoto/Hata/Sarolahti Section 2.4. [Page 6]
INTERNET-DRAFT Expires: May 2008 November 2007 3. Advantages and Motivation 3.1. Avoiding Unnecessary Retransmissions If the TCP sender employs F-RTO, it is able to detect spurious RTOs. When F-RTO detects a spurious RTO, it retransmits only one segment unnecessarily (the first unacknowledged segment) and continues by transmitting new segments. 3.2. Adhering to the Packet Conservation Principle If the TCP sender employs F-RTO, it is able to detect spurious RTOs and avoid the unnecessary retransmission of the whole window of data. The amount of data that the TCP sender employing F-RTO transmits during the next RTT after detecting a spurious RTO depends on the congestion control response that the TCP sender follows. Whichever response algorithm is selected, the segments clocked out by the late acknowledgements must not be transmitted in slow start, unless the TCP sender was in slow start right before the spurious RTO occurred and the RTO recovery was entered. Otherwise, the late acknowledgements would clock out the segments at higher than accepted rate as discussed in Section 2.2 and the TCP sender would not adhere to the packet conservation principle. 3.3. Selecting an Appropriate Congestion Control Response If the F-RTO algorithm detects that the RTO was spurious, the TCP sender may revert the congestion control state back to the same state as it was right before the RTO occurred. One possible option is to restore the congestion window and slow-start threshold [LG04]. This would result in transmitting at the same rate as before the RTO, avoiding the performance penalty of unnecessarily reducing the congestion window and slow-start threshold. However, reverting the congestion control parameters might not be a safe response in all occasions. For example, a spurious RTO may occur due to a make- before-break vertical handover [MK04] from a low latency path to a high latency path [HC05, DK06]. If the handover results in a spurious RTO and the bottleneck link bandwidth-delay product with the new path after the handover is smaller than with the old path, restoring the congestion window is likely to result in congestion on the new bottleneck link. The TCP sender may select to take a conservative congestion control response after detecting a spurious RTO. The original F-RTO algorithm employed a conservative response algorithm after a Kojo/Yamamoto/Hata/Sarolahti Section 3.3. [Page 7]
INTERNET-DRAFT Expires: May 2008 November 2007 spurious RTO was detected [SKR03]. That is, the TCP sender sets the congestion window and slow-start threshold to half of the flight size right before the spurious RTO occurred and continues transmitting new data in congestion avoidance. This approach is always a safe response as the TCP sender halves its transmission rate, thereby taking the spurious RTO as a congestion signal. 3.4. Other Advantages If the F-RTO algorithm declares that an RTO was spuriously triggered, it may take the RTT for the delayed segments into account when calculating the RTO estimate, except for the segment that was retransmitted upon the retransmission timer expiration. This alone may help in avoiding further spurious RTOs. However, with the capability of detecting spurious RTOs the TCP sender may adjust the RTO estimate explicitly in order to avoid entering loss recovery unnecessarily in the later phases of the connection [BBA06]. 3.5. Non-spurious RTOs and Undetected Spurious RTOs If the retransmission timeout is not spurious or the F-RTO algorithm is not able to detect the spurious timeout, it reverts back to the conventional RTO recovery and continues retransmitting segments in slow-start. Two different cases with slightly different behavior can be observed: (i) if the first ACK arriving after the retransmission timer expired is a duplicate acknowledgement, the F-RTO sender declares the RTO genuine and reverts back to the conventional RTO recovery. (ii) if the first ACK arriving after the retransmission timer expired acknowledges new data, the F-RTO sender sends two previously unsent segments. Now, if the next ACK is a duplicate ACK, the F-RTO sender declares the RTO genuine and reverts to the conventional RTO recovery. In the first case, the behavior is identical to the behavior of the conventional RTO recovery. In the second case, the behavior is similar to the conventional RTO recovery with the only difference that the 2nd and 3rd segment sent after the RTO are new segments. When compared to a regular TCP implementation, the use of the F-RTO algorithm does not change the transmission rate of segments in the cases where the RTO is not declared spurious. Therefore, from the congestion control point of view the F-RTO algorithm can be seen to be safe also in these cases. Kojo/Yamamoto/Hata/Sarolahti Section 3.5. [Page 8]
INTERNET-DRAFT Expires: May 2008 November 2007 4. Experimental Results Additional material, such as the cited papers with the F-RTO experimentation results, can be found at [http://www.iki.fi/pasi.sarolahti/frto/]. 4.1. Initial trials in an emulated network The basic F-RTO algorithm was first introduced in [SKR03]. F-RTO performance was experimented in a simple emulated network environment with a slow bottleneck link that was typical to the wireless environments at the time of conducting the analysis. The original conservative F-RTO congestion control response (see Section 3.3) was used. The paper analyzed different scenarios that trigger a retransmission timeout either spuriously or genuinely. The following scenarios were investigated: i) delay spike that triggers a spurious timeout, ii) lost retransmission, iii) loss burst of entire window of data. The paper also discussed a packet reordering scenario, although experiments with packet reordering were not conducted. In the delay spike scenario F-RTO significantly reduced the number of unnecessary retransmissions and also improved the data throughput. In the other cases use of F-RTO did not affect TCP performance negatively, and did not cause any additional traffic to be sent into the network. SACK-enhanced F-RTO with different congestion control response algorithms was evaluated in [Sar03]. Because the cases where duplicate ACKs interact with spurious timeout detection were relatively rare in practice, in many cases the basic F-RTO performed equally well with the SACK-enhanced F-RTO. 4.2. F-RTO Performance over Commercial W-CDMA Networks Experimentation on F-RTO performance over commercial W-CDMA networks and in a test environment which emulates HSDPA (High Speed Downlink Packet Access) networks has been reported in [Yam05, Hok05]. In the experimentation over the commercial networks, we downloaded data objects from a test server in the Internet through the W-CDMA mobile communications networks. The F-RTO detection algorithm with the Eifel response algorithm was implemented on the test server, HP- UX 11i prototype. The commercial W-CDMA networks provide a maximum bearer rate of 384 kbps in a downlink and 64 kbps in an uplink. A mobile client downloaded data objects of varying size from the Kojo/Yamamoto/Hata/Sarolahti Section 4.2. [Page 9]
INTERNET-DRAFT Expires: May 2008 November 2007 server in five different situations; fixed point (good and bad wireless conditions), low speed (pedestrian), medium speed (driving by car in an urban area), and high speed (a bullet train). The object sizes were set to 6 Kbytes, 18 Kbytes, 300 Kbytes, 2 Mbytes, and 518 Mbytes (the object size of 518 Mbytes was used only for a bullet train). The experimentation took two weeks collecting performance data for 643 connections with F-RTO and 991 connections without F-RTO. In this experimentation, F-RTO reduced the amount of unnecessarily retransmitted data by 82 percent compared to the connections without F-RTO. Because the spurious RTOs did not occur very often, a relatively large amount of data was sent in total compared to the amount of unnecessarily retransmitted data. Therefore, just avoiding the unnecessary retransmissions did not improve TCP performance significantly. Throughput was improved primarily because F-RTO was used with the Eifel response algorithm that fully reverts the congestion control state to the state valid prior to the spurious retransmission timeout. F-RTO with the Eifel response improved throughput by 6 percent for connections that transferred at least 2 Mbytes and experienced spurious timeout. The network used for the experimentation has a small bandwidth-delay product around ten segments. A larger improvement in throughput is expected in networks with high bandwidth-delay product such as HSDPA networks. There are a few situations in which F-RTO cannot detect a spurious timeout such as severe reordering or duplication occurring on the segment that triggered the spurious timeout, if the sender has no new data to send, or the advertised window does not allow to send new data that is needed by F-RTO to detect the spurious timeout. In the experimentation, F-RTO was able detect 71 percent of spurious timeouts successfully. 28 percent of the spurious timeouts could not be detected by F-RTO because the sender had already sent the FIN segment and had no new data to send when the spurious timeout occurred. 0.7 percent of the spurious timeouts could not be detected because the advertised window prohibited transmitting new data and 0.3 percent because the sender received duplicate acknowledgements after the spurious timeout. The throughput of F-RTO with Eifel response was also evaluated in the test environment that emulated HSDPA networks. The test network has 14 Mbps bearer rate and 300 ms round-trip time, which yields the bandwidth-delay product of about 350 segments with the segment size of 1460 bytes. To trigger a spurious timeout, acknowledgements from the server to the client were delayed intentionally in the early and middle phase of the initial slow start and after the congestion window reached the maximum window size (i.e., in the steady state). F-RTO with Eifel response improved the throughput by 262 percent, 92 Kojo/Yamamoto/Hata/Sarolahti Section 4.2. [Page 10]
INTERNET-DRAFT Expires: May 2008 November 2007 percent, and 37 percent when a spurious timeout occurred in the early slow-start phase, in the middle of the slow start phase, and after reaching the steady state, respectively. The results show that F-RTO with Eifel response improves the throughput significantly in networks with large bandwidth-delay product. 4.3. Impact of Malicious Receiver on Network and Regular TCP Connection As discussed later in section 5.3, with F-RTO a receiver could mislead the sender to declare an RTO spurious even though it was caused due to a lost segment . This impact on networks and regular TCP connections was evaluated using computer simulation. There, two types of conservative response algorithms and a response algorithm that reverts the congestion control state back to the same state as it was right before the RTO occurred are examined. The conservative response algorithms examined reduce the slow start threshold to half of the flight size right before the spurious RTO occurred and the congestion window to one segment like slow start or to the half like fast recovery. The simulation results show that with the conservative response algorithms, the malicious receiver obtains no higher throughput than the regular TCP connection sharing the network bandwidth, so there is no incentive for the malicious receivers to mislead the sender to declare a genuine retransmission timeout spurious. On the other hand, when an aggressive response algorithm is used, there are some situations that the malicious receiver can obtain more bandwidth compared to the regular TCP connection. 5. Hidden Packet Losses There are a few known scenarios where a packet loss could escape F- RTO's notice and cause a false positive detection. These scenarios could be split into two cases: scenarios with a legitime receiver where TCP communication is unaffected, and scenarios with misbehaving receiver. In the first case the hidden packet loss is harmless, if the congestion control response to spurious timeout is conservative enough. The second case requires receiver misbehavior by acknowledging segments that have not been received or by delaying the acknowledgements, and it is not beneficial to the receiver because, as a result, the TCP connection may become unreliable or useless, or the malicious receiver may compromise the performance of the TCP loss recovery in order to mislead the F-RTO sender. We also note that optimistically acknowledging segments that have not yet been received is possible with any regular TCP implementation, and if the receiver's motivation was to damage the TCP connection (for Kojo/Yamamoto/Hata/Sarolahti Section 5. [Page 11]
INTERNET-DRAFT Expires: May 2008 November 2007 example, as a part of some kind of denial-of-service effort), the standard TCP offers easier ways of doing that. Next we will discuss these cases in more detail. 5.1. Loss of Retransmitted Segments RFC 4138 notes that when the timeout is declared spurious, the TCP sender cannot detect whether the unnecessary RTO retransmission was lost. In principle, the loss of the RTO retransmission should be taken as a congestion signal. Thus, there is a small possibility that the F-RTO sender will violate the congestion control rules, if it chooses to fully revert congestion control parameters after detecting a spurious timeout. The Eifel detection algorithm [RFC3522] has a similar property, while the DSACK option can be used to detect whether the retransmitted segment was successfully delivered to the receiver [RFC3708]. This behavior belongs to the first class of the above-mentioned cases; the loss of the RTO retransmission does not harm the TCP connection in any way, because the original segment has reached the receiver. With a conservative enough congestion control response this behavior is not harmful to the network, either. 5.2. Reordering F-RTO can declare a timeout spurious unintentionally when there is reordering between the retransmitted segment and the original segments transmitted before the timeout so that the RTO retransmission is acknowledged before the full window of original transmissions. This could happen, for example, in the case when an original segment is lost on a high-latency connection path, and the RTO retransmission of that segment traverses through a different path that has substantially lower round-trip delay. This might sound a pathological scenario, but could occur on a multi-radio device that is performing a vertical handover between a high-latency WWAN link and a low-latency WLAN link. Also this scenario belongs to the first class of the above-mentioned cases, as it is not harmful to the network if the congestion control response to spurious retransmission timeout is conservative enough. We believe that in practice this kind of combination of loss, delay and reordering is very rare. In addition, this kind of a reordering is less likely to occur with large TCP windows with which the effect of a non-conservative response could be detectable. Kojo/Yamamoto/Hata/Sarolahti Section 5.2. [Page 12]
INTERNET-DRAFT Expires: May 2008 November 2007 5.3. Malicious Receiver RFC 4138 notes in its security considerations that with F-RTO the receiver could mislead the sender into falsely declaring the RTO spurious. There are two possible ways a malicious receiver could trigger a wrong output from the F-RTO algorithm. First, the receiver can acknowledge data that it has not received so that the acknowledgement arrives at the sender after the retransmission timeout. Second, it can delay acknowledgments for segments it has received earlier and acknowledge the outstanding segments after the retransmission timer has expired and the retransmitted segment has arrived, deluding the sender to declare the timeout spurious. If the TCP receiver acknowledges a segment it has not really received, the sender can be led to declare the timeout spurious in the F-RTO algorithm, step 3. However, by doing so the receiver risks the correct behavior of the connection. If both the original transmission and the retransmission of the segment are dropped, the sender incorrectly thinks that the lost segment has been delivered to the receiver being not able to retransmit the segment again. As a result, the TCP connection is unable to proceed unless the receiver delivers the data out-of-order to the application, making the data delivery of the connection unreliable. In addition, this requires that the receiver transmits the false ACK timely such that the ACK does not arrive at the sender until the retransmission timer has expired and that the receiver suppresses any duplicate ACKs in order to prevent the sender from entering the fast retransmit and fast recovery. Therefore, we believe that this kind of attack is very hard to implement succesfully and a malicious receiver is unlikely to get any benefit from this attack, and with an appropriate response this attack is not harmful to the network, either. If the TCP receiver delays the acknowledgements of the out-of-order segments after detecting a hole in the sequence space and waits for the retransmission timer to expire and the retransmitted segment to arrive before it acknowledges the segments with cumulative acknowledgements, it may make the F-RTO sender to walk through the algorithm steps so that the timeout seems spurious when it should have been genuine. We believe this kind of attack is difficult to implement in practice, and it is likely to be of no benefit to the receiver as it needs to force the sender to wait for an RTO to recover each of the lost segments while loss recovery with fast retransmit and fast recovery is likely to be much more efficient. In addition, this approach does not work if consecutive segments are lost unless the receiver acknowledges data that it has not received. If a response algorithm that restores the congestion window and the slow start threshold is used, there are some potential situations that the malicious receiver obtains the higher throughput than the Kojo/Yamamoto/Hata/Sarolahti Section 5.3. [Page 13]
INTERNET-DRAFT Expires: May 2008 November 2007 regular TCP does. However, with a conservative response to the spurious timeout, this attack is of no benefit to the receiver and it is not harmful to the network, either. A study with evaluation results of the impact of the malicious receivers can be found at [http://www.iki.fi/pasi.sarolahti/frto/] 6. Conclusions and Recommendations This document analyzed the possible benefits and disadvantages of using F-RTO enhanced TCP, if it was deployed globally. When a spurious retransmission timeout occurs, the regular RTO recovery wastes the network resources by retransmitting the whole window of data unnecessarily. By doing it, a regular TCP also violates the packet conservation principle and is thus harmful for congestion control, despite following the letters of the specifications. As a result of spurious timeout, the regular RTO recovery transmits 1.5 times more data than what is allowed by the congestion window at the time the spurious timeout occurred and imposes excessive load on the network. F-RTO is able to avoid these unnecessary retransmissions by detecting a spurious timeout and not retransmitting segments unnecessarily. When the spurious retransmission timeout has been detected by F-RTO, the F-RTO sender with an appropriate response algorithm adheres to the packet conservation principle, because it does not transmit more segments than what have left the network. Therefore, a successful detection of a spurious retransmission timeout with F-RTO can result both in reduced load on the network and improved TCP throughput. These factors are especially important in wireless communication. There is one well-known scenario where a spurious timeout hides a packet loss with F-RTO: if the RTO retransmission is lost, a F-RTO sender cannot detect the segment loss. This is common to all currently known mechanisms for detecting spurious retransmission timeout immediately after it has occurred. Missing one packet loss event is not a problem, if the response algorithm is conservative enough. DSACK, that is able to detect spurious timeout after a full window of data has been unnecessarily retransmitted, does not have this problem, but on the other hand, DSACK is not able to avoid the unnecessary retransmissions and the consequent violation of the packet conservation principle. There are two known ways a misbehaving TCP receiver could cheat the F-RTO algorithm: (i) after detecting a packet loss, the receiver Kojo/Yamamoto/Hata/Sarolahti Section 6. [Page 14]
INTERNET-DRAFT Expires: May 2008 November 2007 could delay acknowledging the following segments until a retransmission timer expires and the retransmitted segment arrives and then acknowledge the outstanding data, making the timeout seem spurious to F-RTO. (ii) after F-RTO algorithm has been triggered, the receiver could optimistically acknowledge segments that have been lost and make the RTO seem spurious to F-RTO. In the latter case the penalty to the connection is significant because the control data at the TCP sender may go into an invalid state, causing the TCP connection to be unusable. Furthermore, also with the regular TCP algorithms the receiver can acknowledge unreceived segments before they arrive in the hope of gaining more performance, with the risk of invalidating the TCP state at the sender and making the connection unusable. If the response to a spurious retransmission timeout is conservative enough, a misbehaving receiver cannot cause extensive congestion to the network in either of these cases. Given the above presented benefits and disadvantages, we believe F- RTO [RFC4138] is a safe algorithm to be moved on to Proposed Standard, and to be deployed globally in the Internet with the following notes: * Because F-RTO performance with SCTP has not been studied to a significant extent, we propose that the revised version of RFC 4138 would not include discussion on SCTP. However, the authors would like to encourage future experimentations with F-RTO and SCTP, applying RFC 4138. * Because it is useful to keep the spurious timeout detection and response specifications separate, the authors would like to enable an usage of the F-RTO algorithm that allows detecting a spurious timeout without applying any specific response algorithm, i.e., allowing the TCP sender to continue transmitting new data with a conservative congestion control response. In other words, after detecting a spurious retransmission timeout, the TCP sender would take the spurious timeout as a congestion signal and reduce the congestion window and slow-start threshold. References [BBA06] J. Blanton, E. Blanton, and M. Allman. Using Spurious Retransmissions to Adapt the Retransmission Timeout. Internet-Draft "draft-allman-rto-backoff-04.txt", December 2006. Work in progress. [DK06] L. Daniel and M. Kojo. "Adapting TCP for Vertical Handoffs in Kojo/Yamamoto/Hata/Sarolahti [Page 15]
INTERNET-DRAFT Expires: May 2008 November 2007 Wireless Networks". In Proc. 31st IEEE Conference on Local Computer Networks (LCN), Tampa, FL, USA, November 15-16, 2006. [Jac88] Jacobson, V., "Congestion Avoidance and Control", In Proceedings of ACM SIGCOMM 88. [HC05] H. Huang and J. Cai. Improving TCP Performance during Soft Vertical Handoff. In Proc. 19th International Conference on Advanced Information Networking and Applications (AINA'05), volume 2, pages 329-332, Mar. 2005. [Hok05] A. Hokamura, et al. "Performance Evaluation of F-RTO and Eifel Response Algorithms over W-CDMA packet network". Wireless Personal Multimedia Communications (WPMC'05), Sept. 2005. [KP87] Karn, P. and C. Partridge, "Improving Round-Trip Time Estimates in Reliable Transport Protocols", In Proceedings of ACM SIGCOMM 87. [LG04] Ludwig, R. and A. Gurtov, "The Eifel Response Algorithm for TCP", RFC 4015, February 2005. [MK04] J. Manner and M Kojo, Mobility Related Terminology. RFC 3753, June 2004. [RFC793] J. Postel. Transmission Control Protocol. RFC 793, September 1981. [RFC2119] S. Bradner. Key words for use in RFCs to Indicate Requirement Levels. BCP 14, RFC 2119, March 1997. [RFC3522] R. Ludwig and M. Meyer, The Eifel Detection Algorithm for TCP. RFC 3522, April 2003. [RFC3708] E. Blanton and M. Allman, Using TCP Duplicate Selective Acknowledgement (DSACKs) and Stream Control Transmission Protocol (SCTP) Duplicate Transmission Sequence Numbers (TSNs) to Detect Spurious Retransmissions, RFC 3708, February 2004. [RFC4138] P. Sarolahti and M. Kojo. Forward RTO-Recovery (F-RTO): An Algorithm for Detecting Spurious Retransmission Timeouts with TCP and the Stream Control Transmission Protocol (SCTP), RFC 4138, August 2005. [SKR03] P. Sarolahti, M. Kojo, and K. Raatikainen. F-RTO: An Enhanced Recovery Algorithm for TCP Retransmission Timeouts. In ACM SIGCOMM Computer Communication Review, 33(2), April 2003 Kojo/Yamamoto/Hata/Sarolahti [Page 16]
INTERNET-DRAFT Expires: May 2008 November 2007 [Sar03] P. Sarolahti. Congestion Control on Spurious TCP Retransmission Timeouts. In Proceedings of IEEE Globecom 2003, San Francisco, CA, USA, December 2003. [Yam05] K. Yamamoto, et al. "Effects of F-RTO and Eifel Response Algorithms for W-CDMA and HSDPA networks". Wireless Personal Multimedia Communications (WPMC'05), Sept. 2005. [Zh86] Zhang, L., "Why TCP Timers Don't Work Well", In Proceedings of ACM SIGCOMM 86. AUTHORS' ADDRESSES Markku Kojo University of Helsinki P.O. Box 68 FI-00014 UNIVERSITY OF HELSINKI Finland Email: kojo@cs.helsinki.fi Kazunori Yamamoto NTT Docomo, Inc. 3-5 Hikarinooka, Yokosuka, Kanagawa, 239-8536, Japan Phone: +81-46-840-3812 Email: yamamotokaz@nttdocomo.co.jp Max Hata NTT Docomo, Inc. 3-5 Hikarinooka, Yokosuka, Kanagawa, 239-8536, Japan Phone: +81-46-840-3812 Email: hatama@s1.nttdocomo.co.jp Pasi Sarolahti Nokia Research Center P.O. Box 407 FI-00045 NOKIA GROUP Finland Phone: +358 50 4876607 Email: pasi.sarolahti@nokia.com Kojo/Yamamoto/Hata/Sarolahti [Page 17]
INTERNET-DRAFT Expires: May 2008 November 2007 Full Copyright Statement Copyright (C) The IETF Trust (2007). 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. 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, THE IETF TRUST 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. Intellectual Property 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. Kojo/Yamamoto/Hata/Sarolahti [Page 18]