TCP 的演化史-sack 与 reordering metric

就着 TCP 本身说事，而不是高谈阔论关于它是如何不合时宜，然后摆出一个更务虚的更新。
从一个 case 开始。

按照现在 Linux TCP(遵守 RFC) 实现，以下是一个将会导致 reordering 更新的 sack 序列：

考虑一种情况，这两个携带 sack block 的 ack 本身乱序，而不是被 sack 确认的 data 乱序， 以上的 reordering 更新就是误判，而 reordering 是单调更新的，递增的 reordering 将影响 mark lost 的数量，进而影响 retransmit 效率。

reordering 误判对 rate-based cc 影响非常大，因为 rate-based cc 要求即使在 loss recovey 状态也要源源不断地发送数据以支撑测量，而 reordering 可能会造成 sender 等待，减少 retransmit。

上述误判情况由下图所示(sack block 上的数字标识 sack block 生成的顺序)：

reordering 误判的依据在于，考虑 sender 发送 1～10，其中 1，3，5，7，9 丢失，receiver 依次收到 2，4，6，8，10. 假设 receiver 由于被其它 option 挤占空间，只能支持 max = 3 个 sack block 段，它 “一般”(下面解释为何不是一定) 会按照以下序列生成 sack block：

收到 2，发送 ack 1，携带 sack 2；
收到 4，发送 ack 1，携带 sack 4-2；
收到 6，发送 ack 1，携带 sack 6-4-2；
收到 8，发送 ack 1，携带 sack 8-6-4；
收到 10，发送 ack 1，携带 sack 10-8-6；
…

如果收到 8 或者 10 后发送的 ack 比收到 2 后发送的 ack 先到达 sender，就会出现第一幅图所示的场景。

为什么这么明显问题，Linux TCP 没处理呢？

因为 RFC 并未规定 sack block 的顺序一定是 LRR(Least Recently Received，类似 LRU，Least Recently Used) 链表的形式。在 RFC2018 第 4 小节 Generating Sack Options: Data Receiver Behavior 中有以下描述：

The SACK option SHOULD be filled out by repeating the most recently reported SACK blocks (based on first SACK blocks in previous SACK options) that are not subsets of a SACK block already included in the SACK option being constructed. This assures that in normal operation, any segment remaining part of a non-contiguous block of data held by the data receiver is reported in at least three successive SACK options, even for large-window TCP implementations [RFC1323]). After the first SACK block, the following SACK blocks in the SACK option may be listed in arbitrary order.

既然不是 MUST，sender 就不能对 sack block 假设任何时间序。对 receiver 而言，由于无法区分原始 seg 和重传 seg，如果是重传 seg，这个 LRR 时间序就不准了。

如果(仅如果) RFC 要求 sack block 保持 LRR 强序，那么 sender 收到的 sack block 就一定是这个强序，便不再受 ack 反向路径乱序影响。

我想的是，虽然 RFC 并未要求 MUST，但事实上应该非常大比例的 receiver 实现了 LRR 强序，这样做最简单。不然因为 RFC 的 maybe 摆布一个 arbitrary order 动机呢，图什么呢？

因此，管它 MUST or SHOULD/MAYBE，sender 假设 sack block 是 LRR 强序，如果真的大部分 receiver 命中了我的猜测，reordering 误判将会减少很多。当然，这个假设需要现网数据支撑。

如果真将 sack block 的 LRR 序从 SHOULD/MAYBE 改为 MUST，根据收到 sack option 中 sack block 的顺序，可更加精确处理 reordering 更新。后文基于该假设继续。

同样上面的 case，加入强序后，就更加精确且清晰：

显然，sender 可根据不同的 sack block 序列，判断出不同的 reordering metric，进而将 reordering 更新成不同值。

LRR 强序前，不能确保 sack block 顺序一定有确切含义，对 sender 就更不能确定其意义，sender 只简单将收到的 sack block 进行升序排序，用这个序列去 mask 所有 rtxq(retransmit queue)，求两个区间链表的交集：区间列表的交集

