TCP Congestion Control

2022-02-07 本文已影响0人给艺艺一个未来

介绍

rfc5681 详细说明了TCP的四个拥塞控制算法：慢启动、拥塞避免、快速重传和快速恢复。

专有名词

SEGMENT : segment 指的是任意的 TCP/IP 数据包或者 acknowledgment 包
SENDER MAXIMUM SEGMENT SIZE（SMSS）：SMSS 指的是发送端可传输的最大segment的大小。SMSS的值通常基于：网络MTU（maximum transmission unit），路径MTU发现算法，RMSS 或其他的因素。SMSS不包括TCP/IP headers 和 options。
RECEIVER MAXIMUM SEGMENT SIZE （RMSS）：RMSS 指的是接收端愿意接收的最大segment的大小。RMSS的值由接收端在连接启动阶段发送的MSS选项中指定。如果MSS选项未使用，则默认为536字节。RMSS不包括TCP/IP headers 和 options。
FULL-SIZED SEGMENT：允许包含的最大字节大小的数据的 segment 。
RECEIVER WINDOW（rwnd）：接收窗口大小（在接收端使用）。
CONGESTION WINDOW（cwnd）：拥塞窗口大小（在发送端使用）。
INITIAL WINDOW（IW）：初始化窗口指的是经过三次握手后计算的拥塞窗口的初始化窗口大小。
LOSS WINDOW（LW）：损失窗口指的是当TCP发送端的重传定时器检测到丢包时设置的拥塞窗口大小。
RESTART WINDOW（RW）：重启窗口指的是当TCP发送端在空闲时间段（见慢启动算法）后重新传输时设置的拥塞窗口大小。
FLIGHT SIZE：已发送但尚未累计（cumulatively）确认（acknowledged）的数据量。
DUPLICATE ACKNOWLEDGEMENT：重复的 ACK 指的是 ACK在以下算法下被认为是重复的：
- ACK 的接收者有未完成的数据
- 到来的 ACK 不携带任何数据
- SYN 和 FIN 位都为 off
- 确认号等于给定连接上收到的最大确认号
- 到来的 ACK 宣告的接收窗口大小等于上一次 ACK 宣告的接收窗口大小

或者，利用选择性确认 (SACK) 的 TCP 可以利用 SACK 信息来确定何时传入的ACK是“重复”。

慢启动和拥塞避免

慢启动和拥塞避免算法在TCP发送端使用，用于控制进入网络的数据量。

为了实现这两个算法，在TCP的per-connection阶段引入了两个变量：

拥塞窗口（congestion window）（cwnd）：用于限制发送端在接收到ACK前能够发送至network的最大数据量。
By the way，接收窗口（receive window）（rwnd）：是接收侧对已接收但未完成的数据（到达的数据不连续，乱序）的数量的最大限制；能够进入网络传输的数据取cwnd和rwnd的最小值。
慢启动阈值（slow start threshold）（ssthresh）：用于决定采用慢启动算法还是拥塞避免算法进行传输控制。

开始向未知情况的网络进行传输时要求TCP缓慢探测网络以确定可用带宽，从而避免不适当的爆发数据造成网络拥塞。慢启动算法的目标：在传输开始阶段（采用慢启动算法）和重传定时器检测到丢包之后（重启慢启动算法）避免网络拥塞。另外，慢启动使用"ACK clock"。"ACK clock"在TCP发送端使用，被用于慢启动、拥塞避免以及丢包恢复算法。

初始化

cwnd 的初始值 IW 根据 SMSS 的大小而设置 ：

if SMSS > 2190 bytes:
- IW = 2 * SMSS bytes and MUST NOT be more than 2 segments
if (SMSS > 1095 bytes) and (SMSS <= 2190 bytes):
- IW = 3 * SMSS bytes and MUST NOT be more than 3 segments
if SMSS <= 1095 bytes:
- IW = 4 * SMSS bytes and MUST NOT be more than 4 segments

ssthresh 可以设置为任意高度，但 ssthresh 在遇到拥塞时必须降低。将 ssthresh 设置尽可能高可以自适应网络条件，而不是一些采用任意的主机限制来决定发送速率。在某些 cases 下，例如系统对网络路径有充分的了解，那么更谨慎地设置 ssthresh 初始值可能有好处。

