RFC 9002 – QUIC Loss Detection and Congestion Control

1.Introduction

3.Design of the QUIC Transmission Machinery

QUIC packet中的帧类型影响着QUIC的丢包恢复和拥塞控制逻辑：

• All packets are acknowledged, though packets that contain no ack-eliciting frames are only acknowledged along with ack-eliciting packets.

所有的包都需要ack，除了那种只包含no ack-eliciting frames的包是由其他ack-eliciting packets触发ack的。

• Long header packets that contain CRYPTO frames are critical to the performance of the QUIC handshake and use shorter timers for acknowledgment.

带有长包头、带有CRYPTO frames的包对QUIC的握手性能至关重要，因此对这些包使用时间更短的ack timer。

• Packets containing frames besides ACK or CONNECTION_CLOSE frames count toward congestion control limits and are considered to be in flight.

包含了除ACK/CONNECTION_CLOSE frames之外的frame的包，要受拥塞算法的控制，并且算到inflight里去。

• Packets containing frames besides ACK or CONNECTION_CLOSE frames count toward congestion control limits and are considered to be in flight.

PADDING frames要算到inflight里，但是不出触发ack的发送。

4.QUIC与TCP的不同之处

1.不同的packet number spaces

QUIC uses separate packet number spaces for each encryption level, except 0-RTT and all generations of 1-RTT keys use the same packet number space.

不同加密级别的包的packet number所处的packet number space不一样，保证了不同加密级别的包不会被混淆导致伪重传。不过RTT的测量是不区分packet number space的。

2.单调递增的packet numbers

QUIC将delivery order和transmission order区分开来，避免了TCP不能区分原始包和重传包的问题。transmission order通过packet number确定，delivery order通过STREAM frames中的stream offset确定。这种设计避免了伪重传问题的发生，同时可以获得一个更加精确的RTT。

3.Clearer Loss Epoch

QUIC的loss epoch计算方式：丢包时触发并标记loss epoch开始，收到loss epoch开始之后发出去的包的ack时标记这个loss epoch结束。

TCP的loss epoch计算方式：要等丢的包成功重传(收到ack)才算结束。

QUIC的一个Loss Epoch持续大约一个round，而TCP的Loss epoch可能持续多个round，因为一个包可能需要重传多次才能被成功发到对端。

TCP和QUIC都需要在遇到Loss Epoch时减少拥塞窗口，由于Loss Epoch的机制不同，QUIC大约在丢包的每个round进行一次减少拥塞窗口的操作，而TCP则可能是多个round才执行一次减少拥塞窗口的操作。

4.No Reneging

QUIC支持类似SACK的机制，但是不支持reneging，这样可以简化双端的实现和减小发送端的内存压力。

5.More ACK Ranges

TCP SACK由于TCP选项长度的限制只能包含最多3个range，而QUIC的ack包不受此限制，因此可以包含更多range。

6.Explicit Correction for Delayed Acknowledgements

QUIC接收端会计算ack delay时间，发送端可以通过减去这个ack delay时间算出一个更准确的RTT。

7.Probe Timeout Replaces RTO and TLP

QUIC用PTO替代了RTO和TLP。相较于RTO，QUIC的优势在于将对端可能出现的最大ack delay考虑了进来，而不是使用一个固定的timeout值。

相较于TLP，QUIC在触发PTO时，不会collapse congestion window，避免了非必须的congestion window reduction，当然和TCP相比是更激进了。

在PTO timer触发时，QUIC是可以临时允许probe packets超出congestion window限制的。

8.The Minimum Congestion Window Is Two Packets

TCP设置拥塞窗口最小为1个包。如果这个包丢失了，那么发端需要等待1个PTO(Probe Timeout)的时间去触发重传。拥塞窗口为1个包也更容易触发接收端delay ack的逻辑。

所以QUIC将这个下限改为了2个包。虽然这可能增加网络负载，但是在persistent congestion场景下，QUIC会指数降低其发送速率。

9.Handshake Packets Are Not Special

TCP中，SYN和SYN-ACK包是被特殊对待的，RFC5681：

SYN和SYN-ACK包的ack是禁止触发拥塞窗口的增加的，同时如果SYN或者SYN-ACK包丢了，那么初始发送窗口必须被设置为1个包(1 SMSS)。

QUIC中，SYN、SYN-ACK包被当作普通的带有握手数据的包。

