基于RTT梯度的TCP CDG拥塞控制算法

在BBR之前，业内已经逐渐学会如何判断网络拥塞并且用于TCP拥塞控制了。

        再次重申，我鄙视并且非常恶心TCP！

        我本来想看看CDG算法究竟是个什么东西，无奈并没有发现什么资料，所以，就像BBR一样，只能由我来写，我不希望到时候再搜索CDG的资源，都是我写的了，请注意，CDG不是腾讯的CDG，而是CAIA Delay-Gradient。虽然CDG在BBR之前，但是我认为，在褪去了BBR的光环之后，CDG显得更加适合中国人。毕竟BBR的要求太TMD多了，只是很多人不晓得而已，他们显露着一张张疲惫的脸庞，最终是一张张更加疲惫的脸庞...在介绍CDG之前，我先来说一下BBR的要求：

1.BBR要求底层为其开路，Google B4 SDN做到了，然而国内运营商，BAT的骨干网做不到。
2.BBR在通用下载模式中迎合了HTTP 2.0，因为其支持stream，都是“不短的连接”。
3.BBR适用于非速率优先的连接，比如恒定码率的视频流，Pacing最适合这种，而这种连接最怕传统TCP的突发。
4....
...可能还有5

如果你连1，2，3都不知道，就不要盲目测试BBR了。理解SDN的重要性，以程序员的视角，难！

-----------------------------------

好了，我要开始介绍CDG了。

        一开始可能要扫兴一下，如今Linux 4.2内核版本以后实现的CDG算法，简直就是垃圾！这不怪CDG算法，这怪Linux拥塞控制算法框架本身就是一个垃圾框架！这一切在4.9内核之后得到了改善，这一切不得不让人感谢BBR算法的提供者，是他们修改了Linux的拥塞控制算法框架的结构，然而只有BBR本身收益了，CDG并没有收益。

        这也许是因为CDG一开始就不受欢迎吧，所以它的作者没有动力去完善它。然而这一切被我尝试了一下，效果碾压BBR。一开始不受喜欢并不是CDG的错，而是其受制于Linux拥塞控制算法框架限制的错，被掣肘当然无法发挥，但是被我修改后，它可以驰骋了。关于我对CDG的修正，会有一篇单独的文章阐明。

        CDG算法的核心，在于盯着RTT的变化，以便判断是否队列已经填满，由此来指导丢包发生后的行为。要点有二：

1.如果队列满了而丢包，那么乘性减窗；
2.如果队列非满而丢包，那么概率性乘性减窗；

事实上，如果不是为了保证公平性，如果队列非满而丢包，完全可以不减窗。现在的问题是“如何判断队列是否已经满了”。

        其实很简单，下面的图示足以说明CDG模型的简单性：

图中的参数是以下的含义：

-----------------------------------

为了让“非队列满情况下拥塞而丢包”这件事被忽略，就必须要保持窗口继续增长，然而Linux TCP的实现基于30年前的模型，在快速恢复阶段必须脱离拥塞控制算法的控制，降低窗口，所以对于CDG而言，在实现上必须要使用”小技巧“。Linux在快速恢复阶段采用了PRR算法而不是RFC算法，算是一个创举，然而即便如此，PRR算法也不受任何特定拥塞控制算法的控制。

        这很悲哀！所以，在BBR算法对Linux内核TCP实现进行重构之前，CDG之类的优秀算法只能委曲求全！

        现在让我们看一下CDG的标准行为吧：

然而你在Linux中可能看不到这些，你只能看到个大概。上图中的第4个步骤，在Linux的实现中就没有很好的体现出来，我改了一版自己的实现，实现了这个逻辑。

-----------------------------------

多么好的算法，类似BBR那样对网络进行主动的探知，而不是仅仅依靠ACK反馈。

        我说过BBR是最简单的拥塞控制算法，但是CDG却是比BBR更加简单的。它的模型为其建立了判断拥塞的根据，使CDG算法从对丢包敏感进化成了对拥塞敏感，以此就可以知道到底是拥塞了发生的丢包还是没有拥塞，而拥塞与否是拥塞控制的关键。这就是CDG算法的全部了。

        将CDG的思想用在CUBIC非常简单，这样改造后的CUBIC就可以过滤非拥塞丢包了，这也是我将要做的事情。但是在TODO之前，我必须将Linux本身的CDG算法搞完善才行。现在离Linux 4.9发布的时间还不是太久，该版本集成了BBR算法和其对TCP框架的修改，如果CDG意识到了这里的意义，肯定会优化的，但是起码现在还没有，由于我要自用，只能我来做了。首先，我已经把BBR的逻辑移植到了3.10版本内核，其次，我要把4.3的CDG移植到3.10内核，然后基于这个移植做修改。

参考：《Revisiting TCP Congestion Control using Delay Gradients》