上一篇我已经总结了: TCP 滑动窗口和定时器，所以这一篇我继续总结一下 TCP 的拥塞控制。

理论

重要概念

• AIMD：加法增长乘法减小
• MSS (Maximum Segment Size)：网络中可以经过的最大的段大小；
• CWND(Congestion Window): 同时可以发送多少个包；
  • 一个 CWND 意味着一个 MSS

图 1：MTU 和 MSS 的关系
图来自 Cloudflare 博客

慢速启动

当建立连接时，发送端用一个很小的值初始化窗口，一开始是 1 的，不过后面根据经验值改为 4 作为初始值。然后发送端发送初始化大小窗口的数据，数据包经过一个往返时间之后被确认，对于每一个在重传定时器超市前就接收到的数据段，发送端的拥塞窗口都会增加一个段。这个时候，因为增加了一段和收到了前一个段的响应，所以一下可以发送 2 个段，所以，没经过一个 RTT，拥塞窗口就增加了一倍。虽然这个算法被叫做慢速启动，但其实它一点也不慢。

线性增长

为了保持对慢速启动的控制，发送端为每个链接维持了一个 慢启动阈值，当拥塞窗口超过 慢启动阈值 时，每次 RTT 只会增加一个数据段（之前是成倍得增加），当遇到超时时，慢启动阈值 被设置为当前拥塞窗口的一半。慢启动阈值 一开始的默认值被设置成任意高（当然，不同的拥塞算法有不同的设置策略，例如 Tahoe 一开始设置为 64 KB）

快速重传

如果确认一个包已经超时，如果使用重传定时器，可能效率会比较低，因为它必须保守。发送端有一个快速方法来识别它的包已经丢失，因为在接收端，如果丢失数据包的后续数据包到达接收端时，他们会触发发送端返回确认，这些确认都将携带着相同的确认号，成为 重复确认。发送端每次收到重复确认后，很可能另一个包已经到达了接收端而丢失的那个包还没有出现。

虽然 TCP 可能因为数据段的传输路径不同而导致包的乱序，但是，通常情况下这样的情况并不常见，所以 TCP 很随意得将三次相同的 重复确认 认定为该数据段丢失。

快速恢复

快速重传的机制比较慢，每次出现超时之后都需要从 1 个数据段开始，为了加强效率，因此有了 快速恢复，它的目的就是保持拥塞窗口上运行确认时钟，使得在有一个新的阈值或者快速重传时可以把拥塞窗口减少到一半，而不是直接从初始值开始。为了实现这个效果，就需要对重复计数累计（包括 3 次重复计数），累计重复计数到网络中未确认的分段数是当前拥塞窗口值，这大概需要半个 RTT 即可。

在快速恢复一个 RTT 之后，重复计数的那个分段也应该被接收端接收，在这个时刻，重复确认流将停止，快速恢复模式退出，拥塞窗口将被设置为新的慢启动阈值，并开始按照线性增长开始。

• 12 和 13 表示快速重传，ssthresh 从 1 开始，比较低效；
• 21 和 22 表示快速恢复，出现 3 次重复确认之后，减半拥塞窗口和 ssthresh 减少重传的包。

拥塞控制的改进

选择重传

在重复确认中，发送端无法知道接收端具体丢了哪些包，需要重发那些包，所以 TCP 就增强了一个 选择确认 功能，通过选择确认，接收端最多可以向发送端响应 3 段接收到的数据包，这样发送端就可以有选择得发送丢失的包，从而减小网络压力：

显式拥塞通知

显式拥塞通知(ECN，Explicit Congestion Notification) 是 IP 层的机制，它主要是用来通知主机发生了拥塞，在 TCP 中，当建立连接的时候，发送端会设置 ECE 和 CWR 标志位，告诉对方支持 ECN 机制，双方协商表示都支持 ECN 之后，该 TCP 连接就会使用 ECN。

