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

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

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

慢启动:
init_cwnd×2n=cwnd

i

n

i

t

_

c

w

n

d

×

2

n

=

c

w

n

d

$init_cwnd times 2^n = cwnd$
增长速率为
2n

2

n

$2^n$求导=
n×2n−1

n

×

2

n

−

1

$ntimes 2^{n-1}$. pacing_gain应该等于类似这个东西来算吧
怎么就
2ln2

2

l

n

2

$dfrac{2}{ln2}$了

其实一开始我也不知道，根本就没有注意过这个问题，能找到的资料也就是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同时作用于
PacingRate

P

a

c

i

n

g

R

a

t

e

$PacingRate$和
Cwnd

C

w

n

d

$Cwnd$两者，两者遵循同样的演化规律，即随着
RTT

R

T

T

$RTT$轮数而指数级递增：

PacingRate=f1(rounds)=R0×2rounds

P

a

c

i

n

g

R

a

t

e

=

f

1

(

r

o

u

n

d

s

)

=

R

0

×

2

r

o

u

n

d

s

$PacingRate =f_1(rounds)= R_0times 2^{rounds}$

Cwnd=f2(rounds)=init_cwnd×2rounds

C

w

n

d

=

f

2

(

r

o

u

n

d

s

)

=

i

n

i

t

_

c

w

n

d

×

2

r

o

u

n

d

s

$Cwnd = f_2(rounds)=init_cwndtimes 2^{rounds}$

因此，在推导bbr_high_gain时，可以沿着两条路分别进行，我们先沿着
PacingRate

P

a

c

i

n

g

R

a

t

e

$PacingRate$积分到
Cwnd

C

w

n

d

$Cwnd$这条路推导出
Cwnd

C

w

n

d

$Cwnd$视角的bbr_high_gain，然后再通过
Cwnd

C

w

n

d

$Cwnd$求导到
PacingRate

P

a

c

i

n

g

R

a

t

e

$PacingRate$这条路来验算。

假设在第
n

n

$n$个$RTT$时其
PacingRate

P

a

c

i

n

g

R

a

t

e

$PacingRate$是
R0×2n

R

0

×

2

n

$R_0times 2^n$，那么在下一个
RTT

R

T

T

$RTT$，即
n+1

n

+

1

$n+1$个
RTT

R

T

T

$RTT$时，它的
PacingRate

P

a

c

i

n

g

R

a

t

e

$PacingRate$就会变成
R0×2n+1

R

0

×

2

n

+

1

$R_0times 2^{n+1}$，多了
2n

2

n

$2^n$个
R0

R

0

$R_0$，在Startup阶段，
Cwnd

C

w

n

d

$Cwnd$也遵循同样的演化规律。

为了推导简单，我们将设
R0

R

0

$R_0$，
InitCwnd

I

n

i

t

C

w

n

d

$InitCwnd$，
RTT

R

T

T

$RTT$均为
1

1

$1$来归一化，同时用自变量$x$表示以一个
RTT

R

T

T

$RTT$为单位的轮数，上面的式子可以写成：

PacingRate=f1(x)=2x

P

a

c

i

n

g

R

a

t

e

=

f

1

(

x

)

=

2

x

$PacingRate = f_1(x)=2^x$

Cwnd=f2(x)=2x

C

w

n

d

=

f

2

(

x

)

=

2

x

$Cwnd =f_2(x)=2^x$

而我们知道，
BDP

B

D

P

$BDP$是
PacingRate

P

a

c

i

n

g

R

a

t

e

$PacingRate$在时间上的积分(忽略常数C)。根据我们的假设，我们是按
RTT

R

T

T

$RTT$轮数来计数的，所以一个
RTT

R

T

T

$RTT$单位内的
BDP

B

D

P

$BDP$就是一个关于
PacingRate

P

a

c

i

n

g

R

a

t

e

$PacingRate$的定积分：

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

BDPlastrtt=F(x)|xx−1=∫xx−12xdx=2x2ln2

B

D

P

l

a

s

t

r

t

t

=

F

(

x

)

|

x

−

1

x

=

∫

x

−

1

x

2

x

d

x

=

2

x

2

ln

⁡

2

$BDP_{lastrtt}=F(x)|_{x-1}^{x}=displaystyleint_{x-1}^{x} 2^xdx=dfrac{2^x}{2ln 2}$

抽掉
BDP

B

D

P

$BDP$中的时间维度，在数值上它的意义就是
Cwnd

C

w

n

d

$Cwnd$。

设
G

G

$G$为增益系数，根据间隔一个$RTT$时其
Cwnd

C

w

n

d

$Cwnd$的关系，则有：

F(x)|xx−1=G×f2(x−2)

F

(

x

)

|

x

−

1

x

=

G

×

f

2

(

x

−

2

)

$F(x)|_{x-1}^x=Gtimes f_2(x-2)$

化简可以得到：

2x2ln2=G×2x4

2

x

2

ln

⁡

2

=

G

×

2

x

4

$dfrac{2^x}{2ln 2}=Gtimes dfrac{2^x}{4}$

所以，我们就得到了
G

G

$G$：

$G=dfrac{2}{ln 2}$

---

接下来，我们来沿着从
Cwnd

C

w

n

d

$Cwnd$到
PacingRate

P

a

c

i

n

g

R

a

t

e

$PacingRate$这条路来再走一遍，看看求出的增益系数是不是同一个值。