何时使用慢启动算法、拥塞避免算法

当 cwnd < ssthresh 时，使用慢启动算法。
当 cwnd > ssthresh 时，使用拥塞避免算法。
当 cwnd = ssthresh 时，既可以使用慢启动算法，也可以使用拥塞避免算法。

慢启动

在慢启动期间，TCP的cwnd在每接收到一个新数据的递增确认的ACK后至少增长SMSS个字节。当cwnd的大小超过ssthresh后或当观察到拥塞后慢启动结束。虽然传统的 TCP 实现会在收到覆盖新数据的 ACK 后精确地通过 SMSS 字节增加 cwnd，但我们建议 TCP 实现增加 cwnd：
$cwnd = cwnd + min (N, SMSS)$

其中 N 是在到来的 ACK 中确认的先前未确认的字节数（接收端会采用累积确认、延迟确认等算法，因此存在先前未确认的字节数）。并且不能每个ACK都增加cwnd的大小，毕竟会存在重复的ACK。

拥塞避免

在拥塞避免期间，TCP的cwnd在每个往返时间（RTT）增加一个 full-sized segment。拥塞避免算法持续到发生拥塞。在拥塞避免期间增加 cwnd 的基本准则是：

可以采用 SMSS bytes 增加 cwnd
每一个RTT使 cwnd 增长一次
cwnd每次增长不能超过 SMSS bytes

在拥塞避免期间增加 cwnd 的推荐方法是计算新数据的 ACK 已确认的字节数 (同 slow start)，但不能每个 RTT 触发的 cwnd 的增长不能超过 SMSS bytes。当确认的字节数达到 cwnd，可以增长 SMSS bytes 。

在拥塞避免期间，TCP可以使用的另一个通用的公式是:

$cwnd = cwnd + SMSS \ast SMSS \div cwnd$

在每个确认新数据的 ACK 到来时执行此调整。该公式为每个 RTT 将 cwnd 增加 1 个 full-sized segment 的基本原理提供了可接受的近似值。

实现说明：

由于 TCP 实现中通常使用整数运算，当拥塞窗口大于 $SMSS \ast SMSS$ 时， $SMSS \ast SMSS \div cwnd$ 结果为 0，则结果应该四舍五入到 1 字节。
较旧的实现在 $cwnd = cwnd + SMSS \ast SMSS \div cwnd$ 的右侧有一个附加的附加常数。这是不正确的，实际上会导致性能下降 [RFC2525]。
一些实现以字节为单位维护 cwnd，而其他实现以 full-sized segment 为单位。后者会发现 $cwnd = cwnd + SMSS \ast SMSS \div cwnd$ 难以使用，并且可能更喜欢使用上一段中讨论的计数方法。

慢启动和拥塞避免的异同

同：

窗口增长时机相同：每接收到一个新数据的递增确认的ACK后（即每一个RTT），使窗口增长一次
发生丢包后的行为相同：快速重传、快速恢复、超时重传

异：

窗口增长机制不同：
- 慢启动：新数据的递增确认的ACK累计确认的字节数，但最少增加一个 SMSS
  $cwnd = cwnd + min (N, SMSS)$
- 拥塞避免：一个 full-sized segmen，但最多增加一个 SMSS，
  $cwnd = cwnd + SMSS \ast SMSS \div cwnd$

ssthresh——慢启动阈值

当TCP发送端通过重传定时器检测到 segment loss 且该 segment 尚未通过重传定时器重新发送时，此时 ssthresh 的值必须重新设置为不超过下列等式中给出的值：

$ssthresh = max (FlightSize \div 2, 2 \ast SMSS)$

其中，FlightSize 是网络中未完成数据的数量。

另一方面，当TCP发送端通过重传定时器检测到 segment loss 且该 segment 已经通过重传定时器重新发送至少一次时，此时 ssthresh 的值保持不变。

实现说明：

一个容易犯的错误是：是简单地使用 cwnd，而不是采用 FlightSize，在某些实现中cwnd可能会偶然增加远远超过 rwnd

超时重传——并重启慢启动