每个写到 TCP 端的数据包都会在 IP 头上打上标记，表示支持 ECN，当遇到网络拥塞时，支持 ECN 的路由器就会设置 ECN 标志，然后接收端接受到之后，就会使用 ECE（ECN Echo）标志位给发送端发通知，告诉发送端数据包经历了拥塞。发送端就会通过拥塞窗口减少（CWR，Congestion Window Reduced）标志位告知接收端已经收到拥塞信号了。

当发送端接收到拥塞通知知道，就会采取重复确认一样的拥塞控制。

延迟确认

在调试 API 的延时的时候，可能有些情况下我们会遇到一个很常见的延迟时间：40ms，这个很可能时 TCP 的延迟 ACK 导致的。

TCP 的延迟 ACK 是为了减少 TCP 数据包的传输而创建的，目的是将 ACK 包随下一次的数据包发回对端，如果在一定时间内没有要发送到对端的数据包，那么才会直接 ACK，而这个时间默认就是 40ms，在 CentOS 系统中可以通过设置：

[root@liqiang.io]#  echo 15 > /proc/sys/net/ipv4/tcpdelackmin

来修改，这里是设置为 15ms。在有些系统中是没有修改选项的，默认就是 40 ms，所以如果当你遇到类似于这个时间时，不妨注意一下这个问题。

Linux 下的拥塞控制实现

TCP 拥塞控制算法发展的过程中出现了如下几种不同的思路：

• 基于丢包的拥塞控制：将丢包视为出现拥塞，采取缓慢探测的方式，逐渐增大拥塞窗口，当出现丢包时，将拥塞窗口减小，如 Reno、Cubic 等。
• 基于时延的拥塞控制：将时延增加视为出现拥塞，延时增加时减小拥塞窗口，延时减小时增大拥塞窗口，如 Vegas、FastTCP 等。
• 基于链路容量的拥塞控制：实时测量网络带宽和时延，认为网络上报文总量大于带宽时延乘积时出现了拥塞，如 BBR。
• 基于学习的拥塞控制：没有特定的拥塞信号，而是借助评价函数，基于训练数据，使用机器学习的方法形成一个控制策略，如 Remy。

拥塞控制算法的核心是选择一个有效的策略来控制拥塞窗口的变化，下面介绍几种经典的拥塞控制算法：

Nagle

Nagle 算法主要用来预防小分组的产生。在广域网上，大量 TCP 小分组极有可能造成网络的拥塞。

Nagle 是针对每一个 TCP 连接的。它要求一个 TCP 连接上最多只能有一个未被确认的小分组。在该分组的确认到达之前不能发送其他小分组。TCP 会搜集这些小的分组，然后在之前小分组的确认到达后将刚才搜集的小分组合并发送出去。

有时候我们必须要关闭 Nagle 算法，特别是在一些对时延要求较高的交互式操作环境中，所有的小分组必须尽快发送出去。

我们可以通过编程取消 Nagle 算法，利用 TCP_NODELAY 选项来关闭 Nagle 算法。

Nagle 大致的逻辑：

if 有数据要发送：
    if 可用窗口大小 >= MSS and 可发送的数据 >= MSS：
        立刻发送MSS大小的数据
    else ：
        if 有未确认的数据：
            将数据放入缓存等待接收ACK
        else：
            立刻发送数据

适用场景

• 小包非常多，实时性要求不高，带宽不足的情况

Vegas

Vegas[1] 将时延 RTT 的增加作为网络出现拥塞的信号，RTT 增加，拥塞窗口减小，RTT 减小，拥塞窗口增加。具体来说，Vegas 通过比较实际吞吐量和期望吞吐量来调节拥塞窗口的大小：

Vegas 算法采用 RTT 的改变来判断网络的可用带宽，能精确地测量网络的可用带宽，效率比较好。但是，网络中 Vegas 与其它算法共存的情况下，基于丢包的拥塞控制算法会尝试填满网络中的缓冲区，导致 Vegas 计算的 RTT 增大，进而降低拥塞窗口，使得传输速度越来越慢，因此 Vegas 未能在 Internet 上普遍采用。

适用场景

适用于网络中只存在 Vegas 一种拥塞控制算法，竞争公平的情况。

