Google BBR拥塞控制算法背后的数学解释 - Go语言中文社区

Google BBR拥塞控制算法背后的数学解释


杭州待了一段时间,回到深圳过国庆假期,无奈温州皮鞋?厂老板过节要回温州和上海,不在深圳,也就没有见着,非常遗憾!

国庆节当天,就写这个了。经理不会弹琴,但是经理会弹琴。

我原本可能会在想国庆节的凌晨到大清早写点什么呢,现在不用想了,就写BBR拥塞控制算法背后的数学吧,这个事情我是在杭州回深圳的路上突然找到了最终结果的,我必须把它记录下来。其实在找到这个结果之前,很久很久,我就在思考这个问题了。

背景和动机

2016年大概十月中下旬,同事推荐了一个视频:
Making Linux TCP Fast
https://www.youtube.com/watch?v=hIl_zXzU3DA
跟随视频后的链接netdevconf的链接,还有一些slides和paper可以看:
https://netdevconf.org/1.2/session.html?yuchung-cheng
我也是那时,或者更早些一点,大概九月份的时候,接触了Google的BBR算法,应该算是国内第一批次的了,随后的一段相当长的时间,我对该算法进行了相对深入的剖析以及思考,从解释Paper,分析源码,设计到优化,反正不知花了多少周五的通宵。

随着后续这个BBR算法的逐渐普及,加入讨论的人也越来越多了,从最初的如何用起来到后面的各路大神的各路神技,可谓热闹非凡,我当时讲,TCP被你们玩坏掉了,BBR也难逃劫难…

和CUBIC背后那精湛简介的数学收敛模型不同,BBR是基于测量的一个算法,它甚至没有一个数学上的解释以证明 为什么这样做就是最好的,以至于,很多人开始盲改,最终的效果和自己的预期,当然是大相径庭。

我一直在思考BBR背后的数学,我总觉得能用数学公式表达的东西才是真正确定的,所以我希望在我长时间思考后,能有一个数学上的解释,来解释BBR为什么是高效率的,为什么只能这样做。

这几天,我感觉成功了一点,所以不敢独享这回报,写此文以分享。


插曲

先来个插曲。

很多人看到BBR不排队的特征后,第一想到的就是 不排队甚好,但稍微在缓存队列里堆点数据包也不错,不然怎么能赢了那些不守规矩的流呢? 于是乎就出现了各类所谓的 BBR优化,无一例外地都是把Reno/CUBIC那一套算法的 精髓 照搬到BBR,于是BBR就被玩坏了!

我也干过这种事,后来我跟BBR的作者Neal Cardwell交流,他告诉我 这增加了算法的复杂性,并且破坏了BBR的根本

我退出了 BBR优化队伍,我也不玩了,我潜下心希望能 从数学上证明BBR不排队就是最优的,只要排队就不行,一点队列也不行。本文写作前一天,我得了一些结论。记录这些结论并记录我是怎么想的,就是本文的主要内容。

温州皮鞋厂老板促使我开了场,让我第一次用数学来描述BBR算法。

当时是要计算一下 ***为什么BBR在Startup阶段的gain是2ln2dfrac{2}{ln 2}https://blog.csdn.net/dog250/article/details/80780346

现在,正文开始。


正文

先说一下我的思路,由于我自从中学开始就是一个深度的数形结合控,希望能把一切都画在一个坐标系里,然后无非就是找最高点,最低点,找规律这些了,所谓求极值,展示特征无非也就是那些惯用的方法, 求导,积分,数列展开这些,所以对于BBR算法,我依然循着这样的思路。

现在要做的,就是怎么把BBR的行为画在一个坐标系里。如果这一步做到了的话,我相信以我20年的经验顺水推舟事情就一定能成。

其实,BBR最初的slides和paper中,不断展示的图示是下面这个:
在这里插入图片描述
然后,我仔细观察了这两个坐标系,分别是BW(其实是Deliveryrate) vs Inflight以及RTT vs Inflight,都有Infligh。其实,这两张图是用于展示BBR特征的,它只说了What,并没有解释Why,实际上,难道Inflight不应该是 计算出来的 吗?如果说我能根据另一个坐标系的曲线进行一系列计算,最后 推导出Inflight的值必须是那个值才能达到某种最优的效果,那就解释了Why。

