TCP BBR的startup bbr_high_gain为什么是2/ln2？

程序员文章站 2022-07-09 21:11:03

...

温州皮鞋厂老板上周就一直在问这个。正好昨天和今天早上有空，加上又在雨夜，就写一波。

温州皮鞋厂老板的问题如下：

慢启动: $i n i t_c w n d \times 2^{n} = c w n d$
增长速率为 $2^{n}$ 求导= $n \times 2^{n - 1}$ . pacing_gain应该等于类似这个东西来算吧
怎么就 $\frac{2}{l n 2}$ 了

其实一开始我也不知道，根本就没有注意过这个问题，能找到的资料也就是tcp_bbr.c中关于bbr_high_gain的注释：

/* We use a high_gain value of 2/ln(2) because it's the smallest pacing gain
 * that will allow a smoothly increasing pacing rate that will double each RTT
 * and send the same number of packets per RTT that an un-paced, slow-starting
 * Reno or CUBIC flow would:
 */
static const int bbr_high_gain  = BBR_UNIT * 2885 / 1000 + 1;

另外，BBR的paper：
https://queue.acm.org/detail.cfm?id=3022184
这里面也能找到一段论述：

To handle Internet link bandwidths spanning 12 orders of magnitude, Startup implements a binary search for BtlBw by using a gain of 2/ln2 to double the sending rate while delivery rate is increasing. This discovers BtlBw in log2BDP RTTs but creates up to 2BDP excess queue in the process.

除此之外，就再也找不到别的资料了。我自己也很好奇，也跟很多人进行了讨论，甚至包括BBR的作者之一Neal Cardwell，最终以我自己的理解，整理出了这篇文章，希望能帮同样有此疑问的人解惑。

在Startup阶段，BBR的bbr_high_gain同时作用于 $P a c i n g R a t e$ 和 $C w n d$ 两者，两者遵循同样的演化规律，即随着 $R T T$ 轮数而指数级递增：

$P a c i n g R a t e = f_{1} (r o u n d s) = R_{0} \times 2^{r o u n d s}$
$C w n d = f_{2} (r o u n d s) = i n i t_c w n d \times 2^{r o u n d s}$

因此，在推导bbr_high_gain时，可以沿着两条路分别进行，我们先沿着 $P a c i n g R a t e$ 积分到 $C w n d$ 这条路推导出 $C w n d$ 视角的bbr_high_gain，然后再通过 $C w n d$ 求导到 $P a c i n g R a t e$ 这条路来验算。

假设在第 $n$ 个 $R T T$ 时其 $P a c i n g R a t e$ 是 $R_{0} \times 2^{n}$ ，那么在下一个 $R T T$ ，即 $n + 1$ 个 $R T T$ 时，它的 $P a c i n g R a t e$ 就会变成 $R_{0} \times 2^{n + 1}$ ，多了 $2^{n}$ 个 $R_{0}$ ，在Startup阶段， $C w n d$ 也遵循同样的演化规律。

为了推导简单，我们将设 $R_{0}$ ， $I n i t C w n d$ ， $R T T$ 均为 $1$ 来归一化，同时用自变量 $x$ 表示以一个 $R T T$ 为单位的轮数，上面的式子可以写成：

$P a c i n g R a t e = f_{1} (x) = 2^{x}$
$C w n d = f_{2} (x) = 2^{x}$

而我们知道， $B D P$ 是 $P a c i n g R a t e$ 在时间上的积分(忽略常数C)。根据我们的假设，我们是按 $R T T$ 轮数来计数的，所以一个 $R T T$ 单位内的 $B D P$ 就是一个关于 $P a c i n g R a t e$ 的定积分：

TCP BBR的startup bbr_high_gain为什么是2/ln2？

按照牛顿-莱布尼兹定理则有：

$B D P_{l a s t r t t} = F (x) |_{x - 1}^{x} = \int_{x - 1}^{x} 2^{x} d x = \frac{2^{x}}{2 \ln 2}$

抽掉 $B D P$ 中的时间维度，在数值上它的意义就是 $C w n d$ 。

设 $G$ 为增益系数，根据间隔一个 $R T T$ 时其 $C w n d$ 的关系，则有：

$F (x) |_{x - 1}^{x} = G \times f_{2} (x - 2)$

化简可以得到：

$\frac{2^{x}}{2 \ln 2} = G \times \frac{2^{x}}{4}$

所以，我们就得到了 $G$ ：

$G = \frac{2}{\ln 2}$