Reno

Reno[2] 将拥塞控制的过程分为四个阶段：慢启动、拥塞避免、快重传和快恢复，是现有的众多拥塞控制算法的基础，下面详细说明这几个阶段。

• 慢启动阶段，在没有出现丢包时每收到一个 ACK 就将拥塞窗口大小加一（单位是 MSS，最大单个报文段长度），每轮次发送窗口增加一倍，呈指数增长，若出现丢包，则将拥塞窗口减半，进入拥塞避免阶段；
• 当窗口达到慢启动阈值或出现丢包时，进入拥塞避免阶段，窗口每轮次加一，呈线性增长；
• 当收到对一个报文的三个重复的 ACK 时，认为这个报文的下一个报文丢失了，进入快重传阶段，立即重传丢失的报文，而不是等待超时重传；
• 快重传完成后进入快恢复阶段，将慢启动阈值修改为当前拥塞窗口值的一半，同时拥塞窗口值等于慢启动阈值，然后进入拥塞避免阶段，重复上诉过程。

Reno 拥塞控制过程如图 1 所示。

图 1：TCP Reno 拥塞控制过程

Reno 算法将收到 ACK 这一信号作为拥塞窗口增长的依据，在早期低带宽、低时延的网络中能够很好的发挥作用，但是随着网络带宽和延时的增加，Reno 的缺点就渐渐体现出来了，发送端从发送报文到收到 ACK 经历一个 RTT，在高带宽延时（High Bandwidth-Delay Product，BDP）网络中，RTT 很大，导致拥塞窗口增长很慢，传输速度需要经过很长时间才能达到最大带宽，导致带宽利用率将低。

适用场景

适用于低延时、低带宽的网络。

Cubic

• CUBIC: A New TCP-Friendly High-Speed TCP Variant

Cubic[3] 是 Linux 内核 2.6 之后的默认 TCP 拥塞控制算法， 使用一个立方函数（cubic function）

图 ：这个是图片说明

作为拥塞窗口的增长函数，其中，C 是调节因子，t 是从上一次缩小拥塞窗口经过的时间，Wmax 是上一次发生拥塞时的窗口大小，

图 ：这个是图片说明

β 是乘法减小因子。从函数中可以看出拥塞窗口的增长不再与 RTT 有关，而仅仅取决上次发生拥塞时的最大窗口和距离上次发生拥塞的时间间隔值。

Cubic 拥塞窗口增长曲线如下，凸曲线部分为稳定增长阶段，凹曲线部分为最大带宽探测阶段。如图 2 所示，在刚开始时，拥塞窗口增长很快，在接近 Wmax 口时，增长速度变的平缓，避免流量突增而导致丢包；在 Wmax 附近，拥塞窗口不再增加；之后开始缓慢地探测网络最大吞吐量，保证稳定性（在 Wmax 附近容易出现拥塞），在远离 W max 后，增大窗口增长的速度，保证了带宽的利用率：

图 2：TCP Cubic 拥塞窗口增长函数

当出现丢包时，将拥塞窗口进行乘法减小，再继续开始上述增长过程。此方式可以使得拥塞窗口一直维持在 Wmax 附近，从而保证了带宽的利用率。Cubic 的拥塞控制过程如图 3 所示：

图 3：TCP Cubic 拥塞控制过程

Cubic 算法的优点在于只要没有出现丢包，就不会主动降低自己的发送速度，可以最大程度的利用网络剩余带宽，提高吞吐量，在高带宽、低丢包率的网络中可以发挥较好的性能。

但是，Cubic 同之前的拥塞控制算法一样，无法区分拥塞丢包和传输错误丢包，只要发现丢包，就会减小拥塞窗口，降低发送速率，而事实上传输错误丢包时网络不一定发生了拥塞，但是传输错误丢包的概率很低，所以对 Cubic 算法的性能影响不是很大。

