首页 > 代码库 > TCP BBR算法与Reno/CUBIC的对比

TCP BBR算法与Reno/CUBIC的对比

我一再强调,BBR算法是个分界点,所有的TCP拥塞控制算法,被分为BBR之前和BBR之后的(其实发现,这并不是我个人的观点,很多人都这么认为,所有想写本文探个究竟)。当然这里的”所有“并不包括封闭的那些算法,比如垃圾公司Appex的算法,或者伟大的垃圾微软的算法。任何的算法都内含了一个进化的过程,CUBIC和Reno看起来非常不同,但是却属于同一个思想,因此可以说,CUBIC是Reno的高级版本(将一种锯齿换成另一种锯齿而已),事实上,TCP拥塞控制算法一直处在不断的改进之中,起初,Reno算法,然后就是NewReno,再往后就是各种混战,直到最终落实到了CUBIC,起码在Linux平台是这么一个过程,其它的平台,也是大同小异。
        关于从Reno到CUBIC进化过程的细节,这里不谈,相信80%的人可能并不在乎,另外20%在乎的人可能比我懂得更多,所以,这里不谈。
        ...[但是我还是要把篇幅留下来]
        这里要谈的是BBR和Reno/CUBIC的一致性,这听起来可能让人觉得惊奇,它们不是有本质的区别吗?为什么要说它们的一致性呢?
        我特别感谢Van Jacobson这位大师。虽然他不认识我,我也没见过他,但是他提出的问题导致了Reno,CUBIC直到BBR的诞生,我估计Appex和微软这种只吃饭不拉屎的貔貅也是借鉴了他的思想。
        首先要声明,我并不是Google的粉丝,所以我更能采用公正的眼光看待BBR算法,虽然我一再强调它的多么多么的创新,但是这并不意味着BBR就是最好的,如果把BBR作为一个起点,类似Reno那样的起点,BBR本身也会有一个进化的过程,我希望的是大家都参与这个过程,我能做的只是抛砖引玉。我只是一个宣传者,一个鼓手。顺便说一句,我比较崇拜写出《大教堂与集市》并且会吹笛子的Eric S· Raymond,他自称自己是一名鼓手(为什么不是笛子手呢?)。
        我们先看一下Van Jacobson提出的一些的问题。
To achieve network stability, TCP entity should obey a ‘packet conservation’ principle, which is borrowed from physics.

What is packet conservation principle?
--A new packet is not put into the network until an old packet leaves( i.e. ‘conservation’) while maintaining ‘equilibrium’ in which a connection runs stably
by effectively using the bandwidth available on the path.


OK,理解这个是简单且直观的,然后呢?VJ继续说:
Three failures of packet conservation
  1. The connection does not get to equilibrium
  2. A sender injects a new packet before an old packet
      has exited
  3. The equilibrium can’t be reached because of  
      resource limits along the path

     1, 3 : Equilibrium problem     2 : Conservation problem

To fix those failures, three algorithm are introduced
     * Slow-start algorithm for 1.
     * Retransmit timeout estimation algorithm for 2.
     * Congestion avoidance algorithm for 3.

OK,问题提过了,方案也有了,接下来就是如何解决问题了,也就是说,如何把方案变成代码。

我们看一张图,一张到目前为止,BBR算法之前的TCP拥塞控制算法的图解,假设你对TCP拥塞算法有所了解那么这个图就是直观的:


技术分享


当然,这里并不包括快速重传/快速恢复算法。为什么?难道快速恢复不重要吗?不是不重要,而是,快速恢复属于上述经典图解的一个优化!我不是说过吗,算法是一个进化的过程,不管最终变得多么复杂,其根本是不会变的。在BBR之前,其根本就是上图所示。

        按照VJ的想法,TCP拥塞控制的根本就是实现上图中红色框框所框住的那些阶段的处理逻辑。我们先看看BBR之前是怎么处理的,这虽然并不重要,但看看毕竟不多:
cwnd = 1;
while(1) {
     send packets of min (cwnd, rwnd);                 // burst
     wait until receiving all ACKs for the previous sent packets         slow-start
     if ( timeout occurs )  break;      else   cwnd = 2*cwnd;
}
threshold = cwnd/2;    cwnd = 1;
while(1){
    if ( cwnd < threshold ){
        send packets of min (cwnd, rwnd);              //burst
        wait until receiving all ACKs for the previous sent packets      slow-start
        if ( timeout occurs ){ threshold = cwnd/2;    cwnd = 1;}
        else   cwnd = 2*cwnd;}
        if ( cwnd == threshold || cwnd > threshold )
            send packets of min (threshold, rwnd);     //burst
    } else if ( cwnd > threshold ){
        send a new packet whenever an ACK is received    //self-clocking
        if ( Sender receives all ACKs for the previous sent packets )
            {cwnd = cwnd + 1; send a new packet;}   //to probe more bandwidth
        if ( timeout occurs)
            {threshold = cwnd/2;    cwnd = 1;}          //to avoid congestion
    }
}
然而,还是VJ的话:
“The way we’ve always done it” is not necessarily the same as “the right way to do it”
太TMD的经典了!
然后,我们看下BBR是怎么做的。


