Google tcp拥塞控制 bbr算法 tcp拥塞控制reno算法

先说一下我的思路，由于我自从中学开始就是一个深度的数形结合控，希望能把一切都画在一个坐标系里，然后无非就是找最高点，最低点，找规律这些了，所谓求极值，展示特征无非也就是那些惯用的方法， 求导，积分，数列展开这些，所以对于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 wwRTT：tt ttInflight：ff ff临界的Inflight：fcfc f_cfc?

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

r={1f?fc?1f≤fcf>fcr={1f≤fcf?fc?1f>fc r =

{1f?fc?1amp;f≤fcamp;fgt;fc{1amp;f≤fcf?fc?1amp;fgt;fc

r={1f?fc??1?f≤fc?f>fc??

w={ffc1f≤fcf>fcw={ffcf≤fc1f>fc w=

?????ffc1amp;f≤fcamp;fgt;fc{ffcamp;f≤fc1amp;fgt;fc

w=????fc?f?1?f≤fc?f>fc??

很简单，方程组联立就可以消去变量ff ff。

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

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

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

因此，很显然，我给出下列的比值，最为衡量系统是否最优的度量：E=wtE=wt E=\dfrac{w}{t}E=tw?问题变成了 P(w,t)取在哪里，上述的比值E最大？

肉眼看得出来，ww ww取最大值wmax=1wmax=1 w_{max}=1wmax?=1，tt tt取最小值tmin=1tmin=1 t_{min}=1tmin?=1即可，即取点Pe(wmax,tmin)Pe(wmax,tmin) P_{e}(w_{max},t_{min})Pe?(wmax?,tmin?)，所谓的最优的EE EE值就是11 11，而此时，Inflight的值就是所谓的BDP=wmax×tmin=fc=1BDP=wmax×tmin=fc=1 BDP=w_{max} \times t_{min}=f_c=1BDP=wmax?×tmin?=fc?=1

这确实说明了Inflight取值为临界的恰好要使得队列增加的fcfc f_cfc?时，系统的效能真的是最优的。

如果你将P(w,t)P(w,t) P(w,t)P(w,t)在允许的定义域值域稍微偏离PePe P_ePe?点，你会发现EE EE值均会减少，这反映在TCP数据传输上，就是：

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

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

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

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

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

所谓的简化模型，即假设数据包是间隔均匀匀速到达的，数据包也是匀速经过网络节点设备的。但是在实际上，这并不是事实，真实的情况画在坐标系里并不是直线，而是曲线，类似下面的样子：

此时如果我们依然要求解E=wtE=wt E=\dfrac{w}{t}E=tw?的极大值，很显然要求这条曲线函数tt tt针对ww ww的导数，这下麻烦有点大！我怎么能知道带宽ww ww和传输时间tt tt之间的关系呢？显然，必须有二者之间的关系，才能求导啊！

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

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

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

```

E=wt=wf(w)E=wt=wf(w) E=\dfrac{w}{t}=\dfrac{w}{f(w)}E=tw?=f(w)w?进一步按照求导法则针对ww ww求导，推导如下：E'=w×df(w)dw?f(w)f2(w)E′=w×df(w)dw?f(w)f2(w) E\prime=\dfrac{w\times \dfrac{d f(w)}{d w}-f(w)}{f^2(w)}E′=f2(w)w×dwdf(w)??f(w)?若求EE EE的极大值，那么它一定出现在曲线的拐点处，其导数一定为00 00，因此：E'=w×df(w)dw?f(w)f2(w)=0E′=w×df(w)dw?f(w)f2(w)=0 E\prime=\dfrac{w\times \dfrac{d f(w)}{d w}-f(w)}{f^2(w)}=0E′=f2(w)w×dwdf(w)??f(w)?=0f(w)=w×df(w)dwf(w)=w×df(w)dw f(w)=w\times \dfrac{d f(w)}{d w}f(w)=w×dwdf(w)?

```

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

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

我是从初中开始就喜欢摆置坐标系的，一直到大学，几乎任何数学题，我都能采用数形结合的方案一题多解，某种程度上，我老婆就是当时我如此炫技追到的…最近几年，我用同样的方式设计了iptables的优化方案，DxR的优化方案…不多的几次失败包括Bloom Filter的形象化展示。

所以面对上述的表达式子，依然可以任意把玩。式子两边同时除以ww ww：f(w)w=df(w)dwf(w)w=df(w)dw \dfrac{f(w)}{w}=\dfrac{d f(w)}{dw}wf(w)?=dwdf(w)?

看看左边右边分别是什么？

• 左边：f(w)f(w) f(w)f(w)上任意一点到原点的直线的斜率；
• 右边：曲线f(w)f(w) f(w)f(w)上任意一点切线的斜率。

两个斜率一致的时候，ww ww取值计算的EE EE是最优的，即 曲线f(w)f(w) f(w)f(w)上任意一点PP PP和原点之间的直线与该点的切线共线！ 的时候，该点PP PP的ww ww和tt tt的取值为最优！

形象地看，我们可以通过 操作 来获取最优的点，即：从经过原点的t=0这条直线开始，任其绕着原点逆时针旋转，第一次切到曲线f(w)f(w) f(w)f(w)的那个点，就是最优点。

很简单，是吧。

现在已经定性地把问题解决了，无论曲线t=f(w)t=f(w) t=f(w)t=f(w)长什么样子，我们可以从上述的操作步骤中获取最优的PP PP点，进而求出Inflight值，最终确定Cwnd。

然而，这并不能定量地分析，如果要定量地分析，则必须要有t=f(w)t=f(w) t=f(w)t=f(w)的表达式。

这个表达式何来？我花了好长时间也没有思路。

再仔细看看带宽和RTT之间的关系，在固定的带宽下，RTT受到Inflight的影响，然而Inflight正是我们要求解的，这貌似进入了一个循环，消除Inflight变量并无法确定二者的关系，这便是陷入了两难！

…

我略过了好多文字，这些文字描述了大概将近一个月的见闻，然后我就想到了 排队论， 排队论， 排队论， 排队论， 排队论！

排队论基于概率理论给出精确的逗留时长和到达率以及服务率之间的关系。

排队论是一个复杂的理论，能写几大部头都写不完，我自己也只是略懂一二，并不是专门研究这个的，所以本着解决手头当前问题的广度优先原则，下面我依据排队论的一些结论性的公式进行推导，关于这个公式的推导，我会在本文后面给出一个附录。

我们依然根据最简单的情况建立模型，即经典的M/M/1排队模型下的场景，在该场景下，先设以下的变量：

• 到达率：λλ \lambdaλ
• 服务率：μμ \muμ
• 系统负荷水平：ρρ \rhoρ
• 用户停留时间：WsWs W_sWs?

然后，有一些用到的定义以及公式，我们根据这些公式来进行后续的关于BBR最优化的证明。需要声明的是，M/M/1排队模型是一个简化的模型，并不代表现网中运行BBR算法的TCP传输发包特征就一定符合这个模型，但这是一个很好的开始。

这些结论性的定义和公式如下：

• 系统负荷水平
  ρ=λμρ=λμ \rho=\dfrac{\lambda}{\mu}ρ=μλ?
• 用户停留时间(包括排队时间和被服务的时间)
  Ws=1μ?λWs=1μ?λ W_s=\dfrac{1}{\mu-\lambda}Ws?=μ?λ1?
• 当前系统中用户数(包括排队的和正在被服务的)
  Ls=λμ?λLs=λμ?λ L_s=\dfrac{\lambda}{\mu-\lambda}Ls?=μ?λλ?
• 排队等待时间
  Wg=λμ×(μ?λ)Wg=λμ×(μ?λ) W_g=\dfrac{\lambda}{\mu \times (\mu-\lambda)}Wg?=μ×(μ?λ)λ?
• …

有了这些，便可以建立BBR的模型了。

在一个带宽固定的网络中，我们假设带宽为CC CC(基于这种固定带宽的假设，实际上这是M/D/1排队模型，但是推导过程并无伤大雅！)，而我们发送的带宽可以理解为 到达率， 即λλ \lambdaλ，此时我们可以把WsWs W_sWs?等效于RTT，因此RTT和带宽的关系则为：

RTT=f(λ)=Ws=1μ?λ=1C?λRTT=f(λ)=Ws=1μ?λ=1C?λ RTT=f(\lambda)=W_s=\dfrac{1}{\mu-\lambda}=\dfrac{1}{C-\lambda}RTT=f(λ)=Ws?=μ?λ1?=C?λ1?

根据我们上面的那个最优解公式：

f(λ)=λ×df(λ)dλf(λ)=λ×df(λ)dλ f(\lambda)=\lambda \times \dfrac{d f(\lambda)}{d \lambda}f(λ)=λ×dλdf(λ)?

带入则有：

f(λ)=λ×df(λ)dλ=1C?λf(λ)=λ×df(λ)dλ=1C?λ f(\lambda)=\lambda\times \dfrac{d f(\lambda)}{d \lambda}=\dfrac{1}{C-\lambda}f(λ)=λ×dλdf(λ)?=C?λ1?

而这里的df(λ)dλdf(λ)dλ \dfrac{d f(\lambda)}{d\lambda}dλdf(λ)?则可以对f(λ)f(λ) f(\lambda)f(λ)简单求导：

df(λ)dλ=1(C?λ)2df(λ)dλ=1(C?λ)2 \dfrac{d f(\lambda)}{d\lambda}=\dfrac{1}{(C-\lambda)^2}dλdf(λ)?=(C?λ)21?

代入则有了结论：

λ(C?λ)2=1C?λλ(C?λ)2=1C?λ \dfrac{\lambda}{(C-\lambda)^2}=\dfrac{1}{C-\lambda}(C?λ)2λ?=C?λ1?λ=C?λλ=C?λ \lambda=C-\lambdaλ=C?λλ=C2λ=C2 \lambda=\dfrac{C}{2}λ=2C?

最终，我们发现了最有点PP PP，即：

P(C2,2C)P(C2,2C) P(\dfrac{C}{2},\dfrac{2}{C})P(2C?,C2?)

这个结论有什么用呢？它意味着什么呢？

我们再来看M/M/1模型中的另外一个公式，即计算当前系统的用户数：

Ls=λμ?λ=C2C?C2=1Ls=λμ?λ=C2C?C2=1 L_s=\dfrac{\lambda}{\mu-\lambda}=\dfrac{\dfrac{C}{2}}{C-\dfrac{C}{2}}=1Ls?=μ?λλ?=C?2C?2C??=1

这意味着系统中只有一个用户，这意味着没有排队！！这意味着最优的情况，即EE EE最大的时候，系统是没有队列堆积的！这个时候，我们来计算一下BDP：

BDP=λ×f(λ)=C2×2C=1BDP=λ×f(λ)=C2×2C=1 BDP=\lambda\times f(\lambda)=\dfrac{C}{2}\times \dfrac{2}{C}=1BDP=λ×f(λ)=2C?×C2?=1

正解于天下！这也是我在这方面工作的一个里程碑，现在总结一下就是：在M/M/1排队模型的假设下，BBR拥塞控制算法是效能E最优的。

然而，M/M/1模型只是一个开始，事实上，基于端到端的TCP协议，在链路上会经过非常多的中间节点，即，至少起码的，我们也要在M/M/k排队模型上再次证明上述结论的正确性才行。

而这是简单的。

我们假设一个端到端的链路上有kk kk个中间节点，那么每一个节点都遵循M/M/1排队模型的法则，综合起来就是M/M/k了，我们假设这些节点的处理能力并不相同，并假设其中有一个能力最弱的节点m，其处理能力μmμm \mu_mμm?，在排队论模型中，只要有排队现象，就会增加时延而降低效能E，所以为了不排队每一个节点的到达率均要满足：λk≤μm2λk≤μm2 \lambda_k \le \dfrac{\mu_m}{2}λk?≤2μm??，所以最终的系统中的用户数是要小于kk kk的，这就是说，系统的吞吐是由最弱的节点决定的这个典型的漏桶理论。

我们来看BBR的名称，Bottleneck Bandwidth and RTT，其中以 Bottleneck Bandwidth 为M/M/k排队模型的依据保证了RTT不会因为排队引入的延迟而增加。

换句话说，BBR拥塞控制算法告诉你，别发太多包，超过Bottleneck Bandwidth的限额，你多发了也过不去，还平添时延，因为已经偏离了最优的操作点！

算法是OK的，代表了一种正确的方法，退一步，至少可以说是一种引向正确方法的趋势。然而在实现上，它的根基在于 测量的准确性。算法实现的具体实施过程中，TCP协议固有的不可测量性是最大的掣肘，而这是TCP的固有缺陷所导致，永远也无法被解决！

那么QUIC的实现呢？我准备花大力气测测看。

在很早之前介绍BBR算法的文章中，我提到了 带宽和RTT互为正交 的概念：Google’s BBR拥塞控制算法模型解析：https://blog.csdn.net/dog250/article/details/52895080

现在我们可以基于本文上述的关于最优化的结论再来理解这个 正交。

先从固定的D/D/1排队模型看，我们再看BW vs RTT图：

我们可以看到最优点PePe P_ePe?处，带宽和RTT的乘积正好是矩形的面积，而它就是BDP，无论你在折线上怎么移动PP PP点，你均无法获得更大的矩形面积，往左移动，面积减少，这意味着不够，效能当然低，往上移动，面积不再增加，这说明多发数据包也没用，并不能增加有效BDP。

好完美的既视感！貌似打消了任何企图通过多发包来提升性能的念头，然而突然发现这只是理想D/D/1排队模型下的结论。

稍微真实点的M/M/1排队模型下，是这样子的：

你会发现，在最优化点附近，还是可以 通过比较小的RTT增加的代价，获得更多有效BDP的。这似乎给了人们稍微增加一点Cwnd以理由和意义。黑暗压下来的时候，总是留下一丝的光亮，没有办法。

通过相对严格的数学推导，我们发现BBR算法在BW vs RTT坐标系的曲线上的操作点确实是最优的，然而我们又从同样一张图的M/M/1表述中发现了一点可以利用的Trick…

不管怎么说，不想排队是为了自己，然而制造排队则是毁了大家，你能控制的，仅仅是自己不排队，这是个博弈，答案却非常简单！

如此简单的数学推导，展示了事实，那么，为什么路由器和交换机还要设计队列缓存呢？

从商业的角度，如今的存储设备越来越便宜，更多的缓存可以换取更多的 不丢包指标，极低的代价换一个噱头。

从工程的角度来看，队列不仅仅是 为了缓存多出来的数据包，更多的是一种主动式的管理设施，比如流量整形，按照不同的产品进行限速，优先级管理等等。

最后，从数学上看，假设数据包到达行为是泊松到达，其到达率期望是λλ \lambdaλ，那么为了获得最佳的效能，其服务率必然是2λ2λ 2\lambda2λ，但是这些都是统计分布，到达率的期望只是一个均值，在可计算的概率下，到达率完全可以达到3λ3λ 3\lambda3λ，4λ4λ 4\lambda4λ…为了吸收这些统计峰值，则必须设计队列缓存。

现在的问题是转发节点设备上的缓存要设计多大？有了BW vs RTT这张图，这是可以计算出来的！

我们依然假设这个模型是简单的M/M/1排队模型。我将D/D/1模型和M/M/1模型放在一张图里解释：

虚线和橘黄色真实的实线围成部分的面积就是节点需要的缓存的大小(事实上要稍微大一点，毕竟这里的RTT也是均值)，因为它在泊松到达的正常波动范围内。

此外根据本文上面的推论，当λ=μ2λ=μ2 \lambda=\dfrac{\mu}{2}λ=2μ?的时候，系统的效能E最大，在上图中，这也是可以解释的：

其中蓝线围成的区域面积为 最佳的BDP，这个是和D/D/1模型不同的。

由于泊松到达的统计效应造成了不可避免的排队和空转，且二者不能抵消，因此必须设计缓存队列，曲线相对t=1t=1 t=1t=1往上下凸了，因此从原点出发相切于t=f(λ)t=f(λ) t=f(\lambda)t=f(λ)的切线肯定在λ=μλ=μ \lambda=\muλ=μ的左边，这意味着相对于D/D/1模型，M/M/1模型在其它条件都相同的情况下，损失了一点Inflight！这是统计的不确定性带来的不可消除的代价！

所以说，在非主动管理的意义上，队列的作用是什么？队列的作用是，平滑泊松到达的统计特性引发的突发。突发总是存在的，为了能容忍这些突发， 而不至于丢包。

从示意图上看，即便是BBR，也是无法100%避免排队的，这是泊松到达的统计特征决定的，即便单一服务节点的服务率μμ \muμ是到达率λλ \lambdaλ的1000倍(而不是计算出来的最优值2倍)，也会有小概率的突发会造成轻微排队。故而，队列算是一个基础设施，必不可少，但你要明白，队列是用来干嘛的！

然而，还有一个话题，与统计突发概率相等的对称的现象就是系统空转，而空转是无法弥补的，没有任务到达，系统确实什么也做不了。因此，引入主动队列管理是必要的，上一时间周期来不及处理的任务通过缓存队列推迟到下一个时间周期，填补空转期，这方面，我觉得带突发的令牌桶这个设计，简单又直接。

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

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

事实上，我们的传输速度在3个阶段被不同的因素限制：

1、应用程序限制阶段，此时RTT不变，随着应用程序开始发送大文件，速率直线上升；

2、BDP限制阶段，此时RTT开始不断上升，但吞吐量不变，因为此时瓶颈路由器已经达到上限，缓冲队列正在不断增加；

3、瓶颈路由器缓冲队列限制阶段，此时开始大量丢包。

宏观背景下的BBR

1980年代的拥塞崩溃导致了1980年代的拥塞控制机制的出炉，某种意义上这属于见招拆招的策略，针对1980年代的拥塞，提出了1980年代的拥塞控制算法，即ss，ssthresh，congestion avoid这些。

说实话，这些机制完美适应了1980年代的网络特征，低带宽，浅缓存队列，美好持续到了2000年代。

随后互联网大爆发，多媒体应用特别是图片，音视频类的应用促使带宽必须猛增，而摩尔定律促使存储设施趋于廉价而路由器队列缓存猛增，这便是BBR诞生的背景。换句话说，1980年代的CC已经不适用了，2010年代需要另外的一次见招拆招。

如果说上一次1980年代的CC旨在 收敛，那么这一次BBR则旨在 效能E最大化，这里的E就是本文上面大量篇幅描述的那个E，至少我个人是这么认为的，这也和BBR的初衷 提高带宽利用率 相一致！