从 Reno TCP 到 Scalable TCP,HighSpeed TCP

前文 Scalable TCP 如何优化长肥管道 介绍了 Scalable TCP,但联系另一个类似的算法 HighSpeed TCP(简称 HSTCP),就会看到一个类似从 Reno TCP 经 BIC 到 CUBIC 的路线,但采用了不同的策略。

Reno TCP 经 BIC 到 CUBIC 路线的核心在于 “在长肥管道中快速逼近管道容量”,采用二分法或三次曲线除了属于不同实现方式,二者也有承接。

而从 Reno TCP 分化而来的 Scalable TCP,HSTCP 这条路线的核心在于 “在长肥管道容忍更高的丢包率”,前文已经说过 Scalable TCP,本文简述 HSTCP,来自 Sally Floyd,参见 HighSpeed TCP (HSTCP)

我在 2021 年已经写过一篇关于 HSTCP 的详细推导 漫谈 HSTCP,本文为其缩略版,侧重核心的推导。

常规 Reno TCP 的问题在于对大容量管道没有扩展性,一方面 cwnd 打开速度太慢,另一方面对丢包容忍度太低,二者相互加深纠缠:在高速网络缓慢的 cwnd 打开过程中,只要遭遇丢包,窗口就会减半,而这个过程越久,丢包概率就越大。这个丢包容忍度甚至已经低于世界上最好的介质误码率。

该问题产生的根源在于,设计单纯的端到端拥塞控制算法时只考虑了拥塞丢包(buffer 溢出)的因素,并未考虑底层介质误码造成的随机丢包。这个因素一直影响着几乎所有拥塞控制算法的设计,直到今日。

HSTCP 对 Reno TCP 的优化全在 response curve 上进行。首先给出标准 Reno 的 response function:

W = a ⋅ ( 2 − b ) 2 b ⋅ p W=\sqrt{\dfrac{a\cdot(2-b)}{2b\cdot p}} W=2bpa(2b) 【这个式子我就不推导了,详见之前的文章】

将 a = 1,b = 0.5 带入,得到现行 Reno TCP 的 response function:

W = 1.22 ⋅ 1 p W=1.22\cdot\sqrt{\dfrac{1}{p}} W=1.22p1

双对数坐标系里绘图:
在这里插入图片描述

如红色标注所示,支撑 100 的 cwnd 就需要 10^{-4} 丢包率,可见条件之苛刻。需要让这条线陡峭起来。

不能指望调整 a,b 达到目标,因为 p 的指数不变,线条只能平行移动,而不能改变斜率。前文所述 Scalable TCP 采用改变 per-ack 行为,将与 RTT 相关的 “Per-RTT- Additive Increase” 变换为 RTT 无关的 “Per-ACK- Additive Increase”,做到了 “使斜率变为 -1,直线变陡”,得到了新的 response function:

W = a b ⋅ p W=\dfrac{a}{b\cdot p } W=bpa

HSTCP 则采用了另一种方法,直接从 response curve 上入手,求直线方程:
在这里插入图片描述

很容易求出直线的斜率,即 response function 中 p 的指数:

S = ln ⁡ w 1 − ln ⁡ w 0 ln ⁡ p 1 − ln ⁡ p 0 S=\dfrac{\ln w_1-\ln w_0}{\ln p_1 -\ln p_0} S=lnp1lnp0lnw1lnw0

按照 paper 建议将 p0(0.0015, 31) 和 p1(10^{-7}, 83000) 代入,可求得 S = -0.82,再代入一点坐标,得 HSTCP 的 response function:

W = 0.15 p 0.82 W=\dfrac{0.15}{p^{0.82}} W=p0.820.15

这就是 HSTCP 算法完整描述。但考虑到实际部署实施,还要考虑如何实现算法。

本质上,HSTCP 仍然是一个 AIMD 算法,但显然无法套入 W = a ⋅ ( 2 − b ) 2 b ⋅ p W=\sqrt{\dfrac{a\cdot(2-b)}{2b\cdot p}} W=2bpa(2b) 公式去求 a,b,同时也不能像 Scalable TCP 那样改变 ACK 时钟处理的行为,否则那就是 Scalable TCP 了。HSTCP 的路子是分段拟合不同 a,b 的 response curve: W = a ⋅ ( 2 − b ) 2 b ⋅ p W=\sqrt{\dfrac{a\cdot(2-b)}{2b\cdot p}} W=2bpa(2b) ,具体来讲看下图:
在这里插入图片描述

注意与标准 Reno TCP 的 response curve 黄色线平行的不同 a,b 参数线,图例上都有,它们与 HSTCP 的 response curve 蓝色粗线均有交点,选择几个典型的 a,b 参数,获得各交点的 w 坐标,以这些坐标为界,当 cwnd 达到某个 w 界标后,采用该界标的 a,b 参数直到 cwnd 到达下一个界标 w。

可从 RFC3649 了解整个待定系数的过程:
在这里插入图片描述

Linux kernel 的 HSTCP 实现 中有一张大表,数据均来自该 RFC 建议。

来,看一个不同网络容量下 HSTCP 锯齿的观感:
在这里插入图片描述
看,是不是管道容量越大,锯齿越细,这就是 “可扩展性”!

最后,我们发现 HSTCP 与 Scalable TCP 很像,均做到了 “在大容量网络对 p 的容忍”,即让 response curve 更陡峭,为了做出比较,我将 Scalable TCP 的 curve 也一并画入:
在这里插入图片描述

可见 HSTCP 与 Scalable TCP 何其相似,和 Scalable TCP 固定 AIMD 步频不同,HSTCP 也具有 “可扩展性”,但它体现在 “当前探测的管道容量越大,Additive Increase 就越快,Multiplicative Decrease 比例就越低”,容量越大,就要 capacity-seeking 追得越快,而出现拥塞后的 robustness 容忍度也越大,相对也就不需要过激 md。

这就是 Scalable TCP,HSTCP 的路线,与 BIC,CUBIC 不同,但相似,它们旨在解决类似的问题,提供了不同的方案和迭代路线,《TCP/IP 详解》中提到的 “长肥管道” 问题在不断求解的过程中被解决,但总留下一些尾巴供给下一个挑战者。

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

上一篇:RTOS系统移植


下一篇:程序的开发流程