就是这个思路。让我们一步一步去做。

既然我们把Inflight当成了一个结果而不是原因,为了找这个原因,我们合并两个坐标系,消去公共的Inflight,那么我们就可以得到RTT vs BW的曲线了!

为了数学上表述的方便,后面统一一下符号:
BW:ww
RTT:tt
Inflight:ff
临界的Inflight:fcf_c

下图是消去ff的方法:
首先给出图像的方程表示:

r={1ffcffc1f>fcr = begin{cases} 1 & f le f_c \ f-f_c-1 & f>f_c end{cases}

w={ffcffc1f>fcw= begin{cases} dfrac{f}{f_c} & f le f_c \ 1 & f>f_c end{cases}

在这里插入图片描述
很简单,方程组联立就可以消去变量ff

我们可以看到,最终wwtt的取值范围就是那条开向第二象限的折线,现在的问题是,在这条折线中,P(w,t)P(w,t)在哪里是最优的,而此时的Inflight值就是最适合灌进网络中的数据包的数量,换句话说,它反映了Cwnd应该取什么值。

问题转化为了 如何度量所谓的最优

一般工业界和经济学领域都会采用 ***产出/成本***的比值来衡量一个系统是不是优秀,换句话说就是 最优的系统是用最少的代价换取最高的收益。对于我们目前的模型而言,用语言来表达,即 最少的时间传输最多的数据包

因此,很显然,我给出下列的比值,最为衡量系统是否最优的度量:
E=wtE=dfrac{w}{t}

肉眼看得出来,ww取最大值wmax=1w_{max}=1

这确实说明了Inflight取值为临界的恰好要使得队列增加的
fcf_c

在这里插入图片描述

如果你将P(w,t)P(w,t)在允许的定义域值域稍微偏离PeP_e

  1. 要么带宽没有用满,没有达到wmaxw_{max}
  2. 要么带宽超额了,数据排队了,数据到达的太快,因此延迟增加了;

无论发生了上述的什么情况,显然都不是什么好事。

这算完成了任务吗?证明了BBR是最优的。看起来算是吧…


如果这样就算是一个BBR背后完备的数学模型,这篇文章一个多月前就能写出了。。。


我们发现,上面的推导基于一个明显的事实,即 用肉眼看,之所以可以用肉眼观测出最值,那是因为Yuchung Cheng和Neal Cardwell在描述BBR算法时,简化了模型,基于简化的模型,才给出了那两幅BW vs Inflight和RTT vs Inflight的坐标图示,在这两个图示中,所有的线均为直线。

所谓的简化模型,即假设数据包是间隔均匀匀速到达的,数据包也是匀速经过网络节点设备的。但是在实际上,这并不是事实,真实的情况画在坐标系里并不是直线,而是曲线,类似下面的样子:
在这里插入图片描述
此时如果我们依然要求解E=wtE=dfrac{w}{t}

怎么办?这件事让我搞了一个多月时间!

我能理解数据包的到达其实是柏松到达,被服务时间符合指数分布特征,但是我并没有就着这个思路思考下去(不然我一定能想到排队论),而是希望能先有一个通用的解。

起初,我是反着求解,我假设传输时间tt已经可以用带宽ww来表示,即
t=f(w)t=f(w)

这便是最终的关系式,虽然我不知道tt如何用ww来表示,但这个关系是存在的,这是个普遍适用的关系。

我为得到这个关系式兴奋了一个周末,非常有成就感,虽然它现在看起来很简单,但在当时,这个想法真的显得来得太晚!

我是从初中开始就喜欢摆置坐标系的,一直到大学,几乎任何数学题,我都能采用数形结合的方案一题多解,某种程度上,我老婆就是当时我如此炫技

版权声明:本文来源CSDN,感谢博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/dog250/article/details/82892267
站方申明:本站部分内容来自社区用户分享,若涉及侵权,请联系站方删除。

0 条评论

请先 登录 后评论

官方社群

GO教程

猜你喜欢