深入 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)\cdot a+g\cdot m$ => $a=a+g\cdot (m-a)$

后面的形式直接就有了 “物理意义”，(m - a) 即误差，这个迭代过程展示的是一个校准过程，rtt 不断收敛到正确的值。

由此 (m - a) 作为一个 “误差” 整体直接参与描述 “方差”。VJ-Style 体现在他没有使用真正的方差 $\Sigma |m-a{|}^2$，理由是它包含乘法，乘方运算，存在整数溢出的风险， “不太容易计算” 一直是 VJ 的动力，VJ-Style 偏爱简单的整数加减和移位运算。

VJ 采用 $mde{v}^2=(\Sigma |m-a|{)}^2\ge \Sigma |m-a{|}^2=sde{v}^2$ 作为替换，他证明了 mdev 和 sdev 之间存在简单关系，从而确认 mdev 作为 “误差” 的直接表示，恰好是 sdev 一个很好的近似。

接下来表示 mdev 均值的方法与表示 rtt 的方法相同，然后用这个 “误差” 来修正 rtt 本身：

$Err=m-a$

$a=a+g\cdot Err$

$v=v+g\cdot (|Err|-v)$

很精彩！对 srtt 移动指数平均的简单变形直接导出了这个闭环。精彩还在继续。

为了 “快速计算”，消除 <1 的 g 的方式是缩放，用 $g=\frac{1}{2^n}$ 进行缩放可以利用简单的移位运算：

$2^n\cdot a=2^n\cdot a+Err$

$2^n\cdot v=2^n\cdot 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 加上 “误差” 的一定增益组成：

$RTO=a+4\cdot v$

这里的 4 来自现实数据统计律，因为它不太小，足够大。仍然是为了便于计算，v 的 g 采用了 1/4：

$2^3\cdot a=2^3\cdot a+Err$

$2^2\cdot v=2^2\cdot 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\cdot R_i$，而 $V_i=R_i-R_{i-1}=\frac{R_i}{2}$，所以 $RT{O}_i=R_i+R_i+4V_i=3R_i>2R_i>R_{i+1}$，因此虚假重传将不会发生，好精彩！

AIMD 的 Additive Increase 过程每个 ACK 导致 w 增加 1 / w，这导致了除法运算，不仅如此，VJ 建议不要发送 MTU 分数倍的数据包，因为这会降低载荷率，二力合一，VJ-Style 的 AIMD 采用计数方式简单避免了除法运算：

snd_cwnd_cnt ++;
if (snd_cwnd_cnt > cwnd)cwnd ++;

先写到这，其余的参考 RFC1072 后面再说。

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