使用TSQ解决本地Bufferbloat

在上一篇文章《TCP BBR算法中Pacing，cwnd，fq以及TSQ对RTT的影响》中，我分析了TSQ对本地Qdisc队列中TCP测量RTT的影响，又进一步分析了BBR算法是如何利用这一影响的。然而并没有给出一个总的框图来说明这一切结合在一起是如何运作的。

可以看到，如果有持续的数据包一直企图激进地排入队列，那么CoDel算法将用持续地越来越激烈的丢包作为反应，从而任何流量都无法到达类似传统RED算法中的那种“刚刚好”的平衡状态！

强调CoDel算法的负反馈过程

恕我直言，将竞速流量全部看作是不知收敛的恶意流量。
       当有恶意的竞速流量企图堵死节点队列的时候，它将会面临越来越严重的惩罚，直到其收敛！这就是CoDel算法的负反馈过程。
       CoDel算法判断流量是否收敛的原则非常简单，只有一个，就是数据包的排队延迟小于target即可，这是恶意流量唯一可以钻空子的“平衡状态”，不过想象一下，默认target为5ms的情况下，恶意流量如何能保持“平衡”，完全占据这5ms的时间窗口呢br>       我们假设恶意流量S巧妙控制了它的发送速率和发送量，使得它的数据包在队列中的时间正好处在target即5ms的边界下(这是很难的…)，如果只要S一个流通过节点，这非常棒，S流达到了自己的目的，虽然这并没有什么意义！现在考虑多个流共享节点队列的情况。由于S流完全占据了5ms为界限的排队时间窗口，这必然会导致属于其它流的数据包排队延迟超过5ms，由于S流并不懂得退让，那么这个过程将持续，直到超过了CoDel算法给的“收敛机会”，即interval时间。此时会触发丢包…丢哪个流的包呢少呢br>       CoDel算法最直接的丢包策略就是从队列中依次出队数据包并将其丢弃，那么一个流的数据包在队列里占比越多，丢它的数据包的可能性就越大，显然这个正在讨论的场景中会丢弃大量S流的包。下一个问题，丢多少呢Del算法会持续不断的以越来越快的速度丢包，直到发现有数据包的排队延迟小于5ms了才停止，丢包速度与丢包量正相关，即丢包越多，丢包越快。
       那么紧接着的问题就是，在什么情况下数据包的排队延迟会再次小于5ms呢一种情况，那就是S流收敛了！
       理解这个负反馈过程了吗看一下负反馈和正反馈的通俗解释：

如果S流不收敛会如何单，如果它不收敛，它会面临大量的包被丢弃，直到丢包的速度赶上数据包到达的速度，队列清空停止丢包，才可以再次腾出一个微小的时间窗口，然而它被恶意的S流再次迅速填充，丢包再次开始…结果就是，所有的流量都无法通过！这是一种极端的惩罚，一般而言，除了竞速流量以及攻击流量不懂收敛，正常的TCP以及带有流控的UDP流量在发现丢包时都会采取收敛策略的。
       相对于传统的RED算法，我更倾向于部署简单直接的CoDel算法来进行队列管理，当竞速流量由于被狠狠地惩罚变得无利可图的时候，它们才会懂得收敛的意义，这是一种多方共赢的博弈，而不是零和博弈！
       本节的要点在于，为了让负反馈尽快生效，需要一个正反馈来刺激，请先记住这个结论，下面展示伪代码的时候，会提到一个control_law例程，它展示了正反馈的过程。
       本节结束！

Codel算法伪代码

如果在原理上看CoDel有些不直观，那么给出伪代码或许是更好的方式，因为它更直接。Talk is cheap,show me the code!
我先给出CoDel伪代码的链接：http://queue.acm.org/appendices/codel.html
       然后我简单分析一下这个代码。

       我简化了上述链接中的代码，去掉了异常判断，假设场景如下：
1.节点拥有无限长容量的队列，且队列永不为空；
2.只有一个队列入口，即enque例程；

3.只有一个队列出口，即dequeue例程。

time_t first_above_time;     Time when we’ll declare we’re above target (0 if below)
time_t drop_next;     Time to drop next packet
uint32_t count;     Packets dropped since going into drop state
flag_t dropping;     Equal to 1 if in drop state
———————————————
time_t target = MS2TIME(5);        Target queue delay (5 ms)
time_t interval = MS2TIME(100);        Sliding minimum time window width (100 ms)

