【TCP】BBR拥塞控制算法

传统的拥塞控制算法是以丢包为驱动的拥塞控制算法,其实还有一种以带宽测量为驱动的谷歌(2016年提出的) BBR 拥塞控制算法。

我们先来看一个问题,大管道向小管道传输数据引发拥堵:

image

图中:

发送方的管道流量非常的大,但是瓶颈路由器向接收方发送的管道却是非常的窄。所以一定就会导致大量的报文积压等待在发送方的管道,实际上从很窄的瓶颈路由线路出来以后,虽然接收方的管道也很大,但是接收方的线路是跑不满的。

接收方收到回 ACK 的时候 ACK也是非常稀疏的,完全占不满带宽。

所以当出现丢包时,一定是在路由器R1开始丢包,此时会有两个问题:

  1. 发送方的 RTT 很慢,因为每一个报文都要在这里堵塞,等待大量的时间;

  2. 整体的带宽因为丢包导致的拥塞控制会进一步的下降;

传统的拥塞控制算法会有如下问题:

image

横坐标是时间,纵坐标是发送速率。基于慢启动快速的上升,但是实际的带宽没有那么大,很快发生了丢包。丢包以后进入快速重传/快速恢复,再次发生丢包,循环往复。这种场景下 RTT 很低,带宽也没有达到最高。

linux 2.6 内核以后引入拥塞控制算法:

image

Reno是应用最广泛且较为成熟的算法。该算法所包含的慢启动、拥塞避免和快速重传、快速恢复机制,是现有的众多算法的基础。CUBIC:拥塞控制算法。

它虽然更加平滑,但是由于同样是基于丢包来驱动,所以它也会带来 RTT 时延非常的大。

最佳控制点

--- 1979 Leonard Kleinrock 提出

基于丢包的拥塞控制点

  • 高时延,大量丢包
  • 随着内存便宜(各种路由器就会使用更大的内存,缓冲队列也会更大),时延更高

image

上面的图: Y轴:RTT(往返行程时间),X轴:data volume In-Flight(飞行中的数据量);在最开始应用进程还没有开足马力发送数据(慢启动刚开始),此时 RTT 是不变的,随着发送数据量的逐渐上升。直到达到了最大带宽以后,路由器就开始积压队列了,这时 RTT 开始变大。

下面的图:Y轴:Delivery Rate(带宽),X轴:data volume In-Flight(飞行中的数据量);一开始带宽上升,到达瓶颈后保持不变。

传统的算法是在丢包以后开始控制拥塞,其实应该在第一个点开始控制,就可以享受最大带宽,最小时延(RTT),最低的丢包率。

但是怎样才能测出这样的点呢?

在拐点之前的时间段内只能测量出 RTT 测量不出最大带宽。在拐点之后的时间段内只能测出 Bw(最大带宽) 测量不出 RTT。

最佳控制点

  • 最大带宽下
  • 最小时延
  • 最低丢包率

RTT 与 Bw 独立变化

  • 同时只有一个可以被准确测量

State-1: 其实我们核心的目标就是把路由器的缓存队列将为零,这个时候有任何报文来转发。我们立刻就可以发到链路中,它的效率是最高的。带宽可以最大,时延最小,丢包率最低。

State-2: 但是一旦开始积压队列以后,任何报文都要先积压一段时间才会发送出去,时延就上升了。

State-3: 当缓存队列满了之后就会出现丢包。

image

所以我们刚才说的最佳控制点就是:State-2;刚刚开始积压的这个点。

image

BBR 算法

全称:TCP Bottleneck Bandwidth and Round-trip propagation time

由 Google 于 2016 发布,Linux 4.9 内核引入, QUIC(协议) 使用

image

BBR 在 Youtube 上的应用: 吞吐量提升

BBR 在 Youtube 上的应用: RTT时延变短

BBR 在 Youtube 上的应用: 重新缓存时间间隔变长(丢包时会发生重新缓存,使用BBR 丢包的次数大幅度减少所以重新缓存时间间隔变长)

那么如何找到准确的最佳控制点?

image

BBR 如何找到准确的 RTprop 和 BtlBw:

RTT 里有排队噪声

  • ACK 延迟确认、网络设备(路由器缓存队列)排队

什么是 RTprop

去掉 RTT 里的排队噪声剩下的就是RTprop,物理属性:发送数据到接收数据整个链路的时间

如何测量出 RTprop

image

RTT(time) = RTprop(time) + 噪声(time)

经过多次反复测量:我们取噪声的最小值,就可以近似地得出 RTprop

如何测量出 BtlBw

BtlBw - 最大传输带宽

image

经过反复的测量取最大的发送速率,就近似地得到 BtlBw。

有了 RTprop 和 BtlBw 的值以后就可以根据上面的图找到最佳控制点。

基于 pacing_gain 调整

当 TCP 链路发生了变化,这样之前得到的 RTprop 和 BtlBw 由于链路变化而失效以后,发送端可以基于 pacing_gain 来调整。

  • 700 ms内的测量:BtlBw:10-Mbps,RTprop:40-ms链路

  • 如何检测带宽变大: 定期提升 pacing_gain

image

图中我们定期根据 pacing_gain 提升发送速率也定期的降低发送速率,在这样的过程中,如果链路发生变化,就可以测量出新的 RTprop 和 BtlBw 。

在提升 1.25 倍以后,测量带宽有没有变大,再用 0.75 倍看看带宽有没有变小。后面跟 6 个 1 倍后再次循环构成一个周期。

有了这样一个周期性变化的 pacing_gain 以后,当线路发生变换时 pacing_gain 的作用:

  • 20秒:10 Mbps,40-ms 升至 20 Mbps

  • 40秒:又降至 10 Mbps

image

图中在20秒时原先的 10 Mbps,40-ms 的线路突然转为 20 Mbps,这时由于 pacing_gain 的作用:首先用了 1.25 后拿到了更大的带宽同时 RTT 没有变小。虽然 0.75 也测试了一下,但是还是发现带宽变大了。每一个 pacing_gain 周期都在提升最大带宽。到二十一点几秒的时,带宽已升至 20 Mbps。

当第 40 秒时从 20 Mbps 降至 10 Mbps,此时我们在网络中飞行的报文数快速的增加,RTT也突然升的很高。在接近 42 秒的时候,重新执行到这个流程,降至 0.75 时发现 RTT 在大幅度下降,于是就使用了新的 RTprop 和 BtlBw 。重复 pacing_gain 的周期,逐渐把发送速率降了下来,适合了 10 Mbps。

收到 ACK 时

  • 更新 RTprop、BtlBw
function onAck(packet)
   rtt = now - packet.sendtime
   update_min_filter(RTpropFilter, rtt)  // 找出最小的 RTT,更新 RTprop 属性

   delivered += packet.size
   delivered_time = now
   deliveryRate=(delivered-packet.delivered)/(delivered_time-packet.delivered_time)

   if (deliveryRate > BtlBwFilter.currentMax || ! packet.app_limited) // 找出最大的 BtlBw
      update_max_filter(BtlBwFilter, deliveryRate) 
   if(app_limited_until > 0)
      app_limited_until =  app_limited_until - packet.size

发送数据时

  • pacing_gain: 5/4,3/4,1,1,1,1,1,1
function send (packet)
   bdp = BtlBwFilter.currentMax x
RTpropFilter.currentMin
   if(inflight >= cwnd_gain * bdp) // 超出速率那么就等一等再发
      // wait for ack or retransmiss 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)
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