5.Estimating the Round-Trip Time

对每一条path，QUIC通过接收时间减去发送时间和对端上报的ack delay得到RTT采样值，并维护3个关于rtt的值：min_rtt(minimum value over a period of time)，smoothed_rtt(exponentially weighted moving average)，rttvar(the mean deviation)。

5.1Generating RTT Samples

An endpoint generates an RTT sample on receiving an ACK frame that meets the following two conditions:¶

• the largest acknowledged packet number is newly acknowledged, and¶
• at least one of the newly acknowledged packets was ack-eliciting.

能生成RTT采样的ACK frame必须满足两个条件：

• 该ACK frame更新了largest acked packet number；
• 该ACK frame至少ack了一个ack-eliciting 包。

计算公式：larget_rtt = ack_time – sent_time_of_largest_acked

这里的largest_rtt意思是使用该ACK frame更新后的largest acked packet number这个包的发送、ack时间来计算rtt，而不是说这样算出来的rtt有”最大”的意味。因为对端上报的ack delay值是基于这个largest acked packet number对应的包计算的，所以计算RTT采样值是需要用这个包来计算。

从公式来看，ack delay没有直接参与RTT采样值的计算，也没有用在min_rtt的计算中，而是用在了smoothed_rtt和rttvar的计算中。

5.2Estimating min_rtt

min_rtt计算是不考虑ack delay的影响的，min_rtt提供了一个smoothed_rtt的计算结果的下限。

在遇到persistent congestion时，min_rtt需要更新为最新RTT采样值，并且smoothed_rtt也要重新估算。

5.3Estimating smoothed_rtt and rttvar

计算smoothed_rtt时，RTT采样值是要扣除ack delay的。

在握手完成前，对端上报的ack delay可能超出对端的max_ack_delay这个值，因此在握手完成前可以忽略max_ack_delay这个值(因为握手阶段可能计算量大导致对端的ack delay大，但是握手完成后这种问题就应该不存在了)。

总之握手完成前，ack delay的值是需要特殊处理的，如果握手完成前对端上报的ack delay导致算出来的RTT比min_rtt还小，是可以忽略掉这种RTT采样值的。

握手完成后，ack delay应该取min(ack_delay，max_ack_delay)，如果扣掉min(ack_delay, max_ack_delay)后，RTT的值比min_rtt还小了，那么这个RTT采样值就不应该扣除ack delay，而是直接参与smoothed_rtt的计算。

在某些情况下，发送端收到ack后也不是立即处理这个ack的，比如文档中讲的0-RTT情况，发送端不能立即解密收到的ack，这个时候计算smoothed_rtt要把这个不能解密导致的延迟也给扣除掉。

smoothed_rtt和rttvar的更新过程

1.连接开始或连接迁移后：

smoothed_rtt = kInitialRtt

rttvar = kInitialRtt / 2

2.得到第一个RTT sample后：

smoothed_rtt = latest_rtt

rttvar = latest_rtt / 2

3.接下来smoothed_rtt和rttvar的演化过程：

ack_delay = decoded acknowledgment delay from ACK frame

if (handshake confirmed):

  ack_delay = min(ack_delay, max_ack_delay)

adjusted_rtt = latest_rtt

if (latest_rtt >= min_rtt + ack_delay):

  adjusted_rtt = latest_rtt – ack_delay

smoothed_rtt = 7/8 * smoothed_rtt + 1/8 * adjusted_rtt

rttvar_sample = abs(smoothed_rtt – adjusted_rtt)

rttvar = 3/4 * rttvar + 1/4 * rttvar_sample

6.Loss Detection

QUIC通过ack来检测丢包，通过PTO来确保ack被收到。遇到丢包时，QUIC可以选择重传、sending an updated frame，or discarding the frame 3种应对方法。

丢包检测/PTO是在每个packet number space里分别进行的。

6.1 Acknowledgement-Based Detection

QUIC的acknowledged-based detection实现了TCP中的5种算法：

1. Fast Retransmit
2. Early Retransmit
3. Forward Acknowledgement
4. SACK loss recovery
5. RACK-TLP

判断一个包丢失的条件(必须同时满足)：

• The packet is unacknowledged, in flight, and was sent prior to an acknowledged packet.¶
• The packet was sent kPacketThreshold packets before an acknowledged packet (Section 6.1.1), or it was sent long enough in the past (Section 6.1.2).