此外，在超时（Retransimission Timer）时，cwnd 必须设置为不超过丢失窗口 LW，LW 等于 1 个 full-sized segment（无论 IW 的值如何）。因此，在重传 loss segment 后，TCP 发送方使用慢启动算法将窗口从1 个 full-sized segment 增加到新的 ssthresh 值，此后再次使用拥塞避免算法。

超时后基于慢启动的丢失恢复（loss recovery）可能会导致虚假重传，从而触发重复确认。在 TCP 实现中，对这些重复 ACK 到达的反应差异很大。本文档没有具体说明如何处理此类确认，但可以指出这是一个可以从额外关注、实验和规范中受益的领域。

Fast Retransmit / Fast Recovery （快速重传和快速恢复）

重复的ACK

当一个乱序的 segment 到达时，TCP的接收端立即发送一个重复的 ACK 。这个 ACK 的目的是通知发送端：接收端接收到了一个乱序的 segment 以及接收端目前期待收到的序列号。从发送端的视角来看，重复的 ACK 可能会引起一些网络问题。

首先，重复 ACK 可能是 dropped segment 引起，在这种case下，在 dropped segment 之后 all segements 都会触发重复的 ACK，直到 dropped segment 被修复。
其次，重复 ACK 可能是网络对数据段的重新排序造成的（在某些网络路径下并非罕见的事件）。
最后，重复 ACK 可能是网络复制 ACK 或数据段造成的。

另外，当TCP 的接收端接收到的 segment 填充空间中全部或部分间隙时，TCP接收端应该立即发送 ACK 。这将为发送方的超时重传、快速重传或高级丢失恢复算法等方法提供更及时的信息。

TCP发送端基于到来的重复ACK，使用快速重传算法来检测和修复丢包。

快速重传算法和快速恢复算法

快速重传算法：快速重传算法使用3个重复的ACK作为一个segment已丢失的指示，在接收到3个重复的ACK后，TCP重新传输看似丢失的segment，而无需等待重传计时器的触发。

快速恢复算法：在快速重传算法发送看似丢失的 segment 之后，快速恢复算法控制新数据的传输，直到非重复的ACK到达。

收到重复的ACK不执行慢启动的原因：收到重复的ACK不能完全表明一个 segment 已经丢失，因为该部分 segment 最可能已经离开了网络（segment 在接收端的缓冲区中，不再被视作网络资源）。此外，由于保留了 ACK 的时钟（重传定时器），TCP发送端可以继续传输新的 segments 。

快速重传和快速恢复算法的实现

当发送端收到第一个和第二个重复的ACK时，如果接收方宣告的窗口允许，TCP应该根据 [RFC3042] 发送一个先前未发送的数据的 segment ，而总的 FlightSize 将保持小于或等于 cwnd + 2*SMSS，并且新的数据可用于传输。总之，TCP发送端不必改变cwnd来反思这两个重复的ACK [RFC3042]。请注意，使用 SACK [RFC2018] 的发送者不得发送新数据，除非到来的重复确认包含新的 SACK 信息。
当发送端收到第三个重复的ACK时，TCP必须设置 ssthresh 为不超过公式 $ssthresh = max (FlightSize \div 2, 2 \ast SMSS)$ 给的值。当使用 [RFC3042] 时，在传输受限下额外传输的数据不包含在此计算中。
重新传输从 SND.UNA 开始的丢失段（lost segment）( 以上，快速重传)
并且将 cwnd 设置为 $ssthresh + 3*SMSS$ 。这相当于人为地将 cwnd 膨胀了，膨胀的大小实际上是已离开网络且处于接收端缓冲区的 segment 数量（三个，（毕竟收到了三个重复的ACK嘛，可以理解为接收端收到了三个并缓存了下来咯））。
当发送端继续接收到重复的ACK（在第三个重复的ACK之后继续出现的ACK）时，cwnd必须以SMSS大小增长。这当然是人为地膨胀拥塞窗口，以便反映已经离开网络进入接收端缓冲区的 additional segment。
当以前未发送的数据可用并且 cwnd 的新值和接收者通告的窗口允许时，TCP 应该发送 1*SMSS 字节的以前未发送的数据。
当下一个确认先前未确认数据的 ACK 到达（即非重复的ACK）时，TCP 必须将 cwnd 设置为 ssthresh（在步骤 2 中设置的值）。这被称为“放气”窗口。( 以上，快速恢复)

