dctcp 和 l4s tcp prague

时延的罪与罚。

dctcp 为 dcn 而生，专注于避免吞吐优先的长流阻塞延迟敏感的短流。在最坏情况下，没有任何额外队列规则辅助时，即使长流短流排入唯一的 fifo，也要能做到这点。

为此，必须由交换机辅助实现普遍低时延，在队列长度超过一个足够低值 k 时开始标记 ecn，理论上把这部分 ecn 标记的发送量排除掉就能将队列长度降低到 k 以下。 显然的算法就是：

cwnd = cwnd * (1 - mark_rate)

而 mark_rate = (一轮周期中标记 ecn 的 ack) / (一轮周期中所有 ack )。但由于 dctcp 仍以标准 tcp(reno，cubic 等变体) 为底色，标准 tcp 执行 aimd，它以系数 1 / 2 而不是 1 执行 md 响应拥塞，为拟合标准 tcp：

cwnd = cwnd * (1 - mark_rate / 2)

此外，为排除噪声抖动，mark_rate 需某种平均计数，dctcp 设 alpha 作为 mark_rate 移指平均(连续采样最简单的平均算法)：

alpha = (1 - g) * alpha + g * F
cwnd = cwnd * (1 - alpha / 2)

其中 F 即 (一轮周期中标记 ecn 的 ack) / (一轮周期中所有 ack )。当无拥塞 or 轻微拥塞，alpha 很小，cwnd 倾向于不变，最严重情况下 alpha 为 1，即全部标记，此时 dctcp 的 cwnd 减半，其行为拟合标准 tcp。

由此，适用于 dcn 的低时延 cc 出炉，这就是 dctcp 的全部。

但如 rfc8257 所述的部署问题，dcn 为保证极低时延，交换机拥塞阈值配置非常低，dctcp 与标准 tcp 对拥塞的反应在这种情况下导致不公平，标准 tcp 的 aimd 在浅 buffer 本就效率低下，遇到缓慢适配带宽的 dctcp 更加低效，这意味着二者需要隔离。

dctcp 是一个非常简洁的算法，妙处在于它构建于 aimd 标准 tcp 上，实属 tcp 的增强。如果将标准 tcp 视作盲目反应协议，它只要足够公平收敛就足够，那么 dctcp 则以明确的显式 ecn 反馈消除了一大部分盲目损耗，正所谓信息消除不确定性。

但如 tcp 的拧巴属性，假设 dctcp 果真能解决时延问题(事实上已经解决了很大问题)，那它一定揭露了另一个问题。

默认 aimd 行为中，排队时延约 20ms 量级，无论传播时延 100us 还是 100ms，栽进 buffer 就引入 20ms，排队时延掩盖了真实时延差异，100us 和 100ms 相差 1000 倍，排队时延遮掩下成了 20.1ms 和 120ms 相差不到 6 倍。

如果 dctcp 把排队时延消除了，它还能构建于 aimd tcp 之上吗？显然不行。

aimd 速率公式：$吞吐=\frac{\alpha }{RTT}\sqrt{\frac{1}{p}}$，rtt 越大，吞吐越小，aimd 的公平是 bdp 公平，把 rtt 乘过去就公平了，但网络讲究的不是 bdp，而是吞吐。

不过 dcn rtt 不公平并不明显，同属一个机房不跨核心，传播时延相差普遍不到 10 倍，20us 到 200us，这是光速和物理距离决定的，但在广域网这问题就非常明显。

作为把交换机 ecn 标记和 dctcp 搬到广域网的尝试，l4s 框架配合可扩展算法实例 tcp prague，将 rtt 公平性作为算法的内置，解除了算法和 rtt 的关联，即 rtt-independence。

tcp prague 以非常随意但十分精巧的方式引入虚拟 rtt：

virt_rtt = max(srtt, 25ms)

如果 srtt 小于 25ms 就以 25ms 计，依据是 “rtt 越小越强势”，因此把 rtt 最小值限制在 25ms(经验)，这和 “不可扩展 aimd 算法” 引入的排队时延异曲同工，遏制了小 rtt 的侵略性。

在不影响 aimd 的 bdp 公平性前提下做这个调整非常具有技巧性，只需 “长宽缩放面积不变”，virt_rtt 相比 actual_rtt 扩大多少倍，virt_cwnd 就缩小多少倍，这相当于把一个 rtt 极小，吞吐很大的细高长方形拉扯延展成一个等面积扩大的宽胖长方形。为此，引入 m = virt_rtt / srtt。

按照 aimd，在 ai 阶段每个 rtt cwnd 增加 1，引入 virt_rtt 后即每个 virt_rtt virt_cwnd 增加 1：

cwnd += (1 / m) (1 / virt_cwnd) = (1 / m) (1 / (m cwnd)) = (1 / m^2) (1 / cwnd)

这只对 rtt < 25ms 的流有影响。可见，在 tcp prague 眼里，所有流的 rtt 都大于 25ms，在没有排队时延假设的前提下，世界上最大的传播时延在 200ms 左右，与 25ms 相差 10 倍而已，rtt 不公平性被限制在合理范围。

tcp prague 有个细节值得一提。上述 rtt-independence 特性限制了 rtt 公平性问题的扩散，但它无疑损害了小 rtt 的流，如果这条流同时也很短，它出让的本该属于它的吞吐无法从 RTT-InDependence 获得任何益处，哪怕只是好的名声。

在公平性之外，按照 stcf(shortest time-to-completion first) 原则，确实要给短流一些优先权，因此 rtt-independence 只在 d(默认 500) 轮 rtt 后才开启。

dctcp/tcp prague 的思路和 vegas 不同，前者属于为 aimd 注入额外信息消除不确定性进行优化，后者属于直接试图避免拥塞并维持公平(bbr 也一样，但 bbr 在理论上做不到)。但 vegas 也有问题，它为每条流在 buffer 中保留 alpha 个段，如果 buffer 很浅， 流很多时仍然避免不了 buffer overflow 而丢包，如何处理丢包和重传就是 vegas 必须要做的，论文的时间序重传很好，然而在 linux 实现上却回退了，以下来自 linux vegas 的注释：

We do not change the loss detection or recovery mechanisms of Linux in any way. Linux already recovers from losses quite well, using fine-grained timers, NewReno, and FACK.

也许是作者没有真正理解 vegas 时间序重传的重要性。也许 vegas + l4s 框架，根据反馈信息不断调整 alpha，beta 或许能真实现完全的拥塞避免，但 dctcp/tcp prague 在强化 aimd 的路上应该也不会有所区别。

好了，这就是今天要讲的 dctcp 和 tcp prague 的故事。

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