BBR是Google在16年Q4发布的一种新的TCP拥塞控制算法，现已经在Linux 4.9 Kernel实装。相较于传统的Reno和目前相对主流的Cubic而言可以说是采用了完全另一种设计思路。结合Google前些年发布并于Chrome实装的QUIC协议，可以看到Google想从深层次改变目前互联网格局的野心。
这段时间在研究基于UDP的可靠传输，读了不少文献。UDP可靠传输文献倒是有不少，IETF上发的协议也是百家齐鸣，然而只要想在公共网络传输，归根结底拥塞控制还是要参考TCP的老前辈们。今天在网上偶遇一篇文章，通过对比Reno、Cubic、Vegas和BBR的不同，深入讲解了BBR几点核心设计到底是为何而存在，感觉受益匪浅。稍微把学习过程的笔记整理整理发在这里，理解有误之处还请大家多多指点。
原文链接：https://blog.apnic.net/2017/05/09/bbr-new-kid-tcp-block/ 文中图表皆转自原文
TCP Reno
- A.K.A. AIMD
- Slow start 每ACK指数上涨，拥塞避免每ACK线性增加，遇到丢包每重复ACK窗口减半
- Reno的几点假设：
- 丢包只由拥塞导致，拥塞的原因是buffer overflow
- RTT稳定，带宽上限稳定
- 对buffer的认识：减半发送窗口不仅会使buffer停止增长，还会使其减小
- Reno的缺陷
- Buffer << DBP （delay bandwidth product）导致带宽的低利用率
- Buffer > DBP，实际上处于buffer bloat状态，减半对解决问题并无太大作用
- 即使假设成立，拥塞避免期间带宽增长还是太慢
- 30ms RTT，包长1500 Bytes，从5Gbps增长到10Gbps需要3.5小时
- 这还建立在3.5h内不丢包的前提下，也就是说丢包率要小于78亿分之一
Cubic
- 基于BIC （Binary Increase Congestion Control）修改，BIC有如下规定
- 算法目标是一直寻找即将造成丢包的发送速度临界点
- 记住上次丢包前的最大窗口以及当前的窗口大小
- 丢包后，对于每个没有丢包的RTT，窗口大小增加量为（上次最大窗口-当前窗口）/2
- 当目前窗口达到上次最大窗口后，设定某限定值m
- （当前窗口大小-上次最大）<m：每RTT窗口增长值是上次的两倍，初始为1
- （当前窗口大小-上次最大）>=m：线性增长
- Cubic在BIC的基础上为防止后者在低RTT环境下过于激进做了如下修改
- 窗口涨幅使用三次多项式的函数，且自变量为自上次丢包经过时间而非RTT数量
- 用时间取代RTT次数对多股RTT不同的流更为公平
- 对每RTT窗口涨幅的最大值设限，因此刚刚丢包后窗口的增长为线性增长
- Cubic相比Reno更为高效，由于其在丢包后尽快尝试恢复到以前的窗口
从路由器buffer的角度看
- 状态1为队列形成前，入栈速度<带宽
- 状态2为队列已经形成，此时入栈速度>=带宽
- 状态3为队列已满，新包将被丢弃
- 最理想的状态是1与2间的临界状态，缓存队列即将形成却没有形成，带宽被最大利用，且没有因拥塞丢包的情况发生
- Reno在状态1到3间不断抖动，拥塞直到丢包才被发现，恢复过程带宽利用率低下
- Cubic在状态2与3间不断交替，尝试尽可能使缓存被充满以保持带宽利用率，代价是高延迟
- 从路由器的角度讲Cubic与Reno都不是最理想的解决方案
如何实现维持最理想的传输状态？
- 理论上可以通过追踪RTT的变化实现
- 状态1的情况下增加发送速度对RTT没有影响
- 状态2随着窗口大小的增加RTT也会随之线性增加
- 状态3可以由丢包反馈
- 显然，在进入状态2后，增加窗口大小对提升带宽利用没有任何帮助
- 因此，将发送速率维持在使路由器处于在状态1与2中间的状态是理想情况
TCP Vegas
- 早期以维持状态1、2的临界状态为目标的拥塞控制算法
- 记录每包发送时间与对应ACK的收取时间
- 增加的RTT，或者丢包，会导致发送速率减慢
- 稳定的RTT会使发送速率增加，以寻找新的使RTT增加的速率
- Vegas存在的问题
- 发送速率的变化始终为线性变化，对某段链路负载能力的大幅度变化需要长时间才能适应
- 无法竞争过同链路使用Reno或其他由丢包触发控制的流
- 当Vegas感知队列的形成而减慢发送速度时，Reno会继续充满buffer，从而导致Vegas进一步减慢发送速度，以此类推
BBR
- BBR有别于Vegas，意识到了瓶颈带宽与RTT受多方面因素影响，不仅是本流因素
- 一旦BBR决定了可维持的速度，将积极尝试从其他AIMD算法中防守该速度
- BBR持续估计RTT与可用瓶颈带宽
- RTT为一段时间（数十秒到几分钟）内的最小RTT
- 瓶颈带宽为最高传输速度。测量方法是计算最近6-10个RTT内，发送流与ACK流的相关系数（correlation）
- 这两个参数相互独立，其中一个的变化不会影响另一个
- 对于每个发出的包，BBR标注其是为stream packet或者application limited
- 只对针对非application limited包发出的ACK更新瓶颈带宽估计
- pacing：包以预估的瓶颈速率被发出，而不是burst，可以避免瓶颈速率突变时在瓶颈链边缘产生队列
- BBR会定期在一个RTT内以高于DBP一定比例（1.25倍）的速率发送数据
- 不太激进，但足以导致在满占用的链路周围产生队列
- 这会导致RTT的提升，但不一定影响带宽估计
- 如果带宽估计没变，那么BBR会在之后一个RTT内减低速率以使队列被清空
- 如果带宽估计提高，那么BBR对依照新的瓶颈带宽进行调整
- 连续的带宽测试会持续提升预期瓶颈带宽直到一个相对稳定的值。在该预期值提升的过程中，传输速率的提升接近于指数提升，而非Vegas的线性提升
- 突然增加速率产生的带宽压力，也可能使其他拥塞控制算法退让，而后BBR依旧处于稳定传输阶段，迅速占用资源
- 连接建立起步过程速率提升迅速，类似于Reno，每RTT传输速率翻倍。但是起步过程结束的判据与Reno不同，是由瓶颈带宽不再提升触发的
- BBR的其他技术细节与公平性需要参考其他官方文献
分享链路下的测试与可预见问题
- BBR定期增大速率的手段理论上在buffer按照DBP设计的节点会很有效
- 然而如果buffer大于DBP，增大的速率可能不足以产生足够的压力让其他算法退让
- 同时，如果BBR在高估了RTT状态下建立了一个稳定状态，则该状态下路由器的队列会被维持在某一个定长。此时，BBR与基于丢包检测的算法相比，会产生极大优势
- Google报告表明BBR可以与Cubic共存。Cubic略占优势，但不会出现一方将另一方驱逐的情况
- 但是有测试指出不论在低延迟还是跨大陆的链路中BBR相比Cubic都有较大优势
15ms RTT 10Gbps，仅BBR与Cubic，BBR在Cubic 20s后启动的测试结果
300ms RTT 德国到澳大利亚 存在不可控外部流的情况下的测试结果