描述分析 bbr 的文字自 2016 年底起至今从空白到泛滥,我自己在期间贡献了不少,本文又是一篇,但不同的是,本文尝试用闭环的数学模型给出一个 bbr 的全貌,顺便和 aimd 做对比。
先看带宽特性 bw(t),设瓶颈带宽为 C,传播时延为 R,2 条流共享瓶颈,则流 1,流 2 的 bw 记为 x,y,它们的演化过程由于下列方程组描述:
d
x
d
t
=
C
⋅
g
⋅
x
⋅
R
g
⋅
x
⋅
R
+
y
⋅
R
−
x
\dfrac{dx}{dt}=C\cdot \dfrac{g\cdot x\cdot R}{g\cdot x\cdot R+y\cdot R}-x
dtdx=C⋅g⋅x⋅R+y⋅Rg⋅x⋅R−x
y
d
t
=
C
⋅
g
⋅
y
⋅
R
g
⋅
y
⋅
R
+
x
⋅
R
−
y
\dfrac{y}{dt}=C\cdot \dfrac{g\cdot y\cdot R}{g\cdot y\cdot R+x\cdot R}-y
dty=C⋅g⋅y⋅R+x⋅Rg⋅y⋅R−y
分析其稳定性,令 f ( x ) d t = 0 \dfrac{f(x)}{dt}=0 dtf(x)=0, f ( y ) d t = 0 \dfrac{f(y)}{dt}=0 dtf(y)=0,可得稳定点在两条直线的交点:
y
=
−
g
⋅
x
+
C
⋅
g
y=-g\cdot x+C\cdot g
y=−g⋅x+C⋅g
x
=
−
g
⋅
y
+
C
⋅
g
x=-g\cdot y+C\cdot g
x=−g⋅y+C⋅g
由此可分析其稳定点的性质:
可见稳定收敛,由于相空间方程组对称,则收敛到公平。同理,3 条流的情况下,微分方程组如下:
d
x
d
t
=
C
⋅
g
⋅
x
⋅
R
g
⋅
x
⋅
R
+
y
⋅
R
+
z
⋅
R
−
x
\dfrac{dx}{dt}=C\cdot \dfrac{g\cdot x\cdot R}{g\cdot x\cdot R+y\cdot R+z\cdot R}-x
dtdx=C⋅g⋅x⋅R+y⋅R+z⋅Rg⋅x⋅R−x
y
d
t
=
C
⋅
g
⋅
y
⋅
R
g
⋅
y
⋅
R
+
x
⋅
R
+
z
⋅
R
−
y
\dfrac{y}{dt}=C\cdot \dfrac{g\cdot y\cdot R}{g\cdot y\cdot R+x\cdot R+z\cdot R}-y
dty=C⋅g⋅y⋅R+x⋅R+z⋅Rg⋅y⋅R−y
z
d
t
=
C
⋅
g
⋅
z
⋅
R
g
⋅
z
⋅
R
+
x
⋅
R
+
y
⋅
R
−
z
\dfrac{z}{dt}=C\cdot \dfrac{g\cdot z\cdot R}{g\cdot z\cdot R+x\cdot R+y\cdot R}-z
dtz=C⋅g⋅z⋅R+x⋅R+y⋅Rg⋅z⋅R−z
n 条流的情况不再赘述。
看一下数值解的图像:
pacing gain 参数调整会影响 bbr 的动力学,这是在图像上可见的变化:
再看第二部分,in-flight 随时间 t 的演化特征 inflight(t)。设瓶颈带宽为 C,传播时延为 R,2 条流共享瓶颈,则流 1,流 2 的 inflight 记为 x,y,它们的演化过程由于下列方程组描述:
d
x
d
t
=
C
⋅
g
⋅
x
g
⋅
x
+
y
⋅
R
−
x
\dfrac{dx}{dt}=C\cdot \dfrac{g\cdot x}{g\cdot x+y}\cdot R-x
dtdx=C⋅g⋅x+yg⋅x⋅R−x
d
y
d
t
=
C
⋅
g
⋅
y
g
⋅
y
+
x
⋅
R
−
x
\dfrac{dy}{dt}=C\cdot \dfrac{g\cdot y}{g\cdot y+x}\cdot R-x
dtdy=C⋅g⋅y+xg⋅y⋅R−x
相图分析与 bw(t) 同理,从略。3 流,n 流扩展与 bw(t) 同理,从略,直接看数值解图像:
可见 inflight noqueuing 且公平收敛。noqueuing 意思是它们纵坐标大致相等,inflight 之和大致等于 C*R。和 bw(t) 公平收敛一同,修饰词 “大致“ 相等而不是绝对相等皆因最后那次的 probe。
众流最终在不停 probe 中在公平点附近震荡,震荡幅度和收敛速度由 gain 决定,gain 越大,收敛越快,但震荡越大,反之 gain 越小,收敛越慢,但震荡幅度也小,这就是调参要诀。
我此前对 bbr inflight 收敛的几何理解有一些错误,通过微分方程组建模则一目了然予以纠正,这是常规的主流论证逻辑。
关于 bbr probertt,值得说明的是理论上 bbr 并不需要这个状态,因为 probebw 的 probe/drain 周期足以保证 noqueuing,但值得注意的是,bbr 采用 10-round max-filter win 作为 probe 基准,因此必须保证在一个 max-filter win 中至少有一次 probe,而这个 max-filter bw 与真实的 bw 之间的差异便是 buffer 稍微堆积的根源,一切环环相扣,若有偏差则可能使系统偏离稳定点。
bbr 顾名思义需要测量两个不可能同时测得的量,若测 maxbw 需要 probe,若测 minrtt 需要 drain,在这个测量意义上,probertt 又是必须的。测 maxbw 需向右,测 minrtt 则要向左:
To learn the true RTProp, a flow moves to the left of BDP using ProbeRTT state: when the RTProp estimate has not been updated (i.e., by measuring a lower RTT) for many seconds, BBR enters ProbeRTT…
基于此,bbr 的动作可能就不再显得细碎了,和 aimd 也没什么不同。
为显示差异和不同,我给出 aimd 的 bw 以及 inflight 的微分方程组,先看 bw:
d
x
d
t
=
C
⋅
(
x
+
1
)
⋅
R
(
x
+
1
)
⋅
R
+
y
⋅
R
−
x
\dfrac{dx}{dt}=C\cdot\dfrac{(x+1)\cdot R}{(x+1)\cdot R+y\cdot R}-x
dtdx=C⋅(x+1)⋅R+y⋅R(x+1)⋅R−x
d
y
d
t
=
C
⋅
(
y
+
1
)
⋅
R
(
y
+
1
)
⋅
R
+
x
⋅
R
−
y
\dfrac{dy}{dt}=C\cdot\dfrac{(y+1)\cdot R}{(y+1)\cdot R+x\cdot R}-y
dtdy=C⋅(y+1)⋅R+x⋅R(y+1)⋅R−y
而 inflight 对应的微分方程组为:
d
x
d
t
=
x
+
1
−
x
=
1
\dfrac{dx}{dt}=x+1-x=1
dtdx=x+1−x=1
d
y
d
t
=
y
+
1
−
y
=
1
\dfrac{dy}{dt}=y+1-y=1
dtdy=y+1−y=1
不再分析相图了,直接看数值解图像:
和 bbr 不同,aimd 的 inflight 收敛靠的是 buffer 溢出 or aqm 丢包这种外在事件,这导致 aimd 系统对这种外部事件响应处的不连续性,相当于把一个连续函数突然截断,断处无可观测的变化率可言,从而无法直观体现在微分方程组中。
以上,这就是 bbr 的全部。
最后给出求数值解的代码,以 bbr inflight 微分方程组为例:
import numpy as np
import matplotlib.pyplot as plt
x0, y0, z0 = 0.1, 5, 2
T, dt = 200, 0.1
C, R = 10, 2
a = 1.25
times = np.arange(0, T + dt, dt)
plt.figure(figsize = (20, 10))
x = np.zeros_like(times)
y = np.zeros_like(times)
z = np.zeros_like(times)
x[0], y[0], z[0] = x0, y0, z0
for n in range(1, len(times)):
x[n] = x[n-1] + dt * (C*R*a*x[n-1]/(a*x[n-1] + y[n-1] + z[n-1]) - x[n-1])
y[n] = y[n-1] + dt * (C*R*a*y[n-1]/(a*y[n-1] + x[n-1] + z[n-1]) - y[n-1])
z[n] = z[n-1] + dt * (C*R*a*z[n-1]/(a*z[n-1] + y[n-1] + x[n-1]) - z[n-1])
plt.plot(times, x, label = 'x(t)')
plt.plot(times, y, label = 'y(t)', linestyle = 'dashed')
plt.plot(times, z, label = 'z(t)', linestyle = 'dotted')
plt.title(f'g = 1.25, C=10, R=2')
plt.xlabel('time (t)')
plt.ylabel('inflight')
plt.grid(True)
plt.show()
昨天顶着高温跑步,途中想到用微分方程组建模分析一下 bbr 的行为。
浙江温州皮鞋湿,下雨进水不会胖。