低时延,可扩展的 l4s 拥塞控制算法

发布时间:2023年12月27日

最好的拥塞控制算法是维持不拥塞状态。

低时延不必多说,可扩展意思是无论流再多,也要低时延,时延不随流数量增加而增加。遗憾的是,由于缺乏足够信息,任何端到端算法都无法同时满足低时延和可扩展,甚至一个都满足不了。
当提到 vegas 可扩展时,并非指它的低时延可扩展,相反,如果如 vegas 约束 “每条流在 buffer 中滞留 alpha 个报文”,满足以下不等式即可:

α t q u e u i n g < 吞吐 = W t c u r r < β t q u e u i n g \dfrac{\alpha}{t_{queuing}}<吞吐=\dfrac{W}{t_{curr}}<\dfrac{\beta}{t_{queuing}} tqueuing?α?<吞吐=tcurr?W?<tqueuing?β?

很明显,排队时延和 rtt 可同步增大,如果有 n 条流,就会带来 n ? α B W t o t a l \dfrac{n*\alpha}{BW_{total}} BWtotal?n?α? 的时延,这违背了低时延可扩展性,它自己也这么说(vegas 论文 5.3 Queue Behavior):

Given that Vegas purposely tries to occupy between one and three extra buffers along the path for each connection, it seems possible that persistent queues could form at the bottleneck router if the whole world ran Vegas. These persistent queues would, in turn, add to the latency of all connections that crossed that router.

尝试修正它是徒劳的,必然掉入 bbr 主动排空 buffer 再主动 probe 的圈套,破坏了 vegas 带宽自适应能力。良性的 vegas 似乎已经是无路由器辅助的算法中 “效能 = 吞吐/时延” 的上限,难再进展。

没有路由器(交换机,基站)协助,端到端拥塞控制就是死胡同,折腾不出什么花样,现在 l4s 都标准化了,还有人迷信精确的闭环端到端算法,不可理喻又匪夷所思。

rfc9330 强调可扩展算法在不随流量变化的时间从拥塞中恢复,但我强调另一面,如果拥塞从不发生,并且稍微排队(再次强调,为获得 vegas 自适应能力),可扩展性意味着排队时延不随流数量而变化。

dctcp 算个可扩展 “拥塞控制” 算法,tcp prague 也算,但结合 l4s 框架的 vegas 是一个 “无拥塞” 的低时延算法。

把 vegas 约束颠倒一下,不再约束 buffer 中保留固定数量报文,而是约束任意报文在 buffer 中滞留固定时间,问题迎刃而解。

只有 1 条流,buffer 中是 a 个报文,2 条流就是 a / 2 个报文,n 条流就是 a / n 个报文,无论多少条流,buffer 中总报文数量都是 a,这就保证了时延是固定的,由于 buffer 中保留了报文,和 vegas 类似,sender 可自动获取退出流出让的带宽,也能动态出让带宽给新流。

如果没有路由器协助,根本无法完成上述过程,因为不知道 n。但有了 l4s 的思路,这件事就很简单:

α n < W ? t c u r r ? t b a s e t c u r r < β n \dfrac{\alpha}{n}<W*\dfrac{t_{curr}-t_{base}}{t_{curr}}<\dfrac{\beta}{n} nα?<W?tcurr?tcurr??tbase??<nβ?

在路由器将信息通知给 sender 之前,sender 必须支持非整数 cwnd,比如 cwnd = 3 / 4,可以在 4 个 rtt 中 pacing 3 个报文来处理。

一个简单但不易实现的方法是路由器将 n 告诉 sender,然后 sender 不断调整 alpha,beta。考虑到统计波动,在 n 振幅越过一个合理区间时,比如变化量超过总量 1 / 5 时才播报 n。但由于 l4s 并不支持回传整数给 sender,但 dcn 场景下那些小经理们随意自研的非标方案可考虑。

另一个方案比较容易实现,就是动态平衡,路由器算法如下:

  • 设 i = 0, α \alpha α为该路由器配置的固定(为了保留 vegas 的动态自适应能力)排队数量,固定 3*m 个 queue[3][m],。
  • 每个 packet 根据 5-tuple 被 hash0(tuples, i) 到某个 queue[i%3]。
  • 以 T = 5ms 为周期统计 m 个 queue[i%3] 中报文数量超过 α m \dfrac{\alpha}{m} mα?中最长的那个,连续发送 2 个周期 ecn。不足 α m \dfrac{\alpha}{m} mα?的 queue 中取最小的那个,连续发 2 个周期的 “不足”(可选)。
  • queue[i%3] 开始发 ecn 的周期,开始将报文 hash1(tuples, i) 进 queue[i%3 + 1]。
  • queue[i%3 + 1] 开始发 ecn 的周期,开始将报文 hash2(tuples, i) 进 queue[i%3 + 2]。
  • i++,重复第 2 步。

sender 端的 vegas 很简单:

  • 连续收到大于 5ms 的 ecn,n += n / 5(或 n / 10,或 n++)。
  • (可选)连续收到大于 5ms 的 “不足”,n -= n / 5(或 n / 10,或 n++)。

sender 可以不响应 ecn,但路由器 aqm 会教它做人,超过一定阈值也会丢包。

就这样摇摇晃晃保证每一条流公平分享瓶颈带宽并保持低时延,这就是可扩展性。当然,T 不 TCP 不重要,我可能会给出新协议以适配 l4s:

  • the Scalable congestion control on the sending host;
  • the AQM at the network bottleneck; and
  • the protocol between them.

下面的摘录,来自 rfc9330:

But first, the main point to grasp is that low latency is not provided by the network; low latency results from the careful behaviour of the Scalable congestion controllers used by L4S senders. The network does have a role, primarily to isolate the low latency of the carefully behaving L4S traffic from the higher queuing delay needed by traffic with preexisting Classic behaviour.

端到端的 vegas 太过谨慎且脆弱,但辅以 l4s,它很容易变得可用。

低延时,可扩展,这才是可控的因素,而高带宽不是。带宽是资源,而低延时和可扩展是调度。l4s + vegas 比 l4s + dctcp ~ tcp prague 更合时宜。

aimd(可由 reno,cubic 等 loss-based 算法等价) 可阻止拥塞崩溃,但它做不到无拥塞,如 vegas 指出( 5.2 Stability)的,它制造拥塞(先污染后治理…):

Up to the point where the window can be greater than one maximum segment size, Vegas is much better than Reno at recognizing and avoiding congestion—we have already seen that Reno does not avoid congestion, on the contrary, it periodically creates congestion.

在窗口可以小于 1 个 mss 后,配合 l4s 网络设施,事情将变得更好。

但标准化依然倾向于 aimd,因为它能确保可用性,公平性和稳定性三大刚需,本文的额外算法只能供经理杂耍

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

文章来源:https://blog.csdn.net/dog250/article/details/135232901
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。