LRR 强序后，sender 实现更简单了。按照 sack block 在 sack option 的天然顺序匹配发送顺序即可精确判断 reordering。dsack 亦可统一处理。

引入 rack 之后事情变得更简单，sender 可用 sack block 的 LRR 时间序与 rack 时间序做比对来精确判断 reordering：

照 sack block 顺序比对 rack 环，倒排即乱序，reordering 单调递增，rto 复位(rto 意味着路由可能发生了重收敛)。

由于重传歧义硬伤，sender 仍需稍微的启发判断，dsack 一个 seg 后，相信自然序(原始 seg 带来第 1 个 sack，重传 seg 带来第 2 个 sack)，重传后的 sack 相信重传而非乱序，当然，也可以配置信任度量。

无论如何，sack block LRR 强序对 sender 带来更加确定的信息，该信息对 sender 的 cc 决策有益。并且实现更简单了，为什么不呢？

回到 RFC2018，看看初衷。

The SACK option SHOULD be filled out by repeating the most recently reported SACK blocks that are not subsets of a SACK block already included in the SACK option being constructed.

sack block 被安排成 LRR 弱序(may be listed in arbitrary order)，原因二，首先 sack option 长度有限，要为最新的接收事件的数据生成 sack block，其次 sack option 长度又不是那么有限，安排冗余信息可以抵御 ack/sack 丢失，提高鲁棒性：

• Sending a selective acknowledgment for the most recently received data reduces the need for long SACK options.
• The redundant blocks in the SACK option packet increase the robustness of SACK delivery in the presence of lost ACKs.

按照现代的观点，考虑到 sack block 以及反向 ack 本身的乱序对 reordering 的影响，sack block 数量越多越容忍反向路径 ack 乱序，确实如此，4 个 block 够了(如果被其它 option 挤占可能不足 4 个)，况且就算最多只有 4 个 block，只要能零散接收，sack block 就能像滑动窗口(最大 4 段)一样一直滑下去，覆盖所有 ofo(out of order) seg，由于每个 seg 最多可出现4次，即可提供冗余。sack 的该机制是好的，非常好的。

演化过程是见招拆招的过程，远不是全局视角下的设计过程。遇到问题，痛点是解决这个问题，看看初衷问题和 RFC2018 的来源：

sack 解决了问题，sack 就是好的。RFC2018 引入时的 loss recovey 算法依然如旧：

彼时 sack 仅仅可区分对待了 sacked seg，避免不必要的重传。新式的 loss recovey 算法要等后续发布。

标识 sack 相关 loss recovey 算法的 RFC6675 以及前身 RFC3517 均未引入 reordring 的影响，直到 RFC4737 才引入 reordering 度量：Packet Reordering Metrics，这是 2006 年的事，sack 被引入 TCP 时尚无 reordering issue，更谈不上为它提供精准信息。但无论如何，现在 sack 和 reordering 以及 rack 可以结合，并且高尚。
说下本文的缘起。

我用 packetdrill 做 sack 测试，构造了本文图 1 的 ack 乱序 case，触发了 reordering 更新后 mark lost 便不及时了(按照 scoreboard update 算法，保留 reordering 个 sacked seg)，影响了 retransmit 效率。

So？若做 TCP 双边，我觉得一定要确保 receiver 生成 LRR 强序 sack block，多些确切信息总不会错，TCP 就是不确定信息太多才复杂。若做 TCP 单边，我觉得要假设 receiver 生成 LRR 强序 sack block，就算它不是，损失也不多，况且大概率它是，不然对它有什么好处呢？

对了，reordering 的更新不仅和 sack 有关，和 cumulative ack 也有关系。此外，关于反向路径对正向 rate-based 发送的影响，我还有另外一个建议：TCP 时间戳的妙用 以及 TCP 拥塞识别。

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