欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 教育 > 锐评 > bbr 和 inflight 守恒的收敛原理

bbr 和 inflight 守恒的收敛原理

2024/12/1 5:42:22 来源:https://blog.csdn.net/dog250/article/details/141758743  浏览:    关键词:bbr 和 inflight 守恒的收敛原理

先看 bbr,以 2 条流 bw 收敛为例,微分方程组如下:

{ d x d t = C ⋅ g ⋅ x g ⋅ x + y − x d y d t = C ⋅ g ⋅ y g ⋅ y + x − y \begin{cases} \dfrac{dx}{dt}=C\cdot\dfrac{g\cdot x}{g\cdot x+y}-x\\\ \dfrac{dy}{dt}=C\cdot\dfrac{g\cdot y}{g\cdot y+x}-y \end{cases} dtdx=Cgx+ygxx dtdy=Cgy+xgyy

它对应下面的递推式:

{ x t = C ⋅ g ⋅ x t − 1 g ⋅ x t − 1 + y t − 1 y t = C ⋅ g ⋅ y t − 1 g ⋅ y t − 1 + x t − 1 \begin{cases} x_{t}=C\cdot \dfrac{g\cdot x_{t-1}}{g\cdot x_{t-1}+y_{t-1}}\\\ y_{t}=C\cdot \dfrac{g\cdot y_{t-1}}{g\cdot y_{t-1}+x_{t-1}} \end{cases} xt=Cgxt1+yt1gxt1 yt=Cgyt1+xt1gyt1

很显然,通过递推式推导收敛性质非常方便:

  • 当 n 趋向于无穷大时,趋向于一个定值 X,趋向于一个定值 Y。

即 x[n],y[n] 不再变化时,递推式变成了方程组:

{ X = C ⋅ g ⋅ X g ⋅ X + Y Y = C ⋅ g ⋅ Y g ⋅ Y + X \begin{cases} X=C\cdot\dfrac{g\cdot X}{g\cdot X+Y}\\\\Y=C\cdot\dfrac{g\cdot Y}{g\cdot Y+X}\end{cases} X=CgX+YgXY=CgY+XgY

解得两条直线的交点: X = Y = C ⋅ g g + 1 X=Y=\dfrac{C\cdot g}{g+1} X=Y=g+1Cg
在这里插入图片描述

然而直接分析微分方程组更容易,并且可以直接从相图中看出所以然,这也是我为什么一直用微分方程组表达的原因。

若要收敛,则:

{ d x d t = 0 d y d t = 0 \begin{cases} \dfrac{dx}{dt}=0\\\\\dfrac{dy}{dt}=0\end{cases} dtdx=0dtdy=0 即: { x = C ⋅ g ⋅ x g ⋅ x + y y = C ⋅ g ⋅ y g ⋅ y + x \begin{cases} x=C\cdot\dfrac{g\cdot x}{g\cdot x+y}\\\\y=C\cdot\dfrac{g\cdot y}{g\cdot y+x}\end{cases} x=Cgx+ygxy=Cgy+xgy

看起来和递推式一模一样,但不同的是它可以看到收敛点是否稳定。我们画出相图,其实就是上面的图,两条直线将第一象限分割成了 4 个区域,我们分别分析在这 4 个区域中 d x d t \dfrac{dx}{dt} dtdx d y d t \dfrac{dy}{dt} dtdy 的符号即可,正号向右或向上,负号向左或向下,可得(为了画图方便,我将 g 放大到 2.5):
在这里插入图片描述

由此轻易获得稳定的不动点,在 g > 1 时, X = Y = C ⋅ g g + 1 X=Y=\dfrac{C\cdot g}{g+1} X=Y=g+1Cg,若 0 < g < 1,则 x,y 是发散的。

接下来分析收敛速度,我这里不需要确定精确的数值关系,只需要一个定性关系,获得收敛速度和增益 g 的关系,因此就不需要线性化矩阵和求解特征方程了,只需要观测方程:

f ( x ) = C ⋅ g ⋅ x g ⋅ x + K f(x)=C\cdot \dfrac{g\cdot x}{g\cdot x+K} f(x)=Cgx+Kgx

将 K 看作常量,当 g 增加时,f(x) 更快逼近 C,但 K 是一个与 f(x) 相对称的僵持量 f(y),因此当 g 增加时,f(x),f(y) 更快逼近稳定点 X = Y = C ⋅ g g + 1 X=Y=\dfrac{C\cdot g}{g+1} X=Y=g+1Cg

现在看 inflight 守恒算法,同样的假设下,微分方程组如下:

{ d x d t = C ⋅ x ⋅ R + I x ⋅ R + I + y ⋅ R + I − x d y d t = C ⋅ y ⋅ R + I y ⋅ R + I + x ⋅ R + I − y \begin{cases} \dfrac{dx}{dt}=C\cdot\dfrac{ x\cdot R+I}{x\cdot R+I+y\cdot R+I}-x\\\ \dfrac{dy}{dt}=C\cdot\dfrac{y\cdot R+I}{y\cdot R+I+x\cdot R+I}-y \end{cases} dtdx=CxR+I+yR+IxR+Ix dtdy=CyR+I+xR+IyR+Iy

按照和 bbr 类似方法可得到方程组:
{ x 2 R + x y R + ( I − C ⋅ R ) x − C ⋅ I = 0 y 2 R + x y R + ( I − C ⋅ R ) y − C ⋅ I = 0 \begin{cases}x^2R + xyR + (I - C\cdot R)x - C\cdot I = 0\\y^2R + xyR + (I - C\cdot R)y - C\cdot I = 0\end{cases} {x2R+xyR+(ICR)xCI=0y2R+xyR+(ICR)yCI=0
在这里插入图片描述

依然定性分析收敛速度,随着 I 的增大, d x d t \dfrac{dx}{dt} dtdx d y d t \dfrac{dy}{dt} dtdy更快接近 1 ⋅ I 2 ⋅ I \dfrac{1\cdot I}{2\cdot I} 2I1I,收敛越快,但 buffer 占量也随之增加。

两条曲线的夹角越大,收敛越快,这个可以在相图中用几何方法证明

给出一个 inflt 守恒数值解的代码,3 流收敛:

C, R = 10, 5
def dx(a, b, c, r, I):d = C* (a*R + I) / ((b + c)*r + a*R + I) - areturn d...x1[i] = x1[i-1] + (dx(x1[i-1], x2[i-1], x3[i-1], r[i-1], I)) * dtx2[i] = x2[i-1] + (dx(x2[i-1], x1[i-1], x3[i-1], r[i-1], I)) * dtx3[i] = x3[i-1] + (dx(x3[i-1], x1[i-1], x2[i-1], r[i-1], I)) * dtr[i] = (x1[i-1]*R + x2[i-1]*R + x3[i-1]*R + 3*I) / C

我们看到了 bbr 和 inflt 守恒算法的殊途同归。

但且慢,bbr 应该用我前面那篇文章(bbr 微观建模)里的模型,如此一来增益 g 就不再是常量,而与共存流的相位差有关了,假如两个流的相位差为 0,则 g = 1,退化为同步 mimd,永不收敛,但在统计意义上,大量流共存场景,这种现象属实大概率只存在一个 probertt 周期,这就是 bbr 代码在结束 probertt 之后随机部署 probebw phase 的意义。

然而 inflt 守恒算法没有这么多边角事。此后我会把 bbr 1.25X bdp 收敛的过程如何均匀平铺在整个时间轴的细节给出。

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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com