掌握了上述伪代码里蕴含的那个状态机，就理解了CoDel算法的实质。其实这个AQM机制是非常简单的，想理解原理的，直接看伪代码基本上不到10分钟就能搞定，然而任何简单的东西，其背后的思想却不是一两句话就能说清的，理解背后的思想和理解眼前的原理，其意义完全不同。

CoDel算法与TCP BBR

和传统的TCP拥塞算法相比，BBR可以更好地与CoDel进行适配。本节好好说说这个事。
       传统的TCP拥塞算法是对带宽实际情况无感知的，它们都是基于一个“数学上收敛的模型”，即AIMD模型运作的，在AI过程中，基本上都是盲目的探测，而MD过程又是过激地降速，这个过程往往会造成很多可用带宽的消耗或者说浪费，一方面丢包作为拥塞信 ，重传数据包会消耗部分本来可以传输新数据的带宽，另一方面，在结束了MD过程后，一个新的缓慢AI的过程只有在丢包前夕的那一刻才能有效利用所有带宽，其余时刻都是谨慎又盲目的上探过程，剩余的空闲带宽便无法被利用。这便是传统拥塞算法的症结之根本。
       由于这个症结的存在，排队现象是不可避免的！实际上，传统的TCP拥塞算法误用了节点的队列缓存。队列的存在会让传统的TCP拥塞算法误认为是剩余可用带宽，它们并不能意识到队列的存在，所以即便它们都是收敛的流量，CoDel算法也无法“匡正”它们的“错觉”。因此，在传统TCP拥塞算法上部署CoDel算法，依然会出现锯齿状的全局同步现象，事实上，这种现象是可以消除的，CoDel的本意也是在于消除这种现象。
       BBR根治了传统TCP拥塞算法的症结。
       BBR采集了时间窗口(用于老化数据样本)的历史中最大带宽，以及最小的RTT，并且在另一个时间窗口内“坚持使用该最小RTT”，这就意味着在一个时间窗口内，BBR估算的BDP是不变的，BBR由于采集到了真实的带宽和RTT数据并基于此数据调节发送速率，这便不再需要盲目探测的过程了。BBR采集到的最小RTT便是不排队的RTT，因此在正常情况下，队列缓存不会被使用，CoDel算法几乎不会触发丢包。
       我们先来看下传统的TCP拥塞算法和BBR分别是怎么使用队列的：

可见，BBR自己就不会主动排队，因此CoDel算法在BBR场景下就是只是为了善意的监管，而非惩罚。我们来看看这是为什么。
       在没有恶意的竞速流量，只存在BBR流量的情况下，如果在同一条链路上进入了一个新的流，那么BBR自身的Probe RTT机制会使得最终两条流收敛到均分带宽，如上图的结果。这是怎么做到的呢知道在BBR坚持使用采集到的最小RTT时间超过默认的10s期间，没有采集到至少是持平或者更小的RTT，BBR会进入Probe RTT状态，将发送量减少为4个窗口，重新采集RTT，而此时由于已经有2个流共享同一链路了，BBR自身在退出Probe RTT后会避免形成队列，所以最终它们采集到的最小RTT均不会包括排队延迟，这是一件非常爽的事情。那么在此期间，CoDel的作用是什么呢br>       你会发现，其实不用CoDel算法，BBR也依然可以收敛到不排队状态，期间可能会经历最多10s(默认配置)的轻微排队状态。好像是CoDel变得多此一举了。事实上，我觉得在纯BBR的情况下，CoDel存在的价值恰恰就在于为BBR提供一个良好环境，CoDel是BBR的保护者，而非限制者，也非监管者，CoDel保护BBR免受传统的TCP拥塞控制算法盲目探测之害，同时也在一定程度上阻止了恶意的竞速流量侵占宝贵的带宽。
       CoDel旨在解决Bufferbloat，BBR也是解决了Bufferbloat，目标相同，效果自然相同，可以相当好的携手紧密配合。

CoDel AQM算法总结

——————————–
—-写于令屈原心如刀割的端午之夜

周末快乐！