接下来，我们来沿着从 $C w n d$ 到 $P a c i n g R a t e$ 这条路来再走一遍，看看求出的增益系数是不是同一个值。

我们知道，发送量的变化率其实就是发送速率，因此对 $C w n d$ 关于时间求导，就可以得到速率：

$g (x) = f_{2}' (x) = (2^{x})' = 2^{x} \ln 2$

设 $α$ 为 $P a c i n g R a t e$ 的增益系数，则有：

$g (x + 1) = α \times g (x) = α \times 2^{x} \ln 2$

经过 $α$ 演化的 $P a c i n g R a t e$ 恰好就是 $f_{1} (x + 1)$ 的数值：

$f_{1} (x + 1) = α \times g (x) = 2^{x + 1} = α \times 2^{x} \ln 2$

所以，我们可以求出 $α$ 的数值：

$α = \frac{2}{\ln 2}$

可以看出，这里的 $P a c i n g R a t e$ 的增益和前面的 $C w n d$ 增益在数值上是完全一致的，这也就是TCP BBR中的那个魔数 $\frac{2}{\ln 2}$ 的由来。

如果你足够细心，你会发现上面的推导中有一个破绽。比如，既然 $f_{1} (x) = f_{2} (x)$ ，而 $g (x)$ 又由 $f_{1} (x)$ 求导产生， $g (x)$ 和 $f_{2} (x)$ 均表示 $P a c i n g R a t e$ 时，显然而然的是：

$g (x) \neq f_{2} (x)$

！！
其实，函数 $f_{1}$ 和 $f_{2}$ 之所以这么写是因为它们在离散的 $R T T$ 上表现得确实如此，但在实际中，速率计算， $C w n d$ 计算并非总是由平滑均匀的ACK事件来触发的，所以说就必须用一条光滑的曲线来尽量拟合离散的点，因此，上面的 $f_{1} (x)$ ， $f_{2} (x)$ 本身就不是光滑曲线，它们和 $g (x)$ 本身就不是同一条曲线。

实际上， $f_{1} (x)$ 和 $f_{2} (x)$ 表示的均是折线，所要做的正是用光滑的曲线去拟合折线上那些离散的转折点，所以说，只能用增益系数代入去解方程，而不是直接让两个函数相等。

$f_{1}$ 和 $f_{2}$ 的图像类似下面这样：

TCP BBR的startup bbr_high_gain为什么是2/ln2？

我们再把代表 $B D P$ 的平滑拟合曲线 $F (x)$ 以及代表 $P a c i n g R a t e$ 的平滑拟合曲线 $g (x)$ 画到同一个坐标系中：

TCP BBR的startup bbr_high_gain为什么是2/ln2？

可以看得出，它们是3样不同的曲线。

不过，看起来 $F (x)$ 和 $g (x)$ 对离散的 $f_{1} (x)$ 和 $f_{2} (x)$ 拟合得并不是很理想，那为什么不直接用 $f (x) = 2^{x}$ 来拟合呢？它可是能完美拟合的吧：

TCP BBR的startup bbr_high_gain为什么是2/ln2？

或者，我们可以用二项式去拟合，用级数…

然而这些都不行。为什么呢？因为要考虑到计算，这里并不是在解一道数学题，而是要求出一个确定的常数作为增益系数 $G$ ，注意，是确定的常数。如果不通过积分或者求导的方式引入一个 $\ln 2$ 因子，单纯的 $f (x) = 2^{x}$ 是无法得到一个确定的常数的。

这种方法，我们感到似曾相识，TCP的拥塞控制算法，从BIC到CUBIC就是采用了这种光滑的三次曲线拟合BIC二分折线的方法，其中的那些参数也可以用类似的方法求解。

除此之外，以上推导中，下面的关系是不存在的：

$f_{1} (x + 1) = α \times f_{1} (x)$
$f_{2} (x + 1) = α \times f_{2} (x)$

为什么？因为 $f_{1} (x)$ 和 $f_{2} (x)$ 上的点是离散的，非连续函数在无定义的域上求值没有意义。然而ACK的到达并非以RTT为单位准点的，更有可能遭遇ACK丢失，ACK聚集等无法预知的时间，因此ACK到达是任意的，所以就必须用光滑的曲线来拟合这些离散的点，从而达到比较平滑的增益效果。

简单点说，增益系数 $G$ 的结果是针对光滑的拟合曲线而言的，即针对 $g (x)$ 以及 $F (x)$ 的，而不是针对 $f_{1} (x)$ 和 $f_{2} (x)$ 的。