我们知道，发送量的变化率其实就是发送速率，因此对
Cwnd

C

w

n

d

$Cwnd$关于时间求导，就可以得到速率：

g(x)=f2′(x)=(2x)′=2xln2

g

(

x

)

=

f

2

′

(

x

)

=

(

2

x

)

′

=

2

x

ln

⁡

2

$g(x)=f_2prime(x)=(2^x)prime=2^x ln2$

设
α

α

$alpha$为
PacingRate

P

a

c

i

n

g

R

a

t

e

$PacingRate$的增益系数，则有：

g(x+1)=α×g(x)=α×2xln2

g

(

x

+

1

)

=

α

×

g

(

x

)

=

α

×

2

x

ln

⁡

2

$g(x+1)=alpha times g(x) = alpha times 2^x ln2$

经过
α

α

$alpha$演化的
PacingRate

P

a

c

i

n

g

R

a

t

e

$PacingRate$恰好就是
f1(x+1)

f

1

(

x

+

1

)

$f_1(x+1)$的数值：

f1(x+1)=α×g(x)=2x+1=α×2xln2

f

1

(

x

+

1

)

=

α

×

g

(

x

)

=

2

x

+

1

=

α

×

2

x

ln

⁡

2

$f_1(x+1) = alpha times g(x) = 2^{x+1} = alpha times 2^x ln2$

所以，我们可以求出
α

α

$alpha$的数值：

α=2ln2

α

=

2

ln

⁡

2

$alpha = dfrac{2}{ln2}$

可以看出，这里的
PacingRate

P

a

c

i

n

g

R

a

t

e

$PacingRate$的增益和前面的
Cwnd

C

w

n

d

$Cwnd$增益在数值上是完全一致的，这也就是TCP BBR中的那个魔数
2ln2

2

ln

⁡

2

$dfrac{2}{ln2}$的由来。

---

如果你足够细心，你会发现上面的推导中有一个破绽。比如，既然
f1(x)=f2(x)

f

1

(

x

)

=

f

2

(

x

)

$f_1(x)=f_2(x)$，而
g(x)

g

(

x

)

$g(x)$又由
f1(x)

f

1

(

x

)

$f_1(x)$求导产生，
g(x)

g

(

x

)

$g(x)$和
f2(x)

f

2

(

x

)

$f_2(x)$均表示
PacingRate

P

a

c

i

n

g

R

a

t

e

$PacingRate$时，显然而然的是：

g(x)≠f2(x)

g

(

x

)

≠

f

2

(

x

)

$g(x) ne f_2(x)$

！！
其实，函数
f1

f

1

$f_1$和
f2

f

2

$f_2$之所以这么写是因为它们在离散的
RTT

R

T

T

$RTT$上表现得确实如此，但在实际中，速率计算，
Cwnd

C

w

n

d

$Cwnd$计算并非总是由平滑均匀的ACK事件来触发的，所以说就必须用一条光滑的曲线来尽量拟合离散的点，因此，上面的
f1(x)

f

1

(

x

)

$f_1(x)$，
f2(x)

f

2

(

x

)

$f_2(x)$本身就不是光滑曲线，它们和
g(x)

g

(

x

)

$g(x)$本身就不是同一条曲线。

实际上，
f1(x)

f

1

(

x

)

$f_1(x)$和
f2(x)

f

2

(

x

)

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

f1

f

1

$f_1$和
f2

f

2

$f_2$的图像类似下面这样：

我们再把代表
BDP

B

D

P

$BDP$的平滑拟合曲线
F(x)

F

(

x

)

$F(x)$以及代表
PacingRate

P

a

c

i

n

g

R

a

t

e

$PacingRate$的平滑拟合曲线
g(x)

g

(

x

)

$g(x)$画到同一个坐标系中：

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

不过，看起来
F(x)

F

(

x

)

$F(x)$和
g(x)

g

(

x

)

$g(x)$对离散的
f1(x)

f

1

(

x

)

$f_1(x)$和
f2(x)

f

2

(

x

)

$f_2(x)$拟合得并不是很理想，那为什么不直接用
f(x)=2x

f

(

x

)

=

2

x

$f(x)=2^x$来拟合呢？它可是能完美拟合的吧：

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

然而这些都不行。为什么呢？因为要考虑到计算，这里并不是在解一道数学题，而是要求出一个确定的常数作为增益系数
G

G

$G$，注意，是确定的常数。如果不通过积分或者求导的方式引入一个$ln2$因子，单纯的
f(x)=2x

f

(

x

)

=

2

x

$f(x)=2^x$是无法得到一个确定的常数的。

---

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

---

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

f1(x+1)=α×f1(x)

f

1

(

x

+

1

)

=

α

×

f

1

(

x

)

$f_1(x+1)=alpha times f_1(x)$

f2(x+1)=α×f2(x)

f

2

(

x

+

1

)

=

α

×

f

2

(

x

)

$f_2(x+1)=alpha times f_2(x)$

为什么？因为
f1(x)

f

1

(

x

)

$f_1(x)$和
f2(x)

f

2

(

x

)

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

简单点说，增益系数
G

G

$G$的结果是针对光滑的拟合曲线而言的，即针对$g(x)$以及
F(x)

F

(

x

)

$F(x)$的，而不是针对
f1(x)

f

1

(

x

)

$f_1(x)$和
f2(x)

f

2

(

x

)

$f_2(x)$的。