拥塞控制算法的 Utility-Function

网络效能最大化(Network Utility Maximization) 是一种在网络资源分配和优化等领域广泛应用的理念和技术手段，旨在通过合理分配网络资源(如带宽)，使网络整体效用最大化，而效用则通过 Utility-Function $U(x)$ 来度量。

NUM 最大化意味着 $\Sigma U(x_i)$ 在 $\Sigma x_i<=C$ 的约束下达到最大，这是一个独立的计算领域，本文只谈 $U(x)$ 本身。

$U(x)$ 形式一般(几乎一定)是上凹的，背后是边际效益递减在起作用，意味着 $U(x)$ 是一个递增的，但增长速度递减的函数，log，arctan 均符合该特征，有意思的是，从各拥塞控制算法本身而不是 NUM 的概念出发，推导出 $U(x)$ 符合 log，arctan 的形式是自然而然的，边际效益递减符合类第一性原理：$y={\log }_{a}x$，$y=\arctan (x)$，$y=1-e^{-x}$，$y=x^{0.5}$.

Loss-based AIMD Utility-Function 推导：

设 p 为丢包率，w 为 cwnd，a, b 为 AIMD 参数，看 Loss-based AIMD 的微分方程：

$\frac{dw}{dt}=(1-p)\ast \frac{a}{w}-p\ast b\ast w$

稳定状态下 $\frac{dw}{dt}=0$，于是：

$(1-p)\ast \frac{a}{w}=p\ast b\ast w$

设 x 为发送速率，d 为时延，有 $x=\frac{W}{d}$，于是：

$p=\frac{a}{a+b\cdot W^2}=\frac{a}{a+b\cdot x^2\cdot d^2}$

网络效能由于 p 而变化，于是：

$U^{\prime }(x)=p=\frac{a}{a+b\cdot x^2\cdot d^2}$

积分可得：

$U(x)=\sqrt{\frac{a}{b}}\cdot d\cdot \arctan (\sqrt{\frac{b}{a}}\cdot d\cdot x)$

总结 Loss-based AIMD，丢包率独立于 buffer 单独起作用，需区别对待 buffer 溢出和其它丢包(万年难题)。

Delay-based Vegas Utility-Function 推导：

设 D 为实际 rtt，d 为 minrtt，w 为 cwnd，看 Delay-based Vegas 的 diff 公式：

$diff=\alpha =\frac{w}{d}-\frac{w}{D}$

排队时延 d - D 度量排队 Delay，设发送速率为 x：

$D-d=\frac{\alpha \cdot d}{\frac{w}{D}}=\frac{\alpha \cdot d}{x}$

网络效能由于排队 Delay 而变化，于是：

$U^{\prime }(x)=D-d=\frac{\alpha \cdot d}{x}$

积分可得：

$U(x)=\alpha \cdot d\cdot \log (x)$

等式 $x\cdot (D-d)=\alpha \cdot d$ 左边是 queuing 数据量，右边是约束。具体细节参考 Understanding TCP Vegas: A Duality Model

总结 Vegas，链路上的 buffer 中保留一定量的数据，网络便可高效能传输。

BDP-based BBR Utility-Function 推导：

设 d 为最小测量 rtt，B 为最大带宽(maxbw)下的有效(不算排队时延) BDP：

$d=\frac{B}{x}$

最小 rtt 的承诺度量网络效能的变化：

$U^{\prime }(x)=d=\frac{B}{x}$

积分可得：

$U(x)=B\cdot \log (x)$

总结 BBR，对 minrtt 非常敏感(ProbeRTT 的重要性以及 minrtt 的使用)，minrtt 的共识偏差会影响 BBR 的探测行为和收敛。

写点想法，网络质量越好，拥塞控制的意义越弱，这是边际收益递减的反面，边际成本增加(雇佣一个专家要花不少钱，但他做出来的东西却没什么鸟用)，从内格尔(Nagle)的 RFC896 开始，折腾整整 40 年的拥塞控制，到现在真玩不出什么花活儿了，即将被遗忘，没有坑，工作也难找…大城市立交桥，快速路，高速公路不需要红绿灯，只有乡镇才会批量采购红绿灯…

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