第二点中的time threshold和packet threshold是为了容忍一定程度的乱序。具体的QUIC实现可以设计自适应调整的time threshold和packet threshold来减少丢包误判。

6.1.1 Packet Threshold

推荐的乱序阈值kPacketThreshold是3，具体的QUIC实现不应该将这个阈值设置为比3更小的值。因为QUIC的包是加密的，中间设备不能根据QUIC连接的packet number去调整QUIC包的顺序，所以网络中QUIC的乱序概率可能比TCP大。RACK算法被用在TCP中减少乱序导致的丢包误判，并且预计在QUIC中也可以发挥相同作用。

6.1.2 Time Threshold

收到一个包的ack后，从收到ack这个时刻算起，Time Threshold之前发送的包应该标记为丢包，Time Threshold的计算方式：

max(kTimeThreshold * max(smoothed_rtt, latest_rtt), kGranularity)

如果有比largest_ack_number更早的包没有被标记为丢失，那么应该设置一个时限为剩余时间(Time Threshold减去这个包已经发出去的时间)的timer来检测丢包。注意这里说的是在largest_ack_number之前发出去的包才可以用这个time threshold来检测丢包。对于larget_ack_number之后的包这个time threshold不适用，而是应该用PTO去触发对端回新的ack，然后基于新的ack再用packet threshold和time threshold机制来检测丢包。

kTimeThreshold的推荐值为9/8，kGranularity的推荐值为1ms。

小的TimeThreshold会导致更多丢包误判，而大的TimeThreshold则增加了丢包检测的延时。

6.2 Probe Timeout

当ack-eliciting packets没有在期望时间内返回ack或者server没有validate对端地址时，Probe Timeout(PTO)会触发发送一个或两个probe datagram给对端。

PTO不是用来检测丢包的，而且也禁止因为PTO的触发将未被ack的包标记为丢包。PTO的作用是解决尾丢包问题：

A PTO enables a connection to recover from loss of tail packets or acknowledgments.

Probe Timeout是在每个packet number space里单独算，但是只有一个Probe Timeout的定时器。

6.2.1 Computing PTO

当一个ack-eliciting packet发出去后，发端为其设置一个PTO timer：

PTO = smoothed_rtt + max(4*rttvar, kGranularity) + max_ack_delay

对于Initial or Handshake packet number spaces，ma_ack_delay的取值设置为0，因为对端不应该delay这种包的ack的发送。

When ack-eliciting packets in multiple packet number spaces are in flight, the timer MUST be set to the earlier value of the Initial and Handshake packet number spaces.

如果有多个packet number space的包处于inflight状态，PTO定时器必须设置为Initial and Handshake packet number spaces之中的较小值。

在握手完成前，禁止为Application Data packet number space的包设置PTO timer，因为握手都未完成，发端和收端都不一定能够正常解密收到的包，此时需要避免重传这些可能不能解密的数据。

遇到以下情况，需要重启PTO timer：

• 发出ack-eliciting包或者收到ack-eliciting包的ack
• Initial or Handshake keys are discarded

PTO timer触发时需要应用一个指数退避算法，每次PTO timer触发时，PTO timer的值需要加倍，而当收到ack时，这个指数退避的系数重置为1。但是对于Initial packets，收到的ack是不重置backoff factor的。

PTO连续触发时，其总时间受限于连接的idle timeout(因为直接判断为断连接了)。

存在time threshold的timer时禁止设置PTO timer。

6.2.2 Handshakes and New Paths

断连恢复的连接可以使用之前的smoothed_rtt作为initial RTT。如果之前没有RTT采样，initial RTT应该被设置为333ms，这使得握手阶段的PTO从1s开始，与TCP的initial RTO一致。

连接也可以用发送PATH_CHALLENGE和收到PATH_RESPONSE之间的延迟作为new path的initial RTT，但是这个延迟不应该作为RTT采样。

当Initial keys和Handshake keys被丢弃时，Initial packets和Handshake packets都不再能被ack，这些包都需要从Inflight中移除，并且还需要重置PTO timer。

6.2.2.1 Before Address Validation

在server端validate客户端的地址之前，PTO timer不能违反the amount of data it can send is limited to three times the amount of data received这个原则。

而客户端则需要在握手完成前为其握手包设置PTO timer并在触发时发送握手包(有Handshake keys的情况下)或者发送Initial packet(没有Handshake keys)。

