漫谈TCP BBR的收敛动力学(convergence dynamics)

蔚落 2022-11-08 05:55 189阅读 0赞

如果一个算法的某处说明没有数学支撑，那肯定是不能令人放心的，BBR的收敛性模型从来都是模糊的，不如AIMD那样直接，但还是有一些有意思的动力学过程在里面的。

在Neal Cardwell的github里藏着一篇关于BBR收敛动力学的文档 ***BBR bandwidth-based convergence*** ：  
[https://github.com/google/bbr/commit/c38ae279b67fe1e9b485903daa3f808f7c6e44d4][https_github.com_google_bbr_commit_c38ae279b67fe1e9b485903daa3f808f7c6e44d4]

这篇文档的结论是：

*  ***初始化带宽越小的流在up probe之后获得的加速比越大。***

该结论对应的截图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70]

以下是Neal的推导过程：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 1]

看完了这个推导，我在BBR的convergence region坐标里画了一个具体的收敛过程。

我自中学就喜欢各种几何，所以一有实际问题，我总喜欢把它们摆在一个坐标系里比划，我对在坐标系里解决问题的方法情有独钟，这也算是我的一种方法论。

首先我来解释一下convergence region坐标系各个元素的含义：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 2]

总带宽为1的约束下，设A，B两条流初始带宽分别为 a a a和 1 − a 1-a 1−a，则该状态在convergence region坐标系的坐标为 ( a , 1 − a ) (a,1-a) (a,1−a)，如果它们分别up probe一次，则它们将获得不同的带宽，于是便可以得到A，B两条流各自的带宽增量表达式。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 3]

> 注意，坐标系中各个点的坐标通过解析几何的各种方法很容易计算，比如直线求交点。

用变量 x x x替换 a a a，即 x x x为共享带宽为1的A，B两条流中A的带宽，两条流分别up probe之后，其各自带宽增量的函数表达式：

*  ***probing-increment function for A:***

f ( x ) = 0.25 x ( 1 − x ) 0.25 x + 1 f(x)=0.25\\dfrac\{x(1-x)\}\{0.25x+1\} f(x)=0.250.25x\+1x(1−x)

*  ***probing-increment function for B:***

g ( x ) = 0.25 x ( x − 1 ) 1.25 − 0.25 x g(x)=0.25\\dfrac\{x(x-1)\}\{1.25-0.25x\} g(x)=0.251.25−0.25xx(x−1)

用GeoGebra画出二者的图像：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 4]

很清楚地看到二者在 x = 0.5 x=0.5 x=0.5处相交，且关于 x = 0.5 x=0.5 x=0.5对称。当 x > 0.5 x>0.5 x>0.5时，B的带宽小于A，B的up probe加速比大于A，反之， x < 0.5 x<0.5 x<0.5时，B的带宽大于A，B的up probe加速比小于A。

下面是A，B两条流在ProbeBW状态的收敛过程(先不管ProbeRTT状态)：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 5]

不断收敛的BltBW坐标在convergence region坐标系中攀爬的典型过程如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 6]

这个ProbeBW状态下收敛过程的核心正是那个时间窗口内的max-filter函数，它可以让一条流继续使用已经被抢占的带宽继续up probe，这个正是Neal推导的那个带宽与加速比的负相关性得以运作的核心：

*  ***max BltBW是即时采集到的，但max BltBW的衰减是缓慢进行的，利用时间差来进行up probe的收敛。***

如果没有上述不对称的过程，假设BltBW的感知是即时的，当使用即时的BltBW去进行up probe的时候，事实上是不会收敛的：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 7]

这明显是一个MAMD(Multiplicative Increase and Multiplicative Decrease)过程，inflight按照乘性系数伸缩，收敛点永远在同一条直线上。

所以说，不能离开max-filter函数。这就是 ***Note that even after flow A probes, flow B’s estimated bandwidth would be a function of B’s max-filtered bandwidth samples, which would still include at least one round-trip of the rate “b”. So when sender B probes, it will be sending at a rate 1.25b.*** 这句话的直观解释。

max-filtered bandwidth samples意义重大。

虽然BBR在ProbeBW状态可以完成收敛，但为了确保BBR的正常运行，ProbeRTT状态是必不可少的，这个状态保证了RTprop的有效性。只要一个大象流进入了ProbeRTT状态，所有的流均将同时采集到RTprop，于是BBR天然地完成ProbeRTT状态的全局同步，而ProbeRTT之后即将进入ProbeBW之前，这里正是一个良好的收敛点，BBR在这里randomized了所有即将进入ProbeBW状态的流的ProbeBW phase，如此，BBR的收敛机制在这个几乎排空的管道里开始运行，someone probes for bandwidth while the other flow does not…

早些年，我不自量力地魔改BBR。

我随机化进入ProbeRTT的时间，却不知道如此便破坏了同步点后的公平收敛；我增加了两个cruise phase，却不知道这样就丢失了max-filter函数返回的max bw，ProbeBW状态的流再也无法收敛…

我们来看看在正确理论的指导下，如何调整gain系数。如果你不想要1.25了，那么换成多少好呢？如果比1.25大，会带来什么，如果比1.25小，又意味着什么？把增量函数画出来就明了了：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 8]  
最高的那一组是gain=1.95的增量函数，中间的是gain=1.25的增量函数，最下面的那一组是gain=1.05的增量函数，这意味着它们大约对应的pacing rate up probe增量为大约65%，20%，1%，你想收敛快一点吗？代价是什么呢？是不是很容易选择了。

此外，max-filter函数也是可调整的，维持10个RTT真的好吗？如果我换成2个，会带来什么？在convergence region坐标系中画个过程吧，一切都将呈现在眼前。

现在，我觉得下面这张图可以被解释了：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 9]

--------------------

浙江温州皮鞋湿，下雨进水不会胖。

[https_github.com_google_bbr_commit_c38ae279b67fe1e9b485903daa3f808f7c6e44d4]: https://github.com/google/bbr/commit/c38ae279b67fe1e9b485903daa3f808f7c6e44d4
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70]: /images/20221023/41d998f9022a41b68b6ce904376e284e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 1]: /images/20221023/029dcd195f414495a4a97bf78c36257c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 2]: /images/20221023/e15f68bb00ed4f48803c1855ffbfabbe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 3]: /images/20221023/93dd36ec527a4c78a428c0dc2dc49c79.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 4]: /images/20221023/beffa8c9dd0c440481da2851147d04e8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 5]: /images/20221023/19f0ea09771a4b4eb70f989cfb57e11b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 6]: /images/20221023/54022a14cd8846e2a50a53b2ae7aa222.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 7]: /images/20221023/a6f90266166f493fb12d364dd1b49eae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 8]: /images/20221023/d8fac30a9baf42dd9a37fc5041a5bea2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RvZzI1MA_size_16_color_FFFFFF_t_70 9]: /images/20221023/7d980f0accb44a7789b250ff176a5ba3.png