keep the pipe Just full But no fuller - BBR 与尘封 40 年的求索

推荐一部短视频 Keep the pipe just full, but no fuller，作者就是大名鼎鼎的 L. Kleinrock，现代分组交换网的奠基人，这里有关于他这个人的介绍：

https://www.lk.cs.ucla.edu/index.html

https://en.wikipedia.org/wiki/Leonard_Kleinrock

这视频对应的论文是 Keep the Pipe Just Full, But No Fuller。

我写这篇推荐的缘由有几个：

• 我曾推荐过 Jaffe 的论文，证明最佳操作点不可达，但 BBR 获得了突破，就想挖一下坟；
• 我对排队论非常感兴趣，那就必须读 Kleinrock，他恰是用排队论建模网络的泰山北斗；
• 我迷历史，从 Kleinrock 处可以学到很多，自古看今知未来，这对设计更好的技术有用；
• 我曾经写过好多论证和寻找 “最佳操作点” 的博客，是时候总结一下了；
• 我很喜欢摆弄坐标系；
• …

作为始于 1960 年代的互联网奠基者，Kleinrock 目睹了一切(自他发表论文到他母亲扎进互联网直到 90 多岁高龄去世)，我们耳熟能详的另外几个创造者都是他的同事或学生，他抱怨道，互联网上后来出现了很多拥塞控制算法用来避免崩溃，但无论哪种，全部呈现了某种锯齿形态，不断碰到天花板，又不断跌落，同时引入大量延迟，这种情况已经持续了 40 年。如下图所示，他表示这些算法都围绕在 α 附近折腾 buffer，正确的操作点应该在 β：

Kleinrock 坦言来自 Google 的 BBR 在 40 年后开始改变这一切，但紧接着，Kleinrock 略带自夸的口吻宣传，BBR 的点子自己早在 1978 年就找到了，他找到了如今被称作 kleinrock’s operating point，即最佳操作点，但却无人问津，因为另一个叫做 Jaffe(也是一位大佬) 的人否定了它：

Jaffe 的论文如下：Flow Control Power is Nondecentralizable：

这导致拥塞控制研究方向的改变，从分布式流控转向了 AIMD 收敛，这就是那些锯齿算法的渊源。
随后，Kleinrock 给出了 BBR 的方法，核心点在于 BBR 采用了状态机管理了两个滑动窗口，分别控制 maxbw(BltBw) 和 minrtt(RTprop)：

再往后的内容是一个理论体系，即如何用排队论建模，证明最佳操作点的存在，它的性质，以及找到它的方法。

Kleinrock 提出一个功率 P(即 Power) 概念，其最大值作为我们应追求的理想指标，该指标脱离了如吞吐，时延等单一指标的不可同时测量性，将整个网络作为一个排队系统整体全盘考虑。

P 的大意是让相互交易掣肘的，作为分子越大越好的收益和作为分母越小越好的成本相除，求整体的最大值，这就是最佳操作点，如下截图给个梗概：

我将用文字表述如下。这部分也是我个人的总结，此前零散分布在各处。本文我将用自己的逻辑将这些东西串起来。

按照排队论约定，$\lambda$ 表示到达率，$\mu$ 表示服务率，$\rho =\frac{\lambda }{\mu }$ 表示资源利用率，设等待时间为 $T(\rho )$，归一化消除单位后为 μT(ρ)，表示 1 个任务在系统中消耗的时间相当于多少个服务周期。

现在着手建立资源利用率 $\rho$ 和归一化等待时间 $\mu T(\rho )$ 的关系。按照 Kleinrock 的定义，功率 P 如下表示：

$P(\rho )=\frac{\rho }{\mu T(\rho )}=\frac{\rho }{T_{\mathrm{normalized}}(\rho )}$

跟我的定义 “效能 E” 一致，分母越大越好，分子越小越好，我们希望 P 尽可能大。

不对系统做任何假设，对于任意系统 $P^{\prime }(\rho )=0$ 处取得最值，按求导法则一步一步走(参见我的另一篇总结，写于 2018 年的 BBR 数学解释)，在 $P^{\prime }(\rho )=0$ 处需满足:

