idnits 2.17.1 draft-tsvwg-quic-loss-recovery-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (December 18, 2015) is 3049 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'RFC2119' is defined on line 345, but no explicit reference was found in the text Summary: 2 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group J. Iyengar 3 Internet-Draft I. Swett 4 Intended status: Informational Google 5 Expires: June 20, 2016 December 18, 2015 7 QUIC Loss Recovery And Congestion Control 8 draft-tsvwg-quic-loss-recovery-01 10 Abstract 12 QUIC (Quick UDP Internet Connection) is a new multiplexed and secure 13 transport atop UDP, designed from the ground up and optimized for 14 HTTP/2 semantics. While built with HTTP/2 as the primary application 15 protocol, QUIC builds on decades of transport and security 16 experience, and implements mechanisms that make it attractive as a 17 modern general-purpose transport. QUIC implements the spirit of 18 known TCP loss recovery mechanisms, described in RFCs, various 19 Internet-drafts, and also those prevalent in the Linux TCP 20 implementation. This document describes QUIC loss recovery, and 21 where applicable, attributes the TCP equivalent in RFCs, Internet- 22 drafts, academic papers, and/or TCP implementations. 24 Status of This Memo 26 This Internet-Draft is submitted in full conformance with the 27 provisions of BCP 78 and BCP 79. 29 Internet-Drafts are working documents of the Internet Engineering 30 Task Force (IETF). Note that other groups may also distribute 31 working documents as Internet-Drafts. The list of current Internet- 32 Drafts is at http://datatracker.ietf.org/drafts/current/. 34 Internet-Drafts are draft documents valid for a maximum of six months 35 and may be updated, replaced, or obsoleted by other documents at any 36 time. It is inappropriate to use Internet-Drafts as reference 37 material or to cite them other than as "work in progress." 39 This Internet-Draft will expire on June 20, 2016. 41 Copyright Notice 43 Copyright (c) 2015 IETF Trust and the persons identified as the 44 document authors. All rights reserved. 46 This document is subject to BCP 78 and the IETF Trust's Legal 47 Provisions Relating to IETF Documents 48 (http://trustee.ietf.org/license-info) in effect on the date of 49 publication of this document. Please review these documents 50 carefully, as they describe your rights and restrictions with respect 51 to this document. Code Components extracted from this document must 52 include Simplified BSD License text as described in Section 4.e of 53 the Trust Legal Provisions and are provided without warranty as 54 described in the Simplified BSD License. 56 1. Introduction 58 QUIC (Quick UDP Internet Connection) is a new multiplexed and secure 59 transport atop UDP, designed from the ground up and optimized for 60 HTTP/2 semantics. While built with HTTP/2 as the primary application 61 protocol, QUIC builds on decades of transport and security 62 experience, and implements mechanisms that make it attractive as a 63 modern general-purpose transport. The QUIC protocol is described in 64 [draft-tsvwg-quic-protocol]. 66 QUIC implements the spirit of known TCP loss recovery mechanisms, 67 described in RFCs, various Internet-drafts, and also those prevalent 68 in the Linux TCP implementation. This document describes QUIC loss 69 recovery, and where applicable, attributes the TCP equivalent in 70 RFCs, Internet-drafts, academic papers, and/or TCP implementations. 72 This document first describes parts of the QUIC transmission 73 machinery that are necessary to describe the loss recovery 74 mechanisms. The document then describes QUIC's loss recovery, 75 followed by a list of the various TCP mechanisms that QUIC re- 76 interprets. 78 2. Design of the QUIC Transmission Machinery 80 All transmissions in QUIC are sent with a packet-level header, which 81 includes a packet sequence number(referred to below as a packet 82 number). These packet numbers never repeat in the lifetime of a 83 connection, and are monotonically increasing, which makes duplicate 84 detection trivial. This fundamental design decision obviates the 85 need for disambiguating between transmissions and retransmissions and 86 eliminates significant complexity from QUIC's interpretation of TCP 87 loss detection mechanisms. 89 Every packet can contain several frames; we outline the frames that 90 are important to the loss detection and congestion control machinery 91 below. 93 o STREAM frames contain application data. Crypto handshake data is 94 also sent as STREAM data, and uses the reliability machinery of 95 QUIC underneath. 97 o ACK frames contain acknowledgment information. QUIC uses a NACK- 98 based scheme, where the largest_observed packet number is 99 reported, and packets with sequence numbers lesser than the 100 largest_observed not yet seen are reported as NACK ranges. The 101 ACK frame also includes a receive timestamp for each packet newly 102 acked. 104 2.1. Relevant Differences Between QUIC and TCP 106 There are some notable differences between QUIC and TCP which are 107 important for reasoning about the differences between the loss 108 recovery mechanisms employed by the two protocols. We briefly 109 describe these differences below. 111 2.1.1. Monotonically Increasing Sequence Numbers 113 TCP conflates transmission sequence number at the sender with 114 delivery sequence number at the receiver, which results in 115 retransmissions of the same data carrying the same sequence number, 116 and consequently to problems caused by "retransmission ambiguity". 117 QUIC separates the two: QUIC uses a packet transmission number 118 (referred to as the "sequence number") for transmissions, and any 119 data that is to be delivered to the receiving application(s) is sent 120 in one or more streams, with stream offsets encoded within STREAM 121 frames inside of packets that determine delivery order. 123 QUIC's packet sequence number is strictly increasing, and directly 124 encodes transmission order. A higher QUIC sequence number signifies 125 that the packet was sent later, and a lower QUIC sequence number 126 signifies that the packet was sent earlier. 128 This design point significantly simplifies loss detection mechanisms 129 for QUIC. Most TCP mechanisms implicitly attempt to infer 130 transmission ordering based on the TCP sequence numbers; a non- 131 trivial task, especially when TCP timestamps are not available. 133 QUIC resends lost packets with new packet sequence numbers when 134 retransmission is necessary, removing ambiguity about which packet is 135 acknowledged when an ACK is received. Consequently, more accurate 136 RTT measurements can be made, spurious retransmissions are trivially 137 detected, and mechanisms such as Fast Retransmit can be applied 138 universally, based only on sequence number. 140 2.1.2. No SACK Reneging 142 QUIC ACKs contain information that is equivalent to TCP SACK, but 143 QUIC does not allow any acked packet to be reneged, greatly 144 simplifying implementations on both sides and reducing memory 145 pressure on the sender. 147 2.1.3. More NACK Ranges 149 QUIC supports up to 255 NACK ranges, opposed to TCP's 3 SACK ranges. 150 In high loss environments, this speeds recovery. 152 2.1.4. Explicit Correction For Delayed Acks 154 QUIC ACKs explicitly encode the delay incurred at the receiver 155 between when a packet is received and when the corresponding ACK is 156 sent. This allows the receiver of the ACK to adjust for receiver 157 delays, specifically the delayed ack timer, when estimating the path 158 RTT. This mechanism also allows a receiver to measure and report the 159 delay from when a packet was received by the OS kernel, which is 160 useful in receivers which may incur delays such as context-switch 161 latency before a userspace QUIC receiver processes a received packet. 163 3. An Overview of QUIC Loss Recovery 165 We briefly describe QUIC's actions on packet transmission, ack 166 reception, and timer expiration events. 168 3.1. On Sending a Packet 170 A retransmission timer may be set based on the mode: 172 o If the handshake has not completed, start a handshake timer. 174 * 1.5x the SRTT, with exponential backoff. 176 o If there are outstanding packets which have been NACKed, possibly 177 set the loss timer 179 * Depends on the loss detection implementation, default is 180 0.25RTT in the case of Early Retransmit. 182 o If fewer than 2 TLPs have been sent, compute and restart TLP 183 timer. 185 * Timer is set for max(10ms, 2*SRTT) if there are multiple 186 packets in flight 188 * Timer is set to max(1.5*SRTT + delayed ack timer, 2*SRTT) if 189 there is only one packet in flight. 191 o If 2 TLPs have been sent, set the RTO timer. 193 * Timer is set to max(200ms, SRTT+4*RTTVAR) with exponential 194 backoff after the first RTO. 196 3.2. On Receiving an ACK 198 The following steps are performed when an ACK is received: 200 o Validate the ack, including ignoring any out of order acks. 202 o Update RTT measurements. 204 o Sender marks unacked packets lower than the largest_observed and 205 not NACKed in this ACK frame as ACKED. 207 o Packets with packet number lesser than the largest_observed that 208 are NACKed have missing_reports incremented based on 209 FACK.(largest_observed - missing packet number) 211 o Threshold is set to 3 by default. 213 o Packets with missing_reports > threshold are marked for 214 retransmission. This logic implements Fast Retransmission and 215 FACK-based retransmission together. 217 o If nacked packets are outstanding and the largest observed is the 218 largest sent packet, the retransmission timer will be set to 219 0.25SRTT, implementing Early Retransmit with timer. 221 o Stop timers if no packets are outstanding. 223 3.3. On Timer Expiration 225 QUIC uses one loss recovery timer, which when set, can be in one of 226 several states. When the timer expires, the state determines the 227 action to be performed. (TODO: describe when the timers are set) 229 o Handshake state: 231 * Retransmit any outstanding handshake packets. 233 o Loss timer state: 235 * Lose the outstanding packets which have been NACKed so far. 237 * Report the loss to the congestion controller. 239 * Retransmit as many as the congestion controller allows. 241 o TLP state: 243 * Retransmit the smallest outstanding packet which is 244 retransmittable. 246 * Do not mark any packets as lost until an ACK arrives. 248 * Restart timer for a TLP or RTO. 250 o RTO state: 252 * Retransmit the two smallest outstanding packets which are 253 retransmittable. 255 * Do not collapse the congestion window (ie: set to 1 packet) 256 until an ack arrives and confirms that the RTO was not 257 spurious. Note that this step obviates the need to implement 258 FRTO. 260 * Restart the timer for next RTO (with exponential backoff.) 262 4. TCP mechanisms in QUIC 264 QUIC implements the spirit of a variety of RFCs, Internet drafts, and 265 other well-known TCP loss recovery mechanisms, though the 266 implementation details differ from the TCP implementations. 268 4.1. RFC 6298 (RTO computation) 270 QUIC calculates SRTT and RTTVAR according to the standard formulas. 271 An RTT sample is only taken if the delayed ack correction is smaller 272 than the measured RTT (otherwise a negative RTT would result), and 273 the ack's contains a new, larger largest observed packet number. 274 min_rtt is only based on the observed RTT, but SRTT uses the delayed 275 ack correction delta. 277 As described above, QUIC implements RTO with the standard timeout and 278 CWND reduction. However, QUIC retransmits the earliest outstanding 279 packets rather than the latest, because QUIC doesn't have 280 retransmission ambiguity. QUIC uses the commonly accepted min RTO of 281 200ms instead of the 1s the RFC specifies. 283 4.2. FACK Loss Recovery (paper) 285 QUIC implements the algorithm for early loss recovery described in 286 the FACK paper (and implemented in the Linux kernel.) QUIC uses the 287 packet sequence number to measure the FACK reordering threshold. 289 Currently QUIC does not implement an adaptive threshold as many TCP 290 implementations(ie: the Linux kernel) do. 292 4.3. RFC 3782, RFC 6582 (NewReno Fast Recovery) 294 QUIC only reduces its CWND once per congestion window, in keeping 295 with the NewReno RFC. It tracks the largest outstanding packet at 296 the time the loss is declared and any losses which occur before that 297 packet number are considered part of the same loss event. It's worth 298 noting that some TCP implementations may do this on a sequence number 299 basis, and hence consider multiple losses of the same packet a single 300 loss event. 302 4.4. TLP (draft) 304 QUIC always sends two tail loss probes before RTO is triggered. QUIC 305 invokes tail loss probe even when a loss is outstanding, which is 306 different than some TCP implementations. 308 4.5. RFC 5827 (Early Retransmit) with Delay Timer 310 QUIC implements early retransmit with a timer in order to minimize 311 spurious retransmits. The timer is set to 1/4 SRTT after the final 312 outstanding packet is acked. 314 4.6. RFC 5827 (F-RTO) 316 QUIC implements F-RTO by not reducing the CWND and SSThresh until a 317 subsequent ack is received and it's sure the RTO was not spurious. 318 Conceptually this is similar, but it makes for a much cleaner 319 implementation with fewer edge cases. 321 4.7. RFC 6937 (Proportional Rate Reduction) 323 PRR-SSRB is implemented by QUIC in the epoch when recovering from a 324 loss. 326 4.8. TCP Cubic (draft) with optional RFC 5681 (Reno) 328 TCP Cubic is the default congestion control algorithm in QUIC. Reno 329 is also an easily available option which may be requested via 330 connection options and is fully implemented. 332 4.9. Hybrid Slow Start (paper) 334 QUIC implements hybrid slow start, but disables ack train detection, 335 because it has shown to falsely trigger when coupled with packet 336 pacing, which is also on by default in QUIC. Currently the minimum 337 delay increase is 4ms, the maximum is 16ms, and within that range 338 QUIC exits slow start if the min_rtt within a round increases by more 339 than ⅛ of the connection min_rtt. 341 5. References 343 5.1. Normative References 345 [RFC2119] Bradner, S., "Key Words for use in RFCs to Indicate 346 Requirement Levels", March 1997. 348 5.2. Informative References 350 [draft-tsvwg-quic-protocol] 351 Hamilton, R., Iyengar, J., Swett, I., and A. Wilk, "QUIC: 352 A UDP-Based Secure and Reliable Transport For HTTP/2", 353 July 2015. 355 Authors' Addresses 357 Janardhan Iyengar 358 Google 360 Email: jri@google.com 362 Ian Swett 363 Google 365 Email: ianswett@google.com