TCP拥塞控制技术与BBR的加速原理

本文会简要的讲一下关于 TCP 拥塞控制技术 的由来与发展，以及现在很常见的 BBR 的加速原理

什么是拥塞

拥塞现象，是指数据到达通信子网的过程中，某一部分的分组数量过多，使得该部分网络来不及处理，以致引起这部分乃至整个网络性能下降的现象。严重时会导致网络陷入死锁。
这种现象好比公路上常见的交通拥挤，当节假日公路车辆大量增加时，道路拥堵，使每辆车到达目的地的时间增加，即发生了拥塞。

什么是拥塞控制技术

拥塞控制（Tcp Congestion Control），就是针对此问题的控制技术（应对方案），但也不能说是应对，拥塞控制只能尽量缓解拥塞。
拥塞控制用于调整 TCP 连接单次发送的分组数量（单次发送量，在英文和代码中称做 cwnd），它通过逐步调整单次发送量，使其逼近当前网络的承载量。
拥塞控制的目标是最大限度地利用网络带宽，同时不产生数据流传输中的拥塞现象。
这也是 锐速 和 BBR 能起到明显加速效果的原因。

传统的TCP拥塞控制算法

传统的 TCP 拥塞控制主要是基于 Van Jacobson 博士提出的慢启动算法、拥塞避免算法和用于估计周转 RTT(Round Trip Time)的算法。

慢启动算法通过观察进入网络的速率应该与另一端返回确认的速率相同进行工作。慢启动为发送方增加了一个称为“拥塞窗口”（英文中称为 cwnd ）的窗口，当与接收方建立 TCP 连接时，拥塞窗口被初始化为 1 个报文段（即另一端通告的报文段大小）。接收方每收到一个 ACK ，拥塞窗口就增加 1 个报文段（ cwnd 以字节为单位，而慢启动以报文段大小为单位进行增加），发送方取拥塞窗口与通告窗口中的最小值作为发送上限，即拥塞窗口是发送方的流量控制，通告窗口是接收方的流量控制。发送方开始时发送一个报文段，然后等待 ACK ，收到 ACK 后拥塞窗口从 1 增加到 2 ，即可以发送两个报文段。当收到这两个报文段的 ACK 后拥塞窗口则增加为 4 ，拥塞窗口呈指数式增长。

然后，在某些传输段可能会达到容量上限，中间路由便开始丢弃分组。拥塞避免算法就是用于处理丢失分组的算法。
拥塞避免算法假定分组丢失是非常少的（远小于 1% ），因此认为分组丢失就意味着在发送方和接收方之间的某个传输段上发生了拥塞。
慢启动和拥塞避免算法是两个目的不同、独立的算法，但在实际中这两个算法通常在一起实现。当拥塞发生时，我们希望降低分组进入拥堵段的速率，于是设计了慢启动方式来做到这一点。

1990 年出现的 TCP Reno 版本，增加了快速重传算法和快速恢复算法，避免了当网络拥塞不够严重却因采用慢启动算法而造成过大地减小发送窗口尺寸的现象。

1.拥塞控制的四个阶段

1. 慢启动阶段(Slow Start)：发送方一开始便向网络发送多个报文段，直至达到接收方的通告窗口大小为止。当发送方和接收方处于同一局域网时这种方式值得采用。但假如在发送方和接收方之间存在多个路由或速率较低的链路时，就可能引起一些问题。某些中间路由必须缓存分组，并有可能耗尽存储空间。
2. 拥塞避免阶段(Congestion Avoidance)：当发现有超时或收到 3 个相同 ACK 确认帧时，认为有丢包发生，此时网络已发生拥塞现象，需进行相应的拥塞控制：将慢启动阈值设置为当前拥塞窗口的一半；若检测到超时，拥塞窗口就被置为 1 。假如拥塞窗口 <= 慢启动阈值，则重新进入慢启动阶段；假如拥塞窗口大于慢启动阈值，执行拥塞避免算法。
3. 快速重传阶段(Fast Retransmit)：当发送方收到三个相同的 ACK 副本时，认为有丢包发生，并迅速令发送方重传丢失的数据包，而不必等待 RTO 超时。同时将 ssthresh 设置为当前 cwnd 值的一半，并且将 cwnd 减为原先的一半。
4. 快速恢复阶段(Fast Recovery)：当旧数据包离开网络后，才能发送新数据包进入网络，即同一时刻在网络中传输的数据包数量是恒定的。假如发送方收到一个重复的 ACK ，则认为已经有一个数据包离开了链路，并将拥塞窗口加 1 。