6.2.3 Speeding up Handshake Completion

When a server receives an Initial packet containing duplicate CRYPTO data, it can assume the client did not receive all of the server’s CRYPTO data sent in Initial packets, or the client’s estimated RTT is too small. When a client receives Handshake or 1-RTT packets prior to obtaining Handshake keys, it may assume some or all of the server’s Initial packets were lost.

在握手完成之前，遇到上面这两种情况，endpoint可以在PTO触发之前进行重传。

To speed up handshake completion under these conditions, an endpoint MAY, for a limited number of times per connection, send a packet containing unacknowledged CRYPTO data earlier than the PTO expiry, subject to the address validation limits in Section 8.1 of [QUIC-TRANSPORT]. Doing so at most once for each connection is adequate to quickly recover from a single packet loss. An endpoint that always retransmits packets in response to receiving packets that it cannot process risks creating an infinite exchange of packets.

Endpoints can also use coalesced packets (see Section 12.2 of [QUIC-TRANSPORT]) to ensure that each datagram elicits at least one acknowledgment. For example, a client can coalesce an Initial packet containing PING and PADDING frames with a 0-RTT data packet, and a server can coalesce an Initial packet containing a PING frame with one or more packets in its first flight.

coalesced packets，即把几个包合并到一个包中进行发送，通过这种方式可以确保对端至少为这个合并的包发送至少一个ack。

6.2.4 Sending Probe Packets

PTO timer触发时，发端需要发送1至2个ack-eliciting包。除了发送触发PTO timer的packet number space里的包，还应尽可能发送其他packet number space里的包作为probe packets。但是发送的总量仍然必须保持在1至2个ack-eliciting包这个范围。

如果发端想让收端尽快回ack，发端可以让跳过一个packet number来消除收端的ack delay。

QUIC实现应该在probe packet里携带新的数据而不是重传的数据，除非没有新的数据可以发了。实际的具体实现也可以采用其他的策略决定probe packet里携带什么数据。

没有数据可发时(新数据和重传都没有)，发端应该发一个包含PING或者其他ack-eliciting frame的包，重置PTO timer。

Alternatively, instead of sending an ack-eliciting packet, the sender MAY mark any packets still in flight as lost. Doing so avoids sending an additional packet but increases the risk that loss is declared too aggressively, resulting in an unnecessary rate reduction by the congestion controller.

这段话与前面说的禁止因为PTO timer的触发标记丢包矛盾了，不能理解。

6.3 Handling Retry Packets

收到retry packet的client会重新开始建连过程并重置拥塞控制和丢包恢复的状态、重置所有的定时器，但是会保留加密相关的握手信息。

可以通过retry packet计算出RTT作为重新建连过程中的初始RTT。

6.4 Discarding Keys and Packet State

When Initial and Handshake packet protection keys are discarded (see Section 4.9 of [QUIC-TLS]), all packets that were sent with those keys can no longer be acknowledged because their acknowledgments cannot be processed. The sender MUST discard all recovery state associated with those packets and MUST remove them from the count of bytes in flight.

Endpoints stop sending and receiving Initial packets once they start exchanging Handshake packets; see Section 17.2.2.1 of [QUIC-TRANSPORT]. At this point, recovery state for all in-flight Initial packets is discarded.¶

When 0-RTT is rejected, recovery state for all in-flight 0-RTT packets is discarded.

If a server accepts 0-RTT, but does not buffer 0-RTT packets that arrive before Initial packets, early 0-RTT packets will be declared lost, but that is expected to be infrequent.

It is expected that keys are discarded at some time after the packets encrypted with them are either acknowledged or declared lost. However, Initial and Handshake secrets are discarded as soon as Handshake and 1-RTT keys are proven to be available to both client and server; see Section 4.9.1 of [QUIC-TLS].

简言之，QUIC使用的是前向加密，当进入下一加密阶段时，上一加密阶段的数据已经无用，不需要重传，并且需要从inflight中扣除掉。

7.Congestion Control

这篇规范描述的是一个NewReno算法的实现。

和TCP一样，只包含ACK frames的包不算在inflight里，并且不受拥塞控制。但是QUIC实现可以去检测这些只包含ACK frames的包是否丢失，并且利用这个信息去调整ack-only的包的发送速率，但是这篇规范并没有描述一个这样的机制。

QUIC的cwnd以bytes为单位。