其他考虑因素

重启闲置连接（Restarting IDLE Connections）

上面描述的 TCP 拥塞控制算法的一个已知问题是：TCP在空闲一段相对长的时间之后，TCP将被允许传输潜在的不适当的流量突发。

TCP 可能会在空闲期后将以 cwnd 大小的线路速率突发地向网络传输数据。
TCP在空闲期后，此时地cwnd已经不能代表现在的网络容量（毕竟端到端的网络状况是处于不断变化之中的）。

[Jac88] 建议 TCP 在相对较长的空闲期后使用慢启动来重新启动传输。慢启动用于重新启动 ACK 时钟，就像它在传输开始时所做的那样。该机制已以下列方式广泛部署。当 TCP 在超过一次重传超时时长后仍未收到一个 segment 时，cwnd 会在传输开始前减小到重新启动窗口 (RW) 的值。

出于本标准的目的，我们定义RW = min(IW,cwnd)。

因此，如果 TCP 在超过重传超时的时间间隔内没有发送数据，则 TCP 应该在开始传输之前将 cwnd 设置为不超过 RW。

生成应答（Generating Acknowledgments）

[RFC112] 提出的延迟应答算法可以应用在TCP的接收端。当然在采用延迟应答时，TCP的接收端不必过度延迟应答。

延迟应答的算法：

数量上：每两个 full-sized segment 生成一个 ACK 。
时间上：若数量上能收到第二个 full-sized segment，则在第一个未确认数据包到达的 500 ms 内生成一个 ACK。（毕竟不一定能收到 full-sized segment，可能受协商、受MTU的限制）

在某些情况下，发送方和接收方可能无法就什么构成 full-sized segment 达成一致。如果每次从发送方接收到 2*RMSS 字节的新数据时至少发送一个 ACK，则认为实现符合此要求，其中 RMSS 是接收方指定给发送方的最大段大小（或默认值 536 字节，根据 [RFC1122]，如果接收方在连接建立期间未指定 MSS 选项）。

丢包恢复机制（Loss Recovery Mechanisms）

当检测到数据窗口中的第一次丢失时，ssthresh 必须设置为不超过等式 $ssthresh = max (FlightSize \div 2, 2 \ast SMSS)$ 给出的值。其次，在修复新的数据窗口中的所有 lost segments 之前，每个 RTT 中传输的segments 必须不超过检测到丢失时未完成的segment的数量的一半。最后，在给定的段窗口中的所有损失

最后，在给定的段窗口中的所有丢失都已成功重传后，cwnd 必须设置为不超过 ssthresh，并且必须使用拥塞避免来进一步增加 cwnd。在两个连续的数据窗口中丢失，或丢失重传，应被视为拥塞的两个指示，因此，在这种情况下，cwnd（和 ssthresh）必须降低两次。

我们建议 TCP 实施者采用某种形式的高级丢失恢复，可以应对数据窗口中的多个丢失。 [RFC3782] 和 [RFC3517] 中详述的算法符合上述一般原则。我们注意到，虽然这不是符合上述一般原则的仅有的两种算法，但这两种算法已经过社区审查，目前处于标准轨道上。

安全考虑

本文档要求 TCP 在重传超时和重复确认到达的情况下降低其发送速率。因此，攻击者可以通过导致数据包或其确认丢失，或者通过伪造过多的重复确认来损害 TCP 连接的性能。

为了响应 [SCWA99] 中概述的 ACK 分割攻击，本文档建议根据每个到达的 ACK 中新确认的字节数而不是每个到达的 ACK 上的特定常量来增加拥塞窗口（ cwnd += min (N, SMSS) ，N 是在到来的 ACK 中确认的先前未确认的字节数）。

互联网在很大程度上依赖于这些算法的正确实施，以保持网络稳定性并避免拥塞崩溃。攻击者可以通过伪造过多的重复确认或对新数据的过多确认，使 TCP 端点在面对拥塞时做出更积极的响应。可以想象，这样的攻击可能会使网络的一部分陷入拥塞崩溃。