2.对传统TCP拥塞控制机制的发展及改进

1. 对慢启动的改进
   慢启动算法通过逐渐增加 cwnd 大小来探测可用的网络容量，防止连接一开始便采用过大发送量导致网络拥塞。然而有时该算法也会浪费可用的网络容量，因为慢启动算法总是从 cwnd = 1 开始，每收到一个 ACK ，cwnd 增加 1 ，对于高 RTT 网络，为使 cwnd 达到合适值，需要花费很长时间在探测上。因此可设置较大初始窗口，大的初始窗口避免了延迟 ACK 机制单个报文段初始窗口的等待超时问题，缩短了小 TCP 流的传输时间和大延迟链路上的慢启动时间。
2. 对重传与恢复的改进
   为了避免不必要的重传超时，有人提出了一种受限传输机制：发送方接收到一个或两个重复 ACK 后，才继续传输新的数据报文段。从而避免了不必要的重传。
   有很多情况下，数据报文段并没有丢失，但发送方可能会误判数据报文段丢失，然后调用拥塞控制减小拥塞窗口大小。比如当重传定时过早溢出时，发送方在重传数据报文段时不必要地减小了拥塞窗口，而这时实际上并没有数据报文段丢失。假如是由于数据报文段的重新组织而不是数据报文段的丢失，导致 3 个重复确认，同样会导致发送方不必要地在快速重传数据报文段后减小拥塞窗口。
   假如发送方在重传数据报文段一个 RTT 后发现接收方接收到了重传数据报文段的两个拷贝，则可以推断重传是不必要的。这时，发送方可以撤销对拥塞窗口的减小。发送方可以通过将慢启动阀值增加到初始值，使拥塞窗口恢复至初始值。除了恢复拥塞窗口，发送方还可以调整重复确认阀值或者重传超时参数来避免多次不必要的重传。
3. 对公平性的改进
   在拥塞避免阶段，假如没有发生丢包事件，则发送方的 cwnd 在每个 RTT 时间内大约可以增加一个报文段大小，但这样会造成具有不同 RTT 或窗口尺寸的多个连接在瓶颈处对带宽竞争的不公平性。大 RTT 或小窗口的连接，相应的 cwnd 增长速度也相对缓慢，所以只能得到很少一部分带宽。
   要解决上述问题，可以通过在路由处使用公平队列和 TCP 友好缓存来进行控制以增加公平性。假如没有路由的参与，要增加公平性，就要求发送方的拥塞控制进行相应的改变，在拥塞避免阶段使共享同一资源的各个 TCP 连接以相同速度发送数据，从而确保了各个连接间的公平性。

新的拥塞控制技术 – BBR

BBR 是谷歌内部员工开发的新 TCP 拥塞控制技术，和锐速一样属于激进算法
上文提到过，锐速和 BBR 加速的作用在于最大限度利用网络带宽，同时不产生数据流传输中的拥塞现象
但同时这也引起了 TCP 连接的公平性问题和可能的多余窗口发送

BBR 的组成

概括来讲，BBR 由 5 部分组成：

1. 即时速率的计算
   计算一个即时的带宽，该带宽值是 BBR 后续一切计算的基准。BBR 会根据当前的即时带宽以及其所处的 pipe 状态来计算 pacing rate 以及 cwnd ，后面我会提到，这个即时带宽计算方法的突破式改进是 BBR 简单且高效的根源，计算方案按照数学计算，不再局限于数据的含义。在 BBR 运行过程中，系统会跟踪当前时段的最大即时带宽。
2. RTT 的跟踪
   BBR 之所以可以获取高带宽利用率，是因为它可以非常奔放地探测到带宽的最大值以及 RTT 的最小值，这样计算出来的 BDP 就是目前为止 TCP 管道的最大容量。BBR 的目标就是充分利用这个最大容量，这个目标最终驱动了 cwnd 的计算。在 BBR 运行过程中，系统会跟踪当前时段最小 RTT 。
3. pipe 状态机
   BBR 根据 TCP 的拥塞状况，有针对性地定义了 4 种状态，即 STARTUP ，DRAIN ，PROBE_BW ，PROBE_RTT 这四种状态。BBR 通过对上述计算的即时带宽 BW 和 RTT 的持续观察，在这四种状态之间自由切换，相比以前的所有拥塞控制算法，其革命性的改进在于 BBR 不再跟踪系统的 TCP 拥塞状态机，而旨在用统一且自由的方式来应对 pacing rate 和 cwnd 的计算，不管当前 TCP 是处在 Open 还是处在 Disorder 状态，抑或已到达 Recovery 状态。事实就是，BBR 忽略丢包的存在，只考虑对 BW 和 RTT 的观察。
4. 输出：pacing rate 和 cwnd
   BBR 的输出并不仅仅是一个 cwnd ，更重要的是 pacing rate 。在传统算法中，cwnd 是 TCP 拥塞控制算法的唯一输出，但它仅仅规定了当前 TCP 最多可以发送多少数据流，它并没有规定怎么把这么多数据发送出去，在 Linux 中，如果发出这么多数据呢？简单而粗暴 – 突发！忽略接收端通告窗口的前提下，Linux 会把 cwnd 窗口数据全部突发出去，而这往往会造成路由的排队。BBR 在计算 cwnd 的同时，还计算了一个与之适配的 pacing rate ，该 pacing rate 规定 cwnd 指示的窗口数据的数据包之间以多大的时间间隔发送出去。
5. 外部机制的利用
   BBR 可以高效地运行且如此简单，还在于很多机制并不是它本身实现的，而是利用了外部的已有机制。
   下文中将阐述它为什么在计算带宽 BW 时能做到如此奔放地将重传数据也计算在内。

带宽的计算

即时带宽 BW 的计算

BBR 完全忽略系统层面的 TCP 状态，计算带宽时它仅需要两个值：

• 应答了多少数据，记为 delivered
• 应答 delivered 所用的时间，记为 interval_us

将上述二者相除，就能得到带宽：
BW = delivered/interval_us

以上的计算完全是标量计算，只关注数据的大小，不关注数据的含义。例如 delivered 的采集中，BBR 根本不关心某个应答是重传后的 ACK 确认的、正常 ACK 确认的、还是 SACK 确认的。BBR 只关心被应答了多少。
这和 TCP/IP 网络模型是一致的，因为在中间链路上，路由交换机也不会去管这些数据包是重传的还是乱序的，然而拥塞也是在这些地方发生的，既然拥塞点都不关心数据的意义，TCP 为什么要关注呢？拥塞发生的原因，即数据量超过了路由带宽限制，利用这一点，只需要精心地控制发送数据量就好了，完全不用管什么乱序、重传之类的。

PACING RATE 以及 CWND 的计算

pacing rate 怎么计算？就是即时带宽 BW 。而即时带宽 BW 是上一次采样计算的结论，这次能否按照这个 BW 发送数据呢？这要看当前的增益系数的值，设为 G ，那么 G×BW 就是 pacing rate 的值。

至于 cwnd 的计算，cwnd 其实描述了一条网络管道（而 rwnd 描述了接收端缓冲区），因此 cwnd 其实就是这个管道的容量即 BDP 。BW 已经有了，还缺少 RTT 。BBR 一直在持续搜集最小 RTT ，BBR 并没有采用类似移动指数平均算法来猜测 RTT ，而是直接采集最小 RTT（这个 RTT 是 TCP 系统层面移动指数平均的结果，即 SRTT ，但 BBR 并不会对此结果再次做平均。最小 RTT 表示一个曾经达到的最佳 RTT ，既然曾经达到过，说明可以再次达到该 RTT ，这样有益于网络管道利用率最大化。通过 G’×BDP 就算出了 cwnd ，这里的 G’是 cwnd 的增益系数，与带宽增益系数 G 含义一样，根据 BBR 的状态机获取。

状态机

不断地基于当前带宽以及当前的增益系数计算 pacing rate 以及 cwnd ，以这 2 个结果作为拥塞控制算法的输出。在 TCP 连接的持续过程中，每收到一个 ACK ，都会计算即时带宽，然后将结果反馈给 BBR 的 pipe 状态机，不断地调节增益系数。
可以发现，它是一个典型的封闭反馈系统，与 TCP 当前处于什么拥塞状态完全无关。这非常不同于之前的所有拥塞控制算法，在之前的算法中，算法内部是受外部的拥塞状态影响的，比方说在 Recovery 状态下，甚至都不会进入拥塞控制算法。
在 BBR 问世前，Linux 使用 PRR 算法控制 Recovery 状态的窗口调整，即使这个时候网络已经恢复，TCP 也无法发现， 因为 TCP 的 Recovery 状态还未恢复到 Open.