拥塞控制算法

发布时间 2023-04-09 01:19:02作者: codestacklinuxer

典型拥塞控制算法思路

在互联网发展的过程当中,TCP 算法也做出了一定改变,先后演进了 Reno、NewReno、Cubic 和 Vegas,这些改进算法大体可以分为基于丢包和基于延时的拥塞控制算法。 基于丢包的拥塞控制算法以 Reno、NewReno 为代表,这类基于 AIMD 的算法只要未检测到丢包,均是无条件 AI(加性增窗)的,如此一来拥塞窗口总会超过实际宽带的限制。

理想情况下,如果我们把网络看作是一根粗细均匀管道,那么带宽就是该管道的横截面积,它一方面表示主机的发包能力,另一方面也表示网络的吞吐率。如果网络带宽被一条 TCP流独占,那么 Reno 的拥塞窗口理论上会无限 AI 涨下去,不会出现锯齿,而是一条直线。

很明显 Reno 并不理解宽带的概念,它只知道拥塞窗口。这里假如同一个网络管道中又出现一条 TCP 流,那么二者势必要分享带宽。需要分享出让带宽的信号就是拥塞丢包,按照 AIMD 窗口控制理论,当发生拥塞时,二者均会丢包,二者均要执行 MD(乘性减窗),然而如果第一个 TCP 流的窗口已经增长的过大,即便它执行了 MD,也依然远大于实际可用带宽,拥塞将持续,丢包将加剧。

因此,拥塞窗口必须维持在刚刚够用的状态,推荐这里芝加哥洛约拉大学关于 NewReno 的讲解,在 Linux Kernel 2.6.13 以前的 Reno 算法中,拥塞窗口甚至就是无限增长。

拥塞控制的目标之一就是探测瓶颈带宽,控制主机发包速率使流量恰好通过瓶颈带宽。理想单流假设的前提下,主机的发包能力决定了拥塞窗口的上限,这个过程无需任何外在干预,单流完全可以自适应网络带宽,Reno 算法只是单纯的将拥塞窗口慢启动或者 AI 到 BDP 而已(在此我们忽略随机噪声丢包),理想单流的情况,网络就是一条单纯的管道,并不需要 Buffer。

然而如果多条流复用同一个网络,网络管道必然会过载,此时需要需要引入部署在交换节点 Buffer 来暂存过载的数据包,如果没有 Buffer,网络将退化到 CSMA/CD 总线,丢弃所有过载的数据包。

BufferBloat

学习现有的经典算法是非常有意义的事情,通过分析它们的优点和缺陷,触类旁通能对新的算法有更好更深的理解,这里 Buffer 出现的成因其实说明得非常明白了

TCP Queue Sizes suggested that an optimum backbone-router buffer size for TCP Reno might be hundreds of megabytes. Because RAM is cheap, and because more space is hard to say no to, queue sizes in the real world often tend to be at the larger end of the scale.

BufferBloat 很大的成因在于 Reno 家族(包括 BIC/CUBIC)的 CC 算法看待网络的方式。 Reno 的本质问题在于它将网络看成了一个容器而忽略了带宽。 我们可以从 Reno 家族的拥塞控制变量 cwnd 中看出来,cwnd 的单位是数据包的个数,而带宽的单位则是单位时间内的数据包的个数。这里可以看出,Reno 家族是 Buffer 友好的,却不是带宽友好的。

BBR正好与此相反,我们看到BBR的拥塞控制变量 Pacing Rate 的单位就是带宽的单位。因此 BBR 是带宽友好的,却不是 Buffer 友好的。现在让我们想象一个理想的 BBR 算法实现,并且整个网络均使用这个 BBR 实现进行拥塞控制。在这种情况下,路由器的 Buffer 将不再有大用,因为 BBR 总是可以通过不断测量瓶颈带宽和最小RTT(任何排队都会让RTT增加),最终收敛到所有的流均不在 Buffer 中排队。如果整个网络均切换到 BBR 进行拥塞控制,这势必会促使路由器厂商逐渐放弃将 Buffer 大小作为重要性能指标的策略,从而缓解整个网络的 BufferBloat

  现实中往往都是 BBR 与 Reno 共存状态,我们可以设想一个拥有无穷大的 Buffer 的网络,Reno 和 BBR 共享该网络的资源,此时 Reno 会倾向尽可能占满更多的 Buffer,这个行为会导致队列不断变长,测量得到的 RTT 不断增加,这会将 BBR 不断逼入 Probe RTT 阶段的超慢速传输。虽然现实网络中不可能拥有无穷大的 Buffer,但可以确定的是,即便是有限的 Buffer,由于空闲 Buffer 耗尽丢包导致的 Reno 进行 MD 以及重传行为也仅仅是缓解了上述 BBR 的窘境,而并非解决了该问题。