Network - TCP Congestion Control

Created by : Mr Dk.

2021 / 03 / 09 16:45

Nanjing, Jiangsu, China

About

拥塞控制是 TCP 通信的每一方需要执行的一系列行为，防止网络因为大规模的通信负载而瘫痪。当有理由认为网络即将进入拥塞状态时，减缓 TCP 传输速率。难点：

  • 如何准确判断合适减慢速度
  • 如何减缓传输速度
  • 何时恢复原有速度

当某一路由器在单位时间内接收到的数据量多余可发送的数据量时，就需要把多余的部分存储起来。如果这种情况持续，那么存储资源将会耗尽，这种现象称为拥塞。如果不采取对策，那么网络性能将大受影响导致瘫痪。因此需要 TCP 通信的每一方都执行 拥塞控制机制。

发送方没有精确的方法知晓中间路由器的状态，常用的推断方式是观察是否有丢包发生。在 TCP 中，丢包被用于判断拥塞发生与否的指标，并衡量是否实施相应措施 (减缓发送)。

TCP 发送端的发送速率应该等于以下两种中的最小值：

  • 接收端的接收速率
  • 传输速率

反应网络传输能力的变量被称为 拥塞窗口 (congestion window, cwnd)，接收端的通知窗口为 awnd。发送端实际可用的窗口就是两者的最小值：W = min { cwnd, awnd }。也就是说，在发送端，还没有收到 ACK 回复的字节数不能多于 W。W、cwnd、awnd 都会随时间动态改变。

Algorithms

在 TCP 连接建立之初，由于无法获知可用的传输资源，cwnd 的初始值是无法确定的，而通信双方交换一个报文就可以获得 awnd 的值。获取 cwnd 的最佳做法是以越来越大的速率发出数据，直到出现丢包为止，这里就有两种策略：

  • 慢速启动发送
  • 立刻以 (awnd 限制下的) 最大速率发送

由于多个 TCP 连接共享网络传输路径，全速启动将会影响其它连接的传输性能。

TCP 发送方的拥塞控制操作是由 ACK 的接收 来驱动的。当接收到一个 ACK 后，拥塞控制机制可以决定是否再发一个数据包，是否再发更多的数据包，如何多发数据包等问题。由一个 ACK 到达触发的数据包传输被称为 自同步 (self-clocking) 关系。

慢启动

当一个新的 TCP 连接建立，或由 重传超时 导致了丢包时，需要执行慢启动。慢启动为 cwnd 指定了一个 初始窗口 (Initial Window)，通常是 SMSS (发送方最大段大小) 的整数倍。当接收到一个大于之前收到的 ACK 号的 ACK 号后，发送窗口扩大为原来的两倍，并发送数量等于窗口大小的数据包。如果这些数据包的 ACK 都被成功接收，那么窗口再扩大两倍。以指数函数的形式扩大窗口。概括：TCP 发送方每收到一个 ACK 就执行一次 cwnd 的增长操作。

拥塞避免

cwnd 不可能以指数函数的形式无限增大。在到达 慢启动阈值 (slow start threshold, ssthresh) 后，意味着 可能 有更多可用的传输资源，如果立刻占用，将使共享路由器的其它连接出现严重的丢包和重传。cwnd 到达 ssthresh 后，将进入拥塞避免阶段。每个新的 ACK 到达，将会使 cwnd 有相应的 小幅增长，也称为累加增长。

每个 ACK 应答到来时，cwnd 增加 1 / cwnd。比如，cwnd 为 8，当 8 个 ACK 应答到来时，cwnd 将会增加 8 * 1/8，也就是 1，即线性增长。

慢启动阈值

在通常操作中，TCP 连接总是选择慢启动和拥塞避免算法中的一个。它们的区别在于 cwnd 以什么样的方式增大。慢启动阈值不是固定的，而是会随着时间改变。如果出现重传的情况，TCP 会认为窗口超出了网络传输能力，将慢启动阈值减小为当前窗口大小的一半。

快速恢复算法

BSD 4.2 (Tahoe) 中的 TCP 版本在检测到丢包后，不论使由于超时还是快速重传，都会重新进入慢启动状态，使得带宽利用率较为低下。需要针对不同的丢包情况，考虑是否需要重新回到慢启动状态：

  • 如果是超时引发的丢包，则重新进入慢启动：慢启动阈值变为 cwnd 的一半，cwnd 被重设为 1
  • 如果是重复 ACK (快速重传) 而引起的丢包，则没必要重新进入慢启动状态

TCP 的标准使用了上述的核心思想：TCP 连接建立之初，设置慢启动阈值，在接收到新数据传输成功的 ACK 后，使用慢启动或拥塞避免算法更新 cwnd。当接收到三次重复的 ACK (快速重传信号) 时，执行快速恢复算法：

  • 慢启动阈值被设置为 cwnd 的一半 (防止网络拥塞)
  • 启动快速重传算法，cwnd 被设置为 (ssthresh + 3 * SMSS)
  • 每接收到一个重复 ACK (丢包已被重传并确认，新的数据包有发送机会)，cwnd 暂时增大 1
  • 当收到新数据的 ACK 后，重新执行拥塞避免算法，cwnd 被设置为慢启动阈值

可以认为三个重复的 ACK 引发的重传占了三个本来可以传输的之后的数据包的流量，所以窗口增长到慢启动阈值 + 3 * SMSS。之后如果又收到一个重复 ACK，说明又要重传一次，又占了一个之后数据包的流量，所以窗口大小又增大了 1。

直到需要被重传的数据都被重传 (接收到了新数据的 ACK)，窗口才会恢复正常大小 (慢启动阈值)，并重新执行拥塞避免算法。

基于延迟的拥塞控制算法

之前的拥塞控制算法基于丢包信息。而实际中，当发送端不断向网络中发送数据包时，不断增长的 RTT 就可以作为拥塞形成的信号。一些拥塞控制技术是基于这个发现而被提出的。

References

TCP/IP 详解 - 卷 1：协议

知乎专栏 - 30 张图解：TCP 重传、滑动窗口、流量控制、拥塞控制