浅析TCP Vegas拥塞控制算法

TCP拥塞控制算法是令TCP协议保持高效率传输的重要设计,不过由于大多数人平时并不需要关心它,大家并不会深入去了解各种拥塞协议之间的差异。提到TCP拥塞控制算法,总令人想到一大堆专业名词,例如拥塞窗口、重传、丢包、RTT……等等,不过其本质可以用”排队论”(Queuing Theory)进行解释。本文将尝试用通俗易懂的方式讲解TCP Vegas算法的设计与实现(其他拥塞控制算法其本质并无太大差异,在了解Vegas算法的基础上很容易触类旁通)

基本原理

先让我们看看维基百科上是如何解释TCP Vegas算法的:

TCP Vegas is a TCP congestion avoidance algorithm that emphasizes packet delay, rather than packet loss, as a signal to help determine the rate at which to send packets.——Wikipedia

TCP Vegas算法是一种拥塞避免算法,它通过关注延迟而不是关注丢包来决定如何调节发包率。

TCP-BBR-pipe

在很多解释Vegas或者BBR算法的文章中,都扔出这张经典的水管流量示意图,实际上我个人认为这张图片并不够形象,因为我们的直觉会认为水管的流量是由外部水压和水管宽度共同决定的,而不是仅仅靠水管宽度。

img

让我们做一个更形象的比喻,无论是坐地铁、火车还是飞机,我们都需要过安检,当人流量比较大的时候,会有专门的人负责控制通过安检通道的人数,我们先称这个控制流量的角色为观察员。为了尽可能提高通过的效率,观察员需要尽量让安检人员持续有活儿干并且不能让太多人涌进来影响安检效率。让我们把这个例子和专业术语对应起来:

  • 每次允许通过的最大人数cwnd(拥塞窗口尺寸)
  • 假设完全没有人排队时,执行完一次安检的时间为RTTnoload
  • 而实际安检的时间RTTactual = RTTnoload + 排队时间
  • 期望通过速率Expect = cwnd/RTTnoload
  • 实际通过速率Actual = cwnd/RTTactual
  • 速率差值Diff = Expect-Actual

由上述条件我们可以作如下推导:

  • Diff = queueSize/RTTnoload = cwnd/RTTnoload - cwnd/RTTactual = cwnd(1/RTTnoload - 1/RTTactual)
  • 最后推导出queueSize = cwnd * (1 - RTTnoload/RTTactual)

从这个公式我们可以看到排队的队列大小与观测到的RTTnoload和RTTactual直接相关联,而且趋势是若RTTactual越接近RTTnoload(比值接近1),则队列尺寸越小。

拥塞控制

Vegas 定义了两个阈值α和β,当 queueSize > β 时,拥塞窗口减小,当 α <= queueSize <=β 时,拥塞窗口不变,当 queueSize < α 时,拥塞窗口增加。α和β的通常是一个较小的取值,例如α=1, β=3,则表示在传输过程中最多只使用2个buffer。这样可以保证系统容量评估得尽可能精准,但是带来的坏处是需要进行非常频繁的调节,适当增大α,β的范围可以减少频繁的调整cwnd。

Vegas算法被认为是最为平滑的控制算法,因为它的通常采用线性的方式增减cwnd(与之相对的是例如slow-start之类的方式),例如每次+1/-1,优点依然是精准,缺点是需要较长的时间才能找到那个平衡点。

虽然我们重点讲的是Vegas算法,但综上所述,拥塞控制协议的原理可以归纳为通过判断某些特定的条件(例如Vegas以RTT为基准,Reno以丢包为条件)确定系统是否在恶化,然后使用特定的算法(例如线性增减、slow-start等)对cwnd进行调节。

一些思考

Vegas算法的缺点

Vegas算法以RTT作为判断依据,如果系统中允许存在超大的buffer或者允许一定程度的服务恶化,则该算法会无法正常工作。这些情况在现实场景中是非常常见的,所以Vegas最终没有广泛部署。

现实场景下的利用

拥塞控制协议设计非常巧妙,那我们还能用在其他地方产生价值吗?在服务流量限制这个场景中,就可以参考拥塞控制协议。以Vegas算法为例,我们同样可以通过计算RTT来调节流量,如果我们有无穷多的资源可以动态扩容,并且永远给用户提供最佳的请求响应速度,那我们基本可以照搬Vegas算法,不过现实情况下我们需要做一些改进。

  • 我们通常不可能有近似无穷多的资源可以动态扩容,也不必永远给用户提供最佳的请求速度,在用户能接受的范围内我们应该适当允许RTTactual > RTTnoload,以提高资源利用率,这里我们可以将RTTnoload换成过去某段时间内统计到的一个基线数据,该值应当不会使服务不可用同时又有较高的资源利用率。
  • 频繁的进行cwnd的调节没有太大必要,可以适当增大α,β的差值。
  • Vegas算法探测到服务恶化后会不断缩小cwnd,但如果由于其他的一些原因(例如其他的服务抢占了系统资源)导致RTTactual再也不可能接近RTTnoload则该算法会导致最后流量跌零,所以RTTnoload不应该固定为历史采样的最小值,可以参考BBR算法的周期性探测计算RTTnoload。

参考文档

坚持原创技术分享,您的支持将鼓励我继续创作!