拥塞控制算法的 rtt 公平性

我强调过，拥塞控制的核心在公平可用性，公平性由 buffer 动力学保证，而 buffer 动力学有两种表现形式：

buffer 占比决定带宽占比，以 aimd 为例；
带宽越小，buffer 挤兑加速比越大，以 bbr 为例。

以这两种形式分类，可清晰获知，对于第一种，rtt 越小越有优势，而对于第二种，公平性与 rtt 无关，rtt 越小，收敛虽迟但到。

先来个直感，以下是一个带 red 的 aimd 实例：

for n in range(1, len(times)):if n % 5 == 0:x[n] = x[n-1] + dt * (C*wx[n-1]/(wx[n-1] + wy[n-1] + wz[n-1]) - x[n-1])y[n] = y[n-1] + dt * (C*wy[n-1]/(wy[n-1] + wx[n-1] + wz[n-1]) - y[n-1])wx[n] = wx[n-1] + Iwy[n] = wy[n-1] + Ielse:x[n] = x[n-1]y[n] = y[n-1]wx[n] = wx[n-1]wy[n] = wy[n-1]if n % 20 == 0:z[n] = z[n-1] + dt * (C*wz[n-1]/(wz[n-1] + wy[n-1] + wx[n-1]) - z[n-1])wz[n] = wz[n-1] + Ielse:z[n] = z[n-1]wz[n] = wz[n-1]if wx[n] + wy[n] + wz[n] > 2*C*R:# 注释为 westwoodif random.random() < 0.5:wx[n] = wx[n]/2#wx[n] = x[n] * Rif random.random() < 0.5:wy[n] = wy[n]/2#wy[n] = y[n] * Rif random.random() < 0.5:wz[n] = wz[n]/2#wz[n] = z[n] * Rr[n] = (wx[n] + wy[n] + wz[n]) / Cif r[n] < R:r[n] = R

代码给出一个 4 倍的 rtt 差别(此外还有西装)，x，y 的 rtt 相等，z 为它们的 4 倍，结局如下：
在这里插入图片描述

这很容易理解，aimd 是一个线性系统( $\dfrac{dw}{dt}=1$ )，rtt 差 n 倍，意味着固定时间内 cwnd 增量差 n 倍，带宽自然也差 n 倍。rtt 正比于 cwnd 增量，而我前面描述过 aimd inc 参数不同时的收敛效果，设 i1，i2 为两条 aimd 流的 cwnd 增量，则(加权)公平线在 y = (a/b)*x。

因此，解决 aimd 算法 rtt 不公平性的方法就是消除 rtt 的影响，用绝对时间替换相对时间，如 cubic 算法所示。

接下来看 inflt 守恒和 bbr，这两个算法都是非线性(其微分方程组没有解析解)，它们的共同点是不通过持续占据 buffer 而做收敛，buffer 对它们的意义在于提供一个验证空间，它们的 buffer 动力学在于用完即走，不靠 buffer 持续占比收敛，而依靠带宽与加速比的负相关(注意，非反比，公式前面写过很多，不再赘述)关系来收敛。

这不难理解，假设流 1 最近一次获得带宽为 x，无论此后流 2 挤兑多少次，假设它获得了带宽 y，但它 drain 掉了 queue，此时 buffer 占率为 0，当流 1 再次挤兑时，它的基础还是 xR，而流 2 的基础为 yR，至于如何收敛，就看 x，y 谁大，越大加速比越小，最终获得公平分配。

先给出 inflt 守恒的直感，然后详细说说 bbr：

for n in range(1, len(times)):if n % 5 == 0:x[n] = x[n-1] + dt * (C*wx[n-1]/(wx[n-1] + wy[n-1] + wz[n-1]) - x[n-1])y[n] = y[n-1] + dt * (C*wy[n-1]/(wy[n-1] + wx[n-1] + wz[n-1]) - y[n-1])wx[n] = x[n-1]*R + Iwy[n] = y[n-1]*R + Ielse:x[n] = x[n-1]y[n] = y[n-1]wx[n] = wx[n-1]wy[n] = wy[n-1]if n % 20 == 0:z[n] = z[n-1] + dt * (C*wz[n-1]/(wz[n-1] + wy[n-1] + wx[n-1]) - z[n-1])wz[n] = z[n-1]*R + Ielse:z[n] = z[n-1]wz[n] = wz[n-1]

效果如下：
在这里插入图片描述

我们看到了虽迟但到。可想而知，bbr 也是虽迟但到的效果。但我想点 bbr 的另一个主题，看看 bbr 是如何解决的。

bbr 有个 maxbw window 滑动窗口，缺省 10-round，这意味着 maxbw 可以保留 10-round 这么久，一旦时间超过这么久，当前流的基础带宽 maxbw = x 就会滑走而不再有效，失去了这个挤兑基础，就失去了信任 “带宽与加速比负相关” 的前提，可想而知，收敛就崩塌了。

我来用一个相对真实的 bbr 实现模拟这个过程：

for n in range(1, len(times)):if n > WIN + 1:sublistx = x[n - WIN : n]sublisty = y[n - WIN : n]sublistz = z[n - WIN : n]max_x = max(sublistx)max_y = max(sublisty)max_z = max(sublistz)else:max_x = x[n-1]max_y = y[n-1]max_z = z[n-1]wx[n] = max_x*Rwy[n] = max_y*Rwz[n] = max_z*Rif n % 3 == 0:x[n] = x[n-1] + dt * (C*g*max_x*R/(g*max_x*R + wy[n-1] + wz[n-1]) - x[n-1])y[n] = y[n-1] + dt * (C*g*max_y*R/(g*max_y*R + wx[n-1] + wz[n-1]) - y[n-1])else:x[n] = C*(wx[n-1])/(wx[n-1] + wy[n-1] + wz[n-1])y[n] = C*(wy[n-1])/(wx[n-1] + wy[n-1] + wz[n-1])if n % 30 == 0:z[n] = z[n-1] + dt * (C*g*max_z*R/(g*max_z*R + wy[n-1] + wx[n-1]) - z[n-1])else:z[n] = C*(wz[n-1])/(wx[n-1] + wy[n-1] + wz[n-1])

我将两个 rtt 设定为 10 倍关系，但绝对值差 30 - 3 = 27 个时间单位，如果我用 WIN = 26(小于 27) 模拟，直接崩塌：
在这里插入图片描述

但如果 WIN = 30，则结局高尚：
在这里插入图片描述

一个 WIN 内至少 probe 一次是标准 bbr 的设定，但按照标准 bbr 的设定，这意味着什么？bbr 的 WIN 是以 rtt 为单位，而不是绝对时间，理论上这里就存在 rtt 的绝对时间不公平问题。

假设流 1 的 rtprop 为 10ms，流 2 的 rtprop 为 200ms，这意味着流 2 的 maxbw 可以保留 2s，而流 1 的 maxbw 仅可以保留 100ms，一旦遭遇拥塞排队，100ms 内没有 probe，流 1 将失去带宽收敛的基础。所以呢，所以 bbr 采用了 packet-timed 来计时，让计时单位和自身关联：

u32     rtt_cnt;            /* count of packet-timed rounds elapsed */
...
/* See if we've reached the next RTT */
if (!before(rs->prior_delivered, bbr->next_rtt_delivered)) {bbr->next_rtt_delivered = tp->delivered;bbr->rtt_cnt++;bbr->round_start = 1;bbr->packet_conservation = 0;
}