$T_{\mathrm{normalized}}(\rho )=\rho \cdot \frac{\mathrm{d}{T}_{\mathrm{normalized}}(\rho )}{\mathrm{d}\rho }$

整理得到：

$\frac{T_{\mathrm{normalized}}(\rho )}{\rho }=\frac{\mathrm{d}{T}_{\mathrm{normalized}}(\rho )}{\mathrm{d}\rho }$

左边是 $T_{\mathrm{normalized}}(\rho )$ 上任意一点到原点的直线斜率，右边是 $T_{\mathrm{normalized}}(\rho )$ 上任意一点切线的斜率，两个斜率相等，意味着经过原点，与 $T_{\mathrm{normalized}}(\rho )$ 相切的切点处取得 P 的最大值。

这是一个普遍的惊人结论，对任意排队系统均适用，推导过程不依赖任何具体表达式。现在来看看它的直观意义。

求 P 的极值，几何等价于求原点连接切点得切线斜率，定量化则等价于求曲线 $T_{\mathrm{normalized}}(\rho )$ 上任意一点横坐标和纵坐标商的极值，以更具普遍性的 M/G/1 排队系统量化它是高尚的。由 Pollaczek-Khinchine 公式，M/G/1 平均响应时间 T(ρ) 为：

$T_{\mathrm{normalized}}(\rho )=\mu T(\rho )=1+\frac{\rho (1+C_b^2)}{2(1-\rho )}$

其中 $C_b$ 为变异系数。以更熟悉的 x，y 表示，等价于：

