深入 TCP VJ-Style
接着 TCP 的文化内涵 继续扯一会儿。
自 30 instruction TCP receive 往前追溯，论文 Jacobson88 源自第一次拥塞崩溃，这篇著名文档在同时期的另一个缘起是另一篇考古文献 [Zhang86] Why TCP Timers Don’t Work Well，后面这篇文献提出了 TCP RTO 的缺陷，指出：
- RTO 是兜底，不要依赖改进 RTO 来优化性能，本质上 RTT 是测不准的；
- 过大过小的 RTO 要么造成连接近乎中断，要么加剧拥塞，当性能太差时，就近乎故障了；
- 虽然 RTO 计算有固有缺陷，但还是需要 “更好的” RTO 计算方法，比如启发式。
VJ 创造了很多技巧，这些技巧携带了很多神秘的 magic number，现在看来这些技巧被认为理所当然到微不足道，早已没人过问理由(一句 “调一手好参数”)，但在 1988 年却是精彩且轰动的，它决定了后续至今的 TCP 演化风格。在 VJ 看来，这些 magic number 都是有理由的，这些理由多数来自 VJ-Style，概括讲，VJ-Style 即对指令的节约。
看 VJ 如何改进 RTO 计算。VJ 简单将 rtt 的移动指数平均换了一种写法(以下按照原始论文的写法)：
a = ( 1 − g ) ⋅ a + g ⋅ m a=(1-g)\cdot a+g\cdot m a=(1−g)⋅a+g⋅m => a = a + g ⋅ ( m − a ) a=a+g\cdot (m-a) a=a+g⋅(m−a)
后面的形式直接就有了 “物理意义”，(m - a) 即误差，这个迭代过程展示的是一个校准过程，rtt 不断收敛到正确的值。
由此 (m - a) 作为一个 “误差” 整体直接参与描述 “方差”。VJ-Style 体现在他没有使用真正的方差 Σ ∣ m − a ∣ 2 \Sigma|m-a|^2 Σ∣m−a∣2，理由是它包含乘法，乘方运算，存在整数溢出的风险， “不太容易计算” 一直是 VJ 的动力，VJ-Style 偏爱简单的整数加减和移位运算。
VJ 采用 m d e v 2 = ( Σ ∣ m − a ∣ ) 2 ≥ Σ ∣ m − a ∣ 2 = s d e v 2 mdev^2=(\Sigma|m-a|)^2\ge\Sigma|m-a|^2=sdev^2 mdev2=(Σ∣m−a∣)2≥Σ∣m−a∣2=sdev2 作为替换，他证明了 mdev 和 sdev 之间存在简单关系，从而确认 mdev 作为 “误差” 的直接表示，恰好是 sdev 一个很好的近似。
接下来表示 mdev 均值的方法与表示 rtt 的方法相同，然后用这个 “误差” 来修正 rtt 本身：
E r r = m − a Err=m-a Err=m−a
a = a + g ⋅ E r r a=a+g\cdot Err a=a+g⋅Err
v = v + g ⋅ ( ∣ E r r ∣ − v ) v=v+g\cdot (|Err|-v) v=v+g⋅(∣Err∣−v)
很精彩！对 srtt 移动指数平均的简单变形直接导出了这个闭环。精彩还在继续。
为了 “快速计算”，消除 <1 的 g 的方式是缩放，用 g = 1 2 n g=\dfrac{1}{2^n} g=2n1 进行缩放可以利用简单的移位运算：
2 n ⋅ a = 2 n ⋅ a + E r r 2^n\cdot a=2^n\cdot a+Err 2n⋅a=2n⋅a+Err
2 n ⋅ v = 2 n ⋅ v + ( ∣ E r r ∣ − v ) 2^n \cdot v=2^n \cdot v+(|Err|-v) 2n⋅v=2n⋅v+(∣Err∣−v)
剩下的事只是选择 n，而 n = 3 时，效果最接近 RFC793 的建议，由此，VJ 完成了对 rtt 计算的一次优化，下面的代码直到现在还在被各种 TCP 实现几乎照抄：
/* 更新平均估计 */
m -= (sa >> 3);
sa += m;
/* 更新偏差估计 */
if (m < 0)m = -m;
m -= (sv >> 3);
sv += m;
Linux 内核的 tcp_rtt_estimator 也在采用。
剩下的计算 RTO 自然水到渠成，它由 rtt 加上 “误差” 的一定增益组成：
R T O = a + 4 ⋅ v RTO=a+4\cdot v RTO=a+4⋅v
这里的 4 来自现实数据统计律，因为它不太小，足够大。仍然是为了便于计算，v 的 g 采用了 1/4：
2 3 ⋅ a = 2 3 ⋅ a + E r r 2^3\cdot a=2^3\cdot a+Err 23⋅a=23⋅a+Err
2 2 ⋅ v = 2 2 ⋅ v + ( ∣ E r r ∣ − v ) 2^2 \cdot v=2^2 \cdot v+(|Err|-v) 22⋅v=22⋅v+(∣Err∣−v)
m -= (sa >> 3);
sa += m;
if (m < 0)m = -m;
m -= (sv >> 2);
sv += m;
rto = (sa >> 3) + sv;
这完美解决了 Lixia Zhang 在 Zhang86 提出的问题，至今工作良好。
RTO 的魔数 4 还来自 VJ 慢启动的理论分析。如果在慢启动轮次结束时计算的重传超时小于等于下一轮的实际 rtt，就会发生虚假重传。最坏情况下，假设所有延迟都由窗口大小的数据排队引发，延迟将每轮翻倍(因为窗口大小翻倍)，因此 R i + 1 = 2 ⋅ R i R_{i+1}=2\cdot R_i Ri+1=2⋅Ri，而 V i = R i − R i − 1 = R i 2 V_i=R_i-R_{i-1}=\dfrac{R_i}{2} Vi=Ri−Ri−1=2Ri，所以 R T O i = R i + R i + 4 V i = 3 R i > 2 R i > R i + 1 RTO_i=R_i+R_i+4V_i=3R_i>2R_i>R_{i+1} RTOi=Ri+Ri+4Vi=3Ri>2Ri>Ri+1，因此虚假重传将不会发生，好精彩！
AIMD 的 Additive Increase 过程每个 ACK 导致 w 增加 1 / w，这导致了除法运算，不仅如此，VJ 建议不要发送 MTU 分数倍的数据包，因为这会降低载荷率，二力合一，VJ-Style 的 AIMD 采用计数方式简单避免了除法运算：
snd_cwnd_cnt ++;
if (snd_cwnd_cnt > cwnd)cwnd ++;
先写到这，其余的参考 RFC1072 后面再说。
浙江温州皮鞋湿，下雨进水不会胖。