一文解释清楚Google BBR拥塞控制算法原理

一文解释清楚Google BBR拥塞控制算法原理

BBR对TCP性能的提升是巨大的,它能更有效的使用当下网络环境,Youtube应用后在吞吐量上有平均4%提升(对于日本这样的网络环境有14%以上的提升):

报文的往返时延RTT降低了33%,这样如视频这样的大文件传输更快,用户体验更好:

不像CUBIC这种基于丢包做拥塞控制,常导致瓶颈路由器大量报文丢失,所以重新缓存的平均间隔时间也有了11%提升:

在Linux4.19内核中已经将拥塞控制算法从CUBIC(该算法从2.6.19内核就引入Linux了)改为BBR,而即将面世的基于UDP的HTTP3也使用此算法。许多做应用开发的同学可能并不清楚什么是拥塞控制,BBR算法到底在做什么,我在《Web协议详解与抓包实战》这门课程中用了6节课在讲相关内容,这里我尝试下用一篇图片比文字还多的文章把这个事说清楚。

TCP协议是面向字符流的协议,它允许应用层基于read/write方法来发送、读取任意长的字符流:

但TCP之下的IP层是基于块状的Packet报文来分片发送的,因此,TCP协议需要将应用交付给它的字符流拆分成多个Packet(在TCP传输层被称为Segment)发送,由于网速有变化且接收主机的处理性能有限,TCP还要决定何时发送这些Segment。TCP滑动窗口解决了Client、Server这两台主机的问题,但没有去管连接中大量路由器、交换机转发IP报文的问题,因此当瓶颈路由器的输入流大于其输出流时,便会发生拥塞:

这虽然是IP网络层的事,但如果TCP基于分层原则不去管,互联网上大量主机的TCP程序便会造成网络恶性拥堵。上图中瓶颈路由器已经造成了网速下降,但如果发送方不管不顾,那么瓶颈路由器的缓冲队列填满后便会发生大量丢包,且此时RTT(报文往返时间)由于存在长队列而极高。

如上图,最好的状态是没有队列,此时RTT最低,而State2中RTT升高,但没有丢包,到State 3队列满时开始发生丢包。

TCP的拥塞控制便用于解决这个问题。在BBR出现前,拥塞控制分为四个部分:慢启动、拥塞避免、快速重传、快速恢复:

慢启动在BBR中仍然保留,它的意义是在不知道连接的瓶颈带宽时,以起始较低的发送速率,以每RTT两倍的速度快速增加发送速率,直到到达一个阈值,对应上图中0-4秒。到该阈值后,进入线性提高发送速率的阶段,该阶段叫做拥塞避免,直到发生丢包,对应上图中8-11秒。丢包后,发速速率大幅下降,针对丢包使用快速重传算法重送发送,同时也使用快速恢复算法把发送速率尽量平滑的升上来。

如果瓶颈路由器的缓存特别大,那么这种以丢包作为探测依据的拥塞算法将会导致严重问题:TCP链路上长时间RTT变大,但吞吐量维持不变。

事实上,我们的传输速度在3个阶段被不同的因素限制:1、应用程序限制阶段,此时RTT不变,随着应用程序开始发送大文件,速率直线上升;2、BDP限制阶段,此时RTT开始不断上升,但吞吐量不变,因为此时瓶颈路由器已经达到上限,缓冲队列正在不断增加;3、瓶颈路由器缓冲队列限制阶段,此时开始大量丢包。如下所示:

如CUBIC这样基于丢包的拥塞控制算法在第2条灰色竖线发生作用,这已经太晚了,更好的作用点是BDP上限开始发挥作用时,也就是第1条灰色竖线。

什么叫做BDP呢?它叫做带宽时延积,例如一条链路的带宽是100Mbps,而RTT是40ms,那么

BDP=100Mbps*0.04s=4Mb=0.5MB

即平均每秒飞行中的报文应当是0.5MB。因此Linux的接收窗口缓存常参考此设置:

第1条灰色竖线,是瓶颈路由器的缓冲队列刚刚开始积压时的节点。随着内存的不断降价,路由器设备的缓冲队列也会越来越大,CUBIC算法会造成更大的RTT时延!

而BBR通过检测RTprop和BtlBw来实现拥塞控制。什么是RTprop呢?这是链路的物理时延,因为RTT里含有报文在路由器队列里的排队时间、ACK的延迟确认时间等。什么叫延迟确认呢?TCP每个报文必须被确认,确认动作是通过接收端发送ACK报文实现的,但由于TCP和IP头部有40个字节,如果不携带数据只为发送ACK网络效率过低,所以会让独立的ACK报文等一等,看看有没有数据发的时候顺便带给对方,或者等等看多个ACK一起发。所以,可以用下列公式表示RTT与RTprop的差别:

RTT我们可以测量得出,RTprop呢,我们只需要找到瓶颈路由器队列为空时多次RTT测量的最小值即可:

而BtlBw全称是bottleneck bandwith,即瓶颈带宽,我们可以通过测量已发送但未ACK确认的飞行中字节除以飞行时间deliveryRate来测量:

