本文主要是介绍当代传输算法以及其效率和公平,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
我不再提拥塞控制算法,因为当代一个好的,正常的传输算法本应该天然主动避免拥塞,而不是拥塞了再控制,本着这个思路,我甚至觉得 bbr 的 probe 都是一种 capacity-seeking 行为,而 capacity-seeking 是一定会制造拥塞的。所以我的想法很简单,跟踪 E = max(bw / delay),保持 inflight 守恒。
设 x 为 E = bw / delay 效能,y 为 flow 在瓶颈处的实际分配带宽,r 为时延,inflt 守恒方程组如下:
I ( t ) = ∑ i = 0 n w i ( t ) I(t)=\displaystyle\sum_{i=0}^n w_i(t) I(t)=i=0∑nwi(t)
d x d t = y r − x \dfrac{dx}{dt}=\dfrac{y}{r}-x dtdx=ry−x
d y d t = C ⋅ y ⋅ r I ( t ) − y \dfrac{dy}{dt}=C\cdot\dfrac{y\cdot r}{I(t)}-y dtdy=C⋅I(t)y⋅r−y
r ( t ) = { I ( t ) C , I ( t ) > C ⋅ R R , I ( t ) ≤ C ⋅ R r(t)=\begin{cases} \dfrac{I(t)}{C} ,& I(t)>C\cdot R\\\\R,&I(t)\leq C\cdot R \end{cases} r(t)=⎩ ⎨ ⎧CI(t),R,I(t)>C⋅RI(t)≤C⋅R
r m i n = min i ∈ [ t , t + T r ] r ( i ) r_{min}=\displaystyle\min\limits_{i\in[t,t+T_r]}r(i) rmin=i∈[t,t+Tr]minr(i)
E b e s t = max i ∈ [ t , t + W i n ] x ( i ) E_{best}=\displaystyle\max\limits_{i\in[t,t+Win]}x(i) Ebest=i∈[t,t+Win]maxx(i)
B D P r e m a i n = y ( E b e s t . t ) ⋅ r m i n + α ⋅ ( r m i n r ) γ − β ⋅ y ( E b e s t . t ) ⋅ r m i n BDP_{remain}=y(E_{best}.t)\cdot r_{min}+\alpha\cdot (\dfrac{r_{min}}{r})^\gamma-\beta\cdot y(E_{best}.t)\cdot r_{min} BDPremain=y(Ebest.t)⋅rmin+α⋅(rrmin)γ−β⋅y(Ebest.t)⋅rmin
理论上,如果一条流保持 inflt 为 y ( E b e s t . t ) ⋅ r m i n y(E_{best}.t)\cdot r_{min} y(Ebest.t)⋅rmin 就不会占任何 buffer,但 buffer 是公平收敛的场所,最终还是要在时延和公平性之间做 trade-off,效率和公平还是不能兼得,调一手好参数重要。 y ( E b e s t . t ) ⋅ r m i n y(E_{best}.t)\cdot r_{min} y(Ebest.t)⋅rmin 后面那一坨就是处理这种 “不可兼得” 的,它是兼顾效率和公平的手段,换句话说,这一坨即保证了效率,又确保了公平。这是一个完备的算法。
效率取决于资源的使用,而公平性则取决于资源的分配。直接使用资源显然是最高效的,而分配则需要一个捯饬资源的场所,捯饬的过程体现了效率的降低。
一般意义上,将时延看作效率的度量,而公平性则体现在收敛速度,我将上面的方程参数具象化,演示一个实例:
这是一个效率和公平不能兼得的实例,但远非唯一。我们一般从市场经济的宏观调控中获得最初关于效率和公平的认知,但在具体的领域,这种认知被具象成不同的形式。
影响效率的另一个 tradeoff 是可靠性,相当的时延来自重传。但这是另一个话题。
包括 bbr 以及我的 inflight 守恒在内的当代传输算法与传统算法的区别有一个核心,当大卫克拉克(David D. Clark,一个名人儿)的团队问雅各布森时为什么不依赖路由器发出的信息进行拥塞控制时,雅各布森的回答是,如果他提出一个路由器实现的算法,以确定何时发送拥塞报文,几乎可以肯定的是,程序员将错误地对其进行编码。但是,没有任何编码错误可以让路由器在内存耗尽的情况下避免丢包。
这个回答总结了始自雅各布森的传统算法的核心特征,它们是一种最简单,仅确保可用性,最消极的拥塞应对算法,先污染后治理就是自然而然的,而当代算法则是主动算法,它们天然考虑到资源的极限而避免了拥塞,而拥塞控制只做兜底。
浙江温州皮鞋湿,下雨进水不会胖。
这篇关于当代传输算法以及其效率和公平的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!