Cubic 算法的另一个不足之处是过于激进，在没有出现丢包时会不停地增加拥塞窗口的大小，向网络注入流量，将网络设备的缓冲区填满，出现 Bufferbloat（缓冲区膨胀）。由于缓冲区长期趋于饱和状态，新进入网络的的数据包会在缓冲区里排队，增加无谓的排队时延，缓冲区越大，时延就越高。另外 Cubic 算法在高带宽利用率的同时依然在增加拥塞窗口，间接增加了丢包率，造成网络抖动加剧。

适用场景

适用于高带宽、低丢包率网络，能够有效利用带宽。

BBR

• BBR: Congestion-Based Congestion Control
• Exploring the BBRv2 Congestion Control Algorithm for use on Data Transfer Nodes

BBR[4] 是谷歌在 2016 年提出的一种新的拥塞控制算法，已经在 Youtube 服务器和谷歌跨数据中心广域网上部署，据 Youtube 官方数据称，部署 BBR 后，在全球范围内访问 Youtube 的延迟降低了 53%，在时延较高的发展中国家，延迟降低了 80%。目前 BBR 已经集成到 Linux 4.9 以上版本的内核中。

BBR 算法不将出现丢包或时延增加作为拥塞的信号，而是认为当网络上的数据包总量大于瓶颈链路带宽和时延的乘积时才出现了拥塞，所以 BBR 也称为基于拥塞的拥塞控制算法（Congestion-Based Congestion Control）。BBR 算法周期性地探测网络的容量，交替测量一段时间内的带宽极大值和时延极小值，将其乘积作为作为拥塞窗口大小（交替测量的原因是极大带宽和极小时延不可能同时得到，带宽极大时网络被填满造成排队，时延必然极大，时延极小时需要数据包不被排队直接转发，带宽必然极小），使得拥塞窗口始的值始终与网络的容量保持一致。

由于 BBR 的拥塞窗口是精确测量出来的，不会无限的增加拥塞窗口，也就不会将网络设备的缓冲区填满，避免了出现 Bufferbloat 问题，使得时延大大降低。如图 4 所示，网络缓冲区被填满时时延为 250ms，Cubic 算法会继续增加拥塞窗口，使得时延持续增加到 500ms 并出现丢包，整个过程 Cubic 一直处于高时延状态，而 BBR 由于不会填满网络缓冲区，时延一直处于较低状态。

图 4：Cubic 和 BBR RTT 对比

由于 BBR 算法不将丢包作为拥塞信号，所以在丢包率较高的网络中，BBR 依然有极高的吞吐量，如图 5 所示，在 1% 丢包率的网络环境下，Cubic 的吞吐量已经降低 90% 以上，而 BBR 的吞吐量几乎没有受到影响，当丢包率大于 15% 时，BBR 的吞吐量才大幅下降。

图 5：Cubic 和 BBR 传输速率与丢包率关系对比

BBR 算法是反馈驱动的，有自主调节机制，不受 TCP 拥塞控制状态机的控制，通过测量网络容量来调整拥塞窗口，发送速率由自己掌控，而传统的拥塞控制算法只负责计算拥塞窗口，而不管发送速率（pacing rate），怎么发由 TCP 自己决定，这样会在瓶颈带宽附近因发送速率的激增导致数据包排队或出现丢包。

经过测试，在高延时、高丢包率的环境下，BBR 相对于 Cubic 算法在传输速度上有较大的提升，具体的测试结果表 1 所示：

表1：200ms 延时下 Cubic 与 BBR 传输速度对比

BBR 算法的不足之处在于设备队列缓存较大时，BBR 可能会竞争不过 Cubic 等比较激进算法，原因是 BBR 不主动去占据队列缓存，如果 Cubic 的流量长期占据队列缓存，会使得 BBR 在多个周期内测量的极小 RTT 增大，进而使 BBR 的带宽减小。

适用场景

适用于高带宽、高时延、有一定丢包率的长肥网络，可以有效降低传输时延，并保证较高的吞吐量。

Remy