早在1979年Leonard Kleinrock就提出了第1条竖线是最好的拥塞控制点,但被Jeffrey M. Jaffe证明不可能实现,因为没有办法判断RTT变化到底是不是因为链路变化了,从而不同的设备瓶颈导致的,还是瓶颈路由器上的其他TCP连接的流量发生了大的变化。但我们有了RTprop和BtlBw后,当RTprop升高时我们便得到了BtlBw,这便找到第1条灰色竖线最好的拥塞控制点,也有了后续发送速率的依据。

基于BBR算法,由于瓶颈路由器的队列为空,最直接的影响就是RTT大幅下降,可以看到下图中CUBIC红色线条的RTT比BBR要高很多:

而因为没有丢包,BBR传输速率也会有大幅提升,下图中插入的图为CDF累积概率分布函数,从CDF中可以很清晰的看到CUBIC下大部分连接的吞吐量都更低:

如果链路发生了切换,新的瓶颈带宽升大或者变小怎么办呢?BBR会尝试周期性的探测新的瓶颈带宽,这个周期值为1.25、0.75、1、1、1、1,如下所示:

1.25会使得BBR尝试发送更多的飞行中报文,而如果产生了队列积压,0.75则会释放队列。下图中是先以10Mbps的链路传输TCP,在第20秒网络切换到了更快的40Mbps链路,由于1.25的存在BBR很快发现了更大的带宽,而第40秒又切换回了10Mbps链路,2秒内由于RTT的快速增加BBR调低了发送速率,可以看到由于有了pacing_gain周期变换BBR工作得很好。

pacing_gain周期还有个优点,就是可以使多条初始速度不同的TCP链路快速的平均分享带宽,如下图所示,后启动的连接由于过高估计BDP产生队列积压,早先连接的BBR便会在数个周期内快速降低发送速率,最终由于不产生队列积压下RTT是一致的,故平衡时5条链路均分了带宽:

我们再来看看慢启动阶段,下图网络是10Mbps、40ms,因此未确认的飞行字节数应为10Mbps*0.04s=0.05MB。红色线条是CUBIC算法下已发送字节数,而蓝色是ACK已确认字节数,绿色则是BBR算法下的已发送字节数。显然,最初CUBIC与BBR算法相同,在0.25秒时飞行字节数显然远超过了0.05MB字节数,大约在 0.1MB字节数也就是2倍BDP:

大约在0.3秒时,CUBIC开始线性增加拥塞窗口,而到了0.5秒后BBR开始降低发送速率,即排空瓶颈路由器的拥塞队列,到0.75秒时飞行字节数调整到了BDP大小,这是最合适的发送速率。

当繁忙的网络出现大幅丢包时,BBR的表现也远好于CUBIC算法。下图中,丢包率从0.001%到50%时,可以看到绿色的BBR远好于红色的CUBIC。大约当丢包率到0.1%时,CUBIC由于不停的触发拥塞算法,所以吞吐量极速降到10Mbps只有原先的1/10,而BBR直到5%丢包率才出现明显的吞吐量下降。

CUBIC造成瓶颈路由器的缓冲队列越来越满,RTT时延就会越来越大,而操作系统对三次握手的建立是有最大时间限制的,这导致建CUBIC下的网络极端拥塞时,新连接很难建立成功,如下图中RTT中位数达到 100秒时 Windows便很难建立成功新连接,而200秒时Linux/Android也无法建立成功。

BBR算法的伪代码如下,这里包括两个流程,收到ACK确认以及发送报文:

function onAck(packet) 
  rtt = now - packet.sendtime 
  update_min_filter(RTpropFilter, rtt) 
  delivered += packet.size 
  delivered_time = now 
  deliveryRate = (delivered - packet.delivered) / (delivered_time - packet.delivered_time) 
  if (deliveryRate > BtlBwFilter.currentMax || ! packet.app_limited) 
     update_max_filter(BtlBwFilter, deliveryRate) 
  if (app_limited_until > 0) 
     app_limited_until = app_limited_until - packet.size

这里的app_limited_until是在允许发送时观察是否有发送任务决定的。发送报文时伪码为:

function send(packet) 
  bdp = BtlBwFilter.currentMax × RTpropFilter.currentMin 
  if (inflight >= cwnd_gain × bdp) 
     // wait for ack or retransmission timeout 
     return 
  if (now >= nextSendTime) 
     packet = nextPacketToSend() 
     if (! packet) 
        app_limited_until = inflight 
        return 
     packet.app_limited = (app_limited_until > 0) 
     packet.sendtime = now 
     packet.delivered = delivered 
     packet.delivered_time = delivered_time 
     ship(packet) 
     nextSendTime = now + packet.size / (pacing_gain × BtlBwFilter.currentMax) 
  timerCallbackAt(send, nextSendTime)

pacing_gain便是决定链路速率调整的关键周期数组。

BBR算法对网络世界的拥塞控制有重大意义,尤其未来可以想见路由器的队列一定会越来越大。HTTP3放弃了TCP协议,这意味着它需要在应用层(各框架中间件)中基于BBR算法实现拥塞控制,所以,BBR算法其实离我们很近。理解BBR,我们便能更好的应对网络拥塞导致的性能问题,也会对未来的拥塞控制算法发展脉络更清晰。

我在《Web协议详解与抓包实战》第5部分课程中第15-20课对拥塞控制有更详细的介绍,详见下方课程二维码:

 

 

 

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注