QUIC的congestion control是每个path单独运行一个拥塞控制逻辑实例，各个path之间的拥塞控制互不影响。

除非PTO timer触发或者进入recovery这两个特殊状态，禁止bytes_in_flight超出cwnd。

7.1 Explicit Congestion Notification

如果传输路径支持ECN，那么QUIC将把IP头中的Congestion Experienced(CE) codepoint视作拥塞的信号。

7.2 Initial and Minimum Congestion Window

初始拥塞窗口应该设置为10MSS，即max(14720, 2MSS)。

最小拥塞窗口设置为2MSS，并且在以下情况需要将拥塞窗口设置为最小拥塞窗口：

• 遇到丢包；
• an increase in the peer-reported ECN-CE count
• persistent congestion

7.3 Congestion Control States

NewReno的拥塞控制状态转换图：

7.3.1 Slow Start

A NewReno sender is in slow start any time the congestion window is below the slow start threshold. A sender begins in slow start because the slow start threshold is initialized to an infinite value.

While a sender is in slow start, the congestion window increases by the number of bytes acknowledged when each acknowledgment is processed. This results in exponential growth of the congestion window.

The sender MUST exit slow start and enter a recovery period when a packet is lost or when the ECN-CE count reported by its peer increases.¶

A sender reenters slow start any time the congestion window is less than the slow start threshold, which only occurs after persistent congestion is declared.

cwnd低于slow start threshold时，连接就处于Slow Start状态。

连接初始时，slow start threshold被设置为无穷大。

7.3.2 Recovery

已经进入recovery状态时遇到丢包或ECN-CE count增加不会导致再次进入recovery状态。

当因丢包和ECN-CE count增加进入recovery状态时，slow start thershold更新为当前cwnd的一半，并且在退出当前recovery状态之前，cwnd也需要设置为当前cwnd的一半。在cwnd减半之前可以发送一个包，加速丢包恢复的过程。

7.3.3 Congestion Avoidance

当cwnd大于等于slow start threshold并且不是处于recovery状态时，发端就处于congestion avoidance状态。congestion avoidance状态下使用AIMD的拥塞控制算法需要限制cwnd的增长速率为每ack cwnd大小的包，cwnd至多加一个mss。

7.4 Ignoring Loss of Undecryptable Packets

不能解密的包的丢包可以忽略掉。但是：

Endpoints MUST NOT ignore the loss of packets that were sent after the earliest acknowledged packet in a given packet number space.

7.5 Probe Timeout

PTO timer触发后发送的Probe Packets不受cwnd限制，但是要算到inflight里。

7.6 Persistent Congestion

当发端发现所有的包都丢了，并且是一段时间内发出去的包都丢掉了，那么就认为网络进入persistent congestion状态。

7.6.1 Duration

判断进入persistent congestion的Duration阈值：

(smoothed_rtt + max(4*rttvar, kGranularity) + max_ack_delay) *

    kPersistentCongestionThreshold

kPersistentCongestionThreshold的建议取值为3。

7.6.2 Establishing Persistent Congestion

检测出persistent congestion后，发端的cwnd需要设置为kMinimumWindow(2MSS)，就如TCP 触发RTO一样。

检测出persistent congestion的条件(全都要满足)：

• 2个ack-eliciting包都被检测出丢掉了；
• 2个包之间的包也都丢掉了；
• 这两个包的发送时间差超过了persistent congestion duration；
• 第一个包发送之前必须已经有RTT采样；

简单来说就是如果一大段连续的包都丢掉了，并且这些包的发送时间跨度达到了persistent congestion duration，就任务是进入了persistent congestion状态。

7.6.3 Example

7.7 Pacing

pacing的速率设置：

rate = N * congestion_window / smoothed_rtt

或者用inter-packet interval来表达：

interval = ( smoothed_rtt * packet_size / congestion_window ) / N

N至少取1，取一个大于1(如1.25)的值可以避免拥塞窗口的underutilization。

7.8 Underutilizing the Congestion Window

不是很懂。。。

8.Security Considerations

术语

Ack-eliciting packet:

A QUIC packet that contains frames other than ACK, PADDING, and CONNECTION_CLOSE. These cause a recipient to send an acknowledgment; see Section 13.2.1.

      如果一个packet包含了除ACK/PADDING/CONNECTION_CLOSE之外的帧，接收端需要 回ack，发送端需要检测这个包是否丢了并在适当的时候重传丢掉的帧。