转 TCP拥塞控制算法-从BIC到CUBIC
“算法”这个标签被第一次添加使用了 20220616 20:07
本文旨在帮助大家理解TCP CUBIC拥塞控制算法背后的点点滴滴以及其方程式为什么就是那样子的。一直以来，很多人都觉得CUBIC算法非常复杂，涉及到复杂的天书般的”3次曲线“...然而，CUBIC并不像大家以为的那样复杂，之所以觉得复杂是因为没有理解其历史和背景。
本文就是介绍CUBIC的历史和背景的...
BIC算法
BIC算法对窗口可能的最大值进行二分查找，它基于以下的事实：1.如果发生丢包的时候，窗口的大小是W1，那么要保持线路满载却不丢包，实际的窗口最大值应该在W1以下；2.如果检测到发生丢包，并且已经将窗口乘性减到了W2，那么实际的窗口值应该在W2以上。 因此，在TCP快速恢复阶段过去之后，便开始在W2~W1这个区间内进行二分搜索，寻找窗口的实际最大值。于是定义W1为Wmax，定义W2为Wmin。 以上说的是”道“，接下来我们看一下”术“，即如何驱动整个二分搜索的过程，非常简单！采用ACK驱动：每收到一个ACK的时候，便将窗口设置到Wmax和Wmin的中点，一直持续到接近Wmax。可见BIC的行为是ACK驱动的，而ACK在什么时候到来是与RTT相关的。这里，我们先留下一个问题。 在了解了”道“和”术“之后，我们来看一下”势“。道只是一个原则，对待所有人都是一样，而术则是实现这个原则的途径，每个人都有不同，然而最终决定谁能独霸天下的是势，这就是说，在领会了道，并且得到了术之后，接下来就要进入争夺阶段了。BIC算法已经在没有丢包的情况下无限接近了Wmax，这意味着带宽有空闲资源了，此次的最大带宽已经不止Wmax了，而是大于Wmax的一个值！问题是，如何找到它！在说如何找到它的方法之前，先说一下怎么知道已经找到了它，答案就是丢包。 超越Wmax之后，如何找到新的Wmax呢？ 也非常简单！既然度过了Wmax都没有丢包，说明新的Wmax还没有达到，此时BIC采取了一种非常简单直接的方法：按照逼近Wmax的路径倒回去，即采用与之对称的方案。 以上整个的道，法，势三者总结成了以下的图示：
两个RTT不同的连接，其通过BIC算法搜索到Wmax的时间是不同，进而其进入Max-Probe阶段也是不同的，因此空闲的带宽会被RTT短的那个连接无情的占有：
当然，BIC算法远不止上面说的那么简单，以上的图解仅仅是理论上的，涉及到实现的时候就不得不考虑TCP运行时的行为特征，比如下图所示的问题：
这带来了BIC实现上的丑陋和复杂性，会有很多的if-else出现，这在感官上很不舒服。----------------------------------------------------------------我们已经看到了BIC的半景全貌，知道了它存在的两个问题：公平性的问题TCP对带宽的利用并不是亲王扫六合的过程，更像是近代欧洲均势。所以说，抢带宽的算法都是傻逼算法。感官上不那么美观的问题数学上追求的是既然原理上是一个公式，在实现上也必须是一个公式，不能加入更多的现实约束。----------------------------------------------------------------解决这些问题的过程导致了CUBIC的诞生！值得注意的是，BIC和CUBIC在命名上特别有意思，BIC是Binary Increase Congestion的首字母缩写，而CUBIC并不是BIC加上了"CU-"前缀(-CU前缀是什么？？)...CUBIC不是什么缩写，它本来就是”立方“的形容词全称，而立方在数学上也是”3次方“的意思，因此顾名思义，CUBIC采用了数学函数即cubic curve的方式，而不是通过ACK到达后的处理行为(B)inary (I)ncrease (C)ongestion来探测窗口。在命名上，这是值得注意的。注解：后面由于会涉及到简单的数学公式，由于在文字中插入希腊字母很不方便，因此凡是数学公式中的希腊字母，我在正文中一律写成其英文音译，比如我会用beta来表示希腊字母里相应读音的那个很像大写B的字母。...