$P=y=\frac{x}{(1+x(1+a)/(2-2x)}$

求助 DS，当 P 取最大值时，P = y = x²，仔细看这意味着什么。

根据 Liittle’s law，系统中任务数 $N=\lambda \cdot W=\rho \cdot \mu T(\rho )$，如果 P 取最大值 x²，则 $\mu T(\rho )=\frac{1}{\rho }$ 带入 N 得到 N = 1.

这证明了当 P 最大时，系统中只有 1 个任务，这就是 “最佳操作点”，也叫最佳工作点，换句话说，系统中只有 1 个任务，不排队就最高效。

用经典得 M/M/1 系统验算一下。

归一化等待时间在 M/M/1 系统为 $\mu T(\rho )=\frac{1}{1-\rho }$，因此 $P=\frac{\rho }{\mu T(\rho )}=\rho \cdot (1-\rho )$，这是个二次曲线，$\rho =0.5$ 时，系统中平均有 1 个任务，P 取最大值 0.25。

仔细观察 M/M/1 验算式，P 表达式的是 “系统在利用率 $\rho$ 下的 ‘有效吞吐效率’”，即服务器繁忙且系统未拥塞的概率，对应恰好有 1 个顾客的概率。这个概率表明，资源利用率被均匀摊派在等待时间中，等待时间越久，单位时间利用率越低。

M/M/1 系统的 P 取最大值时，有效利用率相比服务率降低了 0.5，而等待时间却增加了 1 倍，这多少有点反直觉，但却很容易直观理解。

M/M/1 系统泊松分布可以看作一个对称的钟形，下图解释了为什么利用率降低了一半，等待时间增加了一倍：

统计复用系统中平均 1 个任务和恰好 1 个任务很不同，$\rho =0.5$，意味着有一半时间系统中少于 1 个任务，浪费的那一半资源服务时间无法积累，另一半时间系统中多于 1 个任务，排队时间又无法预支，这一拉一推的坏事叠加，就是统计系统的代价。

再用 BBR 验算。BBR 的 P 定义为 P = bw/rtt，显然，当 bw = maxbw，rtt = minrtt = RTprop 时，P 取最大，该操作点就是不排队的最优操作点。实际上 BBR 模型去除了网络的统计波动从而简化了问题，以至于用排队论解释， BBR 就是一个 D/D/1 排队系统的描述。

在 Kleinrock 的论文中，BBR 作为有限资源确定性模型(Finite Resource Deterministic Model) 的实例呈现：

Kleinrock 在坐标系中给出了变异系数不同的各类 M/G/1 排队系统的 $\rho \sim \mu T(\rho )$ 曲线，展示了其共性，即 “在平均任务 N* = 1 处获得最大功率 P”：

为了在一张图中直观地看到任意变异系数排队系统的最佳操作点以求得对应的 $\rho$，Kleinrock 巧妙地做了坐标变换，将归一化的纵坐标取倒数，形成 $\rho \sim \frac{1}{\mu T(\rho )}$ 坐标系，将整个所有排队系统的最佳操作点优化图景压缩在 1 x 1 方块中：

以上这两个图没有本质区别，只是后者更加一目了然。与 $\rho \sim \mu T(\rho )$ 坐标用切线斜率最小值寻址 P 最大值不同，$\rho \sim \frac{1}{\mu T(\rho )}$ 坐标用曲线和 $\frac{1}{\mu T(\rho )}=\rho$ 的交点横坐标直接寻址 P 的最大值。

任意分布的排队系统 $\rho \sim \frac{1}{\mu T(\rho )}$ 曲线均与 y = x 相交，交点就是最佳操作点，典型的横竖颠倒，柳暗花明的方法论。简单总结一下：

• $\rho \sim \mu T(\rho )$ 坐标系，乘积为矩，商为功率 P，求斜率最值；
• $\rho \sim \frac{1}{\mu T(\rho )}$ 坐标系，乘积为功率 P，商为矩，求面积最值。

外面狂风暴雨，据说是个江淮气旋，挺爽。既然写到了这里，尚无困意，就把今天中午休息时看得另一个 Kleinrock 被采访的短视频再次分享一下：UCLA’s Leonard Kleinrock on packet switching, early Internet。

我们需要一种方法来允许其他人在我们不使用该通信链接时使用它，我称之为资源共享。我们会根据需求共享这些资源：当我有东西要发送时，系统会发送，当我没有任何东西时，其他人可以使用它，网络不断地为他们分配访问权限。

大致解释一下这些话，这么多人需要发送信息的时间分布，就是排队论描述的排队系统的输入，而分组交换网络设计的工作就是给出该排队系统一个输出，让该网络能高效公平满足所有人的发送需求。

大约同一时间，我与 10000 名观众以及计算机工作者和电话工作者举行了大型会议，我首先问：“您能提供一些良好的通信网络吗？” 这些人会说：“看，美国是一个铜矿，到处都是铜线，请使用电话线。” 我当时想，“不，他们不明白。他们打电话只需 35 秒，却向我收取至少三分钟的费用，而我想发送 100 秒的数据。” 他的回答是：“孩子，走开，就像他们说这行不通的原因一样。”数据通信没有收入，没有数据可发送，所以从短期来看他们是对的，这不是收入来源，从长远来看，这将带来一场革命…

Kleinrock 意识到了大型分组交换网络系统的两个核心，资源共享和分布式控制：

• 网络传输的时间片尺度比人们打字或语音听说快得多，这意味着使用的人越多，资源利用率越高；
• 网络必须保证将所有小数据片段到达正确目标，工作量比电话交换机高几个数量级，不能通过控制中心完成。

论动机，​因为是所有人都使用的大型网络系统，所以需要分布式控制和资源共享，这篇划时代的论文最开始叫《大型网络中的数据流》，论实际，论文题目改为了《带存储的网络中的消息延迟》，它包含了底层数学理论的发展和应用，即用排队论建模网络。

挖一下这篇 1961 年的论文：Information Flow in Large Communication Nets，然而已经什么都看不清了：

当被问道 “你曾料到互联网如今天之所见吗？”，Kleinrock 回答 “是也不是，我一开始就料到互联网将无处不在，它将连接一切，始终在线，就像电一样无形，但我没有想到我的母亲也能在线上应对自如，直到她去年去世，享年 99 岁。”

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