技术分享


通过研究上面两个图,你能看出什么呢?
Reno/CUBIC:
它们是事件驱动的!无论是丢包,还是RTT增加,都被视为一种严重的事件,这些严重的事件导致TCP拥塞控制系统在”To find current bandwidth“,”To avoid congestion“以及
”To probe more bandwidth“之间切换,最终落实下来的就是促使拥塞算法(无论Reno,Vegas还是CUBIC)调整窗口的大小。
        那么谁来发现这些事件是否发生呢?答案是TCP拥塞控制状态机。拥塞控制状态机直接主导这些状态的切换,只要它发现丢包,不管是不是真的,都会拉低窗口值。
        所以说,Reno/CUBIC的窗口调整是被动的。
BBR:
bbr是反馈驱动的!bbr内置了自主的调速机制,不受TCP拥塞控制状态机的控制,bbr算法是自闭的,它可以自己完成VJ的所有状态探测以及切换,无需外界干涉,且对外界的干涉视而不见。
        bbr周期性的试图探测是否有更多的带宽,如果有,那么就利用它,如果没有,就退回到之前的状态。
        所以说,bbr的窗口调整是主动的。


        当你看到Reno/CUBIC和bbr的区别的时候,可能会想起中断和轮询的区别,bbr和轮询之间的不同点是,bbr有事实的反馈。


        好了,这就是Reno/CUBIC和bbr的区别,它们同样完成了”To find current bandwidth“,”To avoid congestion“以及”To probe more bandwidth“的逻辑,只是一个是事件驱动的被动实现,一个是反馈驱动的主动实现。和同事聊天时,在聊到高血压的时候,有一个很类似的事实:有一些人只有当觉得自己头晕的时候才会采取降血压的措施,另一些人则不断喝水并且少烟酒让自己血压维持在正常水平...

        本文的最后,我们来看一下bbr算法自身的一些话题。
        事实上,早在1981年的时候Gail & Kleinrock就发现了bbr采用的模型:
Rather than using events such as loss or buffer occupancy, which are only weakly correlated with congestion, BBR starts from Kleinrock’s formal model of
congestion and its associated optimal operating point.

然而,在当时和后续30年中,人们认为这是一件比较困难的事情,你怎么知道当前的带宽是不是最大的且RTT是最小的,要知道,带宽和RTT是相关的,它们的乘积就是BDP!直到最近,Google的bbr才意识到了一种非常简单的方法:
While it is impossible to disambiguate any single bandwidth or RTT measurement, a connection‘s behavior over time tells a clearer story.
有多么clearer呢?
bbr采用了一个时间窗口内的带宽测量和RTT测量,关键是这句话里面的”over time“!bbr算法之所以可以完成最大带宽和最小RTT的测量,关键在于以下的点:


技术分享


当到达最大带宽的时候,RTT开始增长(所有不以增加速率为目的的缓存都是耍流氓!缓存不直接增加速率,缓存通过降低丢包来提高网络利用率!),无论从RTT视图还是从带宽视图来看,两个操作点都是一致的,这是基本!那么bbr是怎么测量的呢?
        先稳定住带宽,当带宽不再增加的时候,bbr认为已经达到最大带宽可,然后在此基础上测量RTT,带宽的RTT的操作点是重合的!就是这么简单且直接。

        现在,你已经明白了,无论任何TCP拥塞控制算法,解决的都是一个问题(这个结论太简单了,简直就是废话)。这是方法不同而已。

        最后,附上一些话。
        除了算法级的优化,还有实现级的优化,比如如何利用当今的多核处理器,如何优化中断,如何优化锁...VJ曾经说过,现如今的TCP实现基本都是沿袭自BSD,而BSD又直接沿袭自Multics,然而Multics根本就是个古董。所以VJ说人们一贯的做法并不一定是正确的做法。回到bbr,作为TCP/IP协议最初的起草人之一,虽然VJ并不是bbr算法的直接实现者,但是VJ贡献的东西可能比任何其它人都要多,都要强。

        PS:昨晚在公司一个通宵,不是因为工作加班,是个人生活问题导致。半睡半醒中写完了本文,也算是给自己内疚的心打了一剂针剂。

TCP BBR算法与Reno/CUBIC的对比