拥塞控制算法的 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] + I
wy[n] = wy[n-1] + I
else:
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] + I
else:
z[n] = z[n-1]
wz[n] = wz[n-1]
if wx[n] + wy[n] + wz[n] > 2*C*R:
# 注释为 westwood
if random.random() < 0.5:
wx[n] = wx[n]/2
#wx[n] = x[n] * R
if random.random() < 0.5:
wy[n] = wy[n]/2
#wy[n] = y[n] * R
if random.random() < 0.5:
wz[n] = wz[n]/2
#wz[n] = z[n] * R
r[n] = (wx[n] + wy[n] + wz[n]) / C
if r[n] < R:
r[n] = R
代码给出一个 4 倍的 rtt 差别(此外还有西装)，x，y 的 rtt 相等，z 为它们的 4 倍，结局如下：
这很容易理解，aimd 是一个线性系统( d w d t = 1 \dfrac{dw}{dt}=1 dtdw=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 + I
wy[n] = y[n-1]*R + I
else:
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 + I
else:
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*R
wy[n] = max_y*R
wz[n] = max_z*R
if 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;
}
这确保了任何流在一个 WIN 内都可以完成一个 probe，确保了公平收敛。很多人咨询这个问题，我这里给出一个长篇回复。
理论很美，在实践中，tcp 的问题在于 ack self-clock，如果 ack 没来，来晚了，聚合了，什么都算不准，但它无疑还是驱动一切的基础，很多问题都来自于它，但很多优化也基于它，很烦，不谈。
想当副经理，就得多给经理送礼。
浙江温州皮鞋湿，下雨进水不会胖。