Remy[5] 也称为计算机生成的拥塞控制算法（computer-generated congestion-control algorithm），采用机器学习的方式生成拥塞控制算法模型。通过输入各种参数模型（如瓶颈链路速率、时延、瓶颈链路上的发送者数量等），使用一个目标函数定量判断算法的优劣程度，在生成算法的过程中，针对不同的网络状态采用不同的方式调整拥塞窗口，反复修改调节方式，直到目标函数最优，最终会生成一个网络状态到调节方式的映射表，在真实的网络中，根据特定的网络环境从映射表直接选取拥塞窗口的调节方式。

Remy 试图屏蔽底层网络环境的差异，采用一个通用的拥塞控制算法模型来处理不同的网络环境。这种方式比较依赖输入的训练集（历史网络模型），如果训练集能够全面覆盖所有可能出现的网络环境及拥塞调节算法，Remy 算法在应用到真实的网络环境中时能够表现的很好，但是如果真实网络与训练网络差异较大，Remy 算法的性能会比较差。

适用场景

网络环境为复杂的异构网络，希望计算机能够针对不同网络场景自动选择合适的拥塞控制方式，要求现有的网络模型能够覆盖所有可能出现情况。

实践

常用命令

• 查看系统中的拥塞窗口：ss -i
  • 示例输出：cubic wscale:13,6 rto:585 rtt:228.914/36.33 ato:40 mss:1448 rcvmss:536 advmss:1448 cwnd:10 bytes_acked:11234 bytes_received:977 segs_out:13 segs_in:9 send 506.0Kbps lastsnd:44057 lastrcv:44145 lastack:43828 pacing_rate 1.0Mbps rcv_space:28960
  • 字段解释：
    • cubic：拥塞算法
    • wscale:<snd_wscale>:<rcv_wscale>：if window scale option is used, this field shows the send scale factor and receive scale factor
    • rto：tcp re-transmission timeout value, the unit is millisecond
    • rtt:<rtt>/<rttvar>：rtt is the average round trip time, rttvar is the mean deviation of rtt, their units are millisecond
    • ato:<ato>：ack timeout, unit is millisecond, used for delay ack mode
    • mss:<mss>：max segment size
    • cwnd:<cwnd>：congestion window size
    • bytes_acked:<bytes_acked>：bytes acked
    • bytes_received:<bytes_received>：bytes received
    • segs_out:<segs_out>：segments sent out
    • segs_in:<segs_in>：segments received
    • send <send_bps>bps：egress bps
    • lastsnd:<lastsnd>：how long time since the last packet sent, the unit is millisecond
    • lastrcv:<lastrcv>：how long time since the last packet received, the unit is millisecond
    • lastack:<lastack>：how long time since the last ack received, the unit is millisecond
    • pacing_rate <pacing_rate>bps/<max_pacing_rate>bps：the pacing rate and max pacing rate
    • rcv_space:<rcv_space>: a helper variable for TCP internal auto tuning socket receive buffer

总结

每一种拥塞控制算法都是在一定的网络环境下诞生的，适合特定的场景，没有一种一劳永逸的算法。网络环境越来越复杂，拥塞控制算法也在不断地演进。本文不是要去选择一个最好的算法，只是简单介绍了几种典型算法的设计思路、优缺点以及适用场景，希望能给大家带来一些启发。

Ref

1. S.O. L. Brakmo and L. Peterson. TCP Vegas: New techniques for congestiondetection and avoidance. In SIGCOMM, 1994. Proceedings. 1994 InternationalConference on. ACM, 1994.
2. V.Jacobson, “Congestion avoidance and control,” in ACM SIGCOMM ComputerCommunication Review, vol. 18. ACM, 1988, pp. 314–329.
3. L. X. I. R. Sangtae Ha. Cubic: A new TCP -friendlyhigh-speed TCP variant. In SIGOPS-OSR, July 2008. ACM, 2008.
4. C.S. G. S. H. Y. Neal Cardwell, Yuchung Cheng and V. Jacobson. BBR:congestion-based congestion control. ACM Queue, 14(5):20{53, 2016.
5. K.Winstein and H. Balakrishnan. TCP Ex Machina: Computer-generated Congestion Control.In Proceedings of the ACM SIGCOMM 2013 Conference, 2013.