network

拥塞控制算法机制介绍

拥塞控制原理实际上包含了四个算法：慢启动，拥塞避免，快重传，快恢复

慢启动阶段

当链路初始启动时，将会把 拥塞控制窗口(cwnd) 设置为1~10个 最大报文段(MSS) ，具体则根据当前机器的TCP协议实现而有所变化。

发送端将根据cwnd的大小来发送数据，在每一个收到有效回复的RTT内，cwnd都会增加1个MSS的大小。考虑到接收端有延迟，大体上是在呈指数级增长。
如果带宽为W，所耗时间如所示计算方法，经过一定的时间之后就可以占满带宽。

time=RTT×log2Wtime=RTT \times log_2W

拥塞避免阶段

拥塞避免的主要思想是 线性增加，乘积减少(AIMD)。

即 Additive Increase, Multiplicative Decrease.

TCP协议中设置了名为 慢启动阈值(ssthresh) 的变量，当cwnd达到ssthresh时，cwnd将会转换为线性增长的拥塞避免阶段。
当数据包在一定时间内没有收到确认时，将会假设未确认是由于网络发生了拥塞，但事实上有些网络环境只是链路质量过于差。
这时候将会进行减半的操作，进而避免产生更多的拥塞。
例如发送了15个包，但只收到了前5个包的确认。后10个包的数据量的一半，设置为新的ssthresh值。
接着把cwnd的值重新设置为1个MSS的大小，再次回到慢启动阶段。

快速重传阶段

有两个事件会导致快速重传的发生，超时重传和重复确认。

超时重传是TCP协议在发送端每发送一个报文段就会设置一个计时器，如果接收端在发送确认回来的时间超过了计时器的等待时间，将会重新发送该报文段。
重复确认是接收端收到未按正确顺序的包时，接收端立刻将最后一次确认过的包再次发送ACK给发送端，该重复阈值一般为3。
即接收端收到同一包的ACK四次之后，便会从ACK中最后一次确认过的包开始继续发包。
一旦发生这两种情况，ssthresh的值和cwnd的值将会与拥塞避免阶段的设置相同，再次回到拥塞避免阶段。

快速恢复阶段

在上述的快速重传阶段之后，又添加了后来的快速恢复阶段。

当发生重复确认时，将进入快速恢复阶段。
这时候将会先按照快速重传阶段的设置把cwnd和ssthresh设置好，接着把cwnd设置为ssthresh加上三个MSS的大小，添加三个的原因一般是重传三次ACK，随后重传丢失了的数据包。
当再次收到重复的ACK时，cwnd将会递增1，并尝试发送间下一个报文段。
这时如果收到新的ACK时，cwnd的值将更改现在的ssthresh的值。
即表示重传已经结束，可以按照顺序继续发送数据，再次回到拥塞避免阶段。

经典TCP拥塞控制算法

TCP/IP协议簇作为当前网络的基本，在保持可靠传输的前提下，承担着流量控制、拥塞控制等任务，以获取高性能数据传输。
TCP协议基本的拥塞控制算法有四个阶段，分别是慢启动阶段、拥塞避免阶段、快速重传阶段、快速恢复阶段。
纵观来看，拥塞控制算法的基本运作流程都可以简化为修改最终数据流，而在这一步不可避免地就要修改 拥塞控制窗口(cwnd)。
一般的拥塞控制算法通过接收端和发送端发包的确认情况和丢失情况，来估计网络是否产生了拥塞，进而避免网络崩溃。
但在实际应用中，这种预估的方法会比真正的拥塞发生要慢上许多。
为解决这一问题，计算机科学家们想过很多办法，比如及早将路由器缓存的情况报告给接收端。
即使用TCP协议的 拓展显式拥塞通知ECN ，当路由器或链路发生拥塞时，把请求发送数据速率降低的信号发给发送端。
仅当配合 活动队列管理(AQM) 策略的时候，ECN才能有效地使用，它依赖于AQM的精确度，而且在高度拥塞的网络环境中性能急剧降低。
另一种方法是测量 RTT(数据包往返时延) ，当RTT增大时，就降低发送数据的速率。
其中的代表是BBR算法，与以往大部分拥塞算法基于丢包来作为拥塞信号不同，BBR算法会主动检测RTT。

BBR拥塞控制算法

普通的拥塞控制算法是由事件驱动的。

不管是丢包还是RTT的增加，都被视为一种严重的拥塞事件，这些严重的拥塞事件导致TCP拥塞控制系统在寻找当前带宽、避免拥塞发生、探测在当前状态下还能使用的带宽这三种状态之间切换，最终的结果也就是导致促使拥塞算法调整拥塞控制窗口的大小。
只要拥塞控制状态机检测到拥塞事件的发生，它就可以直接控制这些状态的切换，而不管它是否实际发生，结果都会导致降低拥塞控制窗口的值。
所以在这点上，Reno算法和Cubic算法的拥塞控制窗口调整是被动的。

BBR算法具有内置的状态机制，不受TCP拥塞控制状态机的控制。
它可以完成所有的状态检测和切换，而不会受到外部干扰。
BBR算法将定期尝试检测是否有更多带宽并尽可能多地使用它，如果没有，它将返回到先前的状态。

BBR状态机的维持。
BBR算法的主体由一个状态机构成，共有四个状态，STARTUP，DRAIN，PROBE_BW，PROBE_RTT。
将 bw(瞬时带宽值) 乘以一个内置的 增益系数(pacing gain) 得到 pacing rate(传输速率) ，以及对RTT值的持续跟踪，BBR算法会根据上述计算的结果在这四个状态之间自由地来回切换。
其目的也是抛弃原有的丢包反馈，使得充分利用带宽。

瞬时带宽的计算。
计算bw(瞬时带宽值)，这是BBR算法中所有计算的基础和规则。
BBR算法将会根据当前获得地瞬时带宽值以及其所处的状态来计算 pacing rate(传输速率) 以及 cwnd(拥塞控制窗口) ，BBR算法的简单高效正是源于此。
系统将会自动跟踪迄今为止最大的瞬时带宽。

实时跟踪RTT。
BBR算法之所以能够获取很高的带宽利用率，是因为它使用了状态机内的两个状态交替测量最大带宽值和最小RTT，得出吞吐率与 RTT的乘积(BDP) 的结果如公式所示。

BDP=BWmax×RTTminBDP=BW_{max} \times RTT_{min}

能利用到这个最大的带宽容量，是BBR算法的最终目标，也正是这个目标最终驱动了cwnd的计算。系统会自动跟踪当前为止最小RTT。
BBR算法最主要维持两个核心的控制参数，pacing rate(传输速率) 和 cwnd(拥塞控制窗口)。

传输速率的计算 pacing_rate=bw×pacing_gainpacing\_rate=bw \times pacing\_gain

拥塞窗口的计算 cwnd=BDP×cwnd_gaincwnd=BDP \times cwnd\_gain

当然，事物存在它的两面性，代价是什么？

BBR自出世以来已经收到了一些批评，首先，因为它倾向于抢占Cubic算法的带宽，在网络公平性上明显存在不足；
其次BBR的机制会导致高重传率；
第三点是在Wi-Fi环境下用户的网速明显变慢。
综合来看，BBR与Cubic相比只能说互有优劣，各有其擅长的领域。

BBRv2

针对BBR的问题，BBRv2的目标就是解决第一版中存在的一些主要缺点，其改进包括了还使用聚合/运行中的参数增强了网络建模，并增加了对 ECN(显式拥塞通知) 的支持等。
为便于理解，我们可以通过这样一张表来了解这几个拥塞算法的异同。

CUBIC BBR v1 BBR v2
Model parameters for the state machine N/A Troughput, RTT Throughput, RTT, max aggregation, max inflight
Loss Reduce cwnd by 30% on window by any loss N/A Explicit loss rate target
ECN RFC3168 (Classic ECN) N/A DCTCP-inspired ECN
Startup Slow-start until RTT rises (Hystart) or any loss Slow-start until throughput plateaus Slow-start until throughput plateaus or ECN/Loss rate > target

早在2019年，Dropbox 就已经在自家的数据中心边缘网络进行尝试使用BBRv2算法，并在下面的博客记载了详细的过程。

Evaluating BBRv2 on the Dropbox Edge Network

“在我们的测试中，BBRv2显示了以下特性:

  • 对于网速较低的用户来说，带宽可以与CUBIC媲美。
  • 对于网速较高的用户来说，带宽可以与BBRv1媲美。
  • 丢包率比BBRv1低4倍；但仍然比CUBIC高2倍。
  • 传输中的数据比BBRv1低3倍；但略低于CUBIC。
  • RTTs较BBRv1低；但仍然比CUBIC高。
  • 与BBRv1相比，RTT具有更高的公平性。

总的来说，BBRv2在BBRv1基础上有了很大的改进，而且在需要更高带宽的情况下，它更接近于成为Reno/CUBIC的完全替代品。
添加实验性的ECN支持，我们甚至可以看到他可以成为 Datacenter TCP (DCTCP) 的完全替代者。”