Skip to content

TCP拥塞控制之CUBIC

Last updated on 2021年3月24日

内容纲要

CUBIC是当前Linux系统上默认的拥塞控制算法。它的拥塞控制窗口增长函数是一个三次函数,这样设计的目的是为了在当前的快速和长距离网络环境中有更好的扩展性。CUBIC的拥塞窗口增长独立于RTT,因此能更好的保证流与流之间的公平性。

问题是什么

当今的因特网朝着速度更快,距离更长的趋势发展,致使针对传统网络设计的TCP拥塞控制算法在性能受到了挑战。上面的网络特性用一个专业名词描述叫做高BDP(bandwidth and delay product),它代表了带宽被完全利用时网络中能容纳的数据包总量。 传统的TCP拥塞控制算法,例如TCP-Reno,TCP-NewReno,TCP-SACK等之所以在新环境下不能充分利用网络带宽,主要是因为在进入拥塞避免阶段后,它们的拥塞窗口每经过一个RTT才加1,拥塞窗口的增长速度太慢,当碰上高带宽环境时,可能需要经历很多个RTT,拥塞窗口才能接近于一个BDP。如果是短流,可能拥塞窗口还没增长到一个BDP,数据流就已经结束了,致使网络带宽浪费和降低用户体验。

已存在方法

为了解决上面提到的网络带宽低利用率问题,有很多新的TCP变体被提出来,例如FAST,HSTCP,STCP,HTCP,SQRT,West-wood和BIC-TCP。这些算法都号称能在很短的时间内提高网络传输速率。在Linux内核2.6.8版本里,BIC-TCP被选为默认算法,其他算法也实施在Linux内核里作为可选项。BIC-TCP相比其他算法的优点是其稳定性。下面先简单介绍下BIC-TCP算法。

解决方法

BIC-TCP

BIC-TCP采用二分搜索的方式来决定拥塞窗口的增长尺度,首先它会记录拥塞窗口的一个最大值点,这个最大值就是TCP最近一次出现丢包时拥塞窗口的值;还会记录一个最小值点,即在一个RTT周期内没有出现丢包事件时窗口的大小。二分搜索记录最小值和最大值的中间点,当拥塞窗口增长到这个中间值且没有出现丢包的话,就说明网络还可以容纳更多的数据包。那么将这个中值设为新的最小值,在新的最小值和最大值间搜索中间值。在拥塞窗口的值还远没有达到BDP时,其增长速度很快;相反,当拥塞窗口的值接近于BDP时,其拥塞窗口增长函数是一个简化的对数凹函数。这个凹函数使拥塞窗口在饱和点或平衡点比凸函数或线性函数保持更长的时间,在饱和点处,凹函数和线性函数它们具有最大的窗口增量,因此在丢包发生时会出现大量的数据包被丢失。 BIC-TCP的主要特征是在前面说过的其独特的窗口增长函数,图1给出了BIC-TCP的窗口增长函数。当出现丢包事件时,BIC-TCP通过乘以因子ββ来缩小窗口,缩小之前的窗口大小被设置为最大 W_{max} ,并且缩小之后的窗口大小被设置为最小值 W_{min}。 然后,BIC-TCP使用这两个参数执行二分搜索,拥塞窗口的下一个取值会是 W_{max}W_{min}之间的“中点” W_{mid} 。 为了防止拥塞窗口从 W_{min}增长到 W_{mid} 的步长 step太大,BIC-TCP还设置了一个常数 S_{max},当 step > S_{max}”> 时,BIC-TCP会取下一个增长点为 <img src= 而不是 W_{mid},如果没有出现丢包的话,再更新 W_{min},直到 step < S_{max}为止。与此同时BIC-TCP还设置一个另一个控制参数 S_{min},当窗口增量小于 S_{min}时,BIC-TCP会将当前拥塞窗口值设为最大值。 如果窗口增长超过最大值,则说明当前窗口最大值还不是一个饱和点,网络还可以容纳更多的数据包,窗口还有增长的空间,一个新的窗口最大值需要被探索。于是BIC-TCP会进入一个新的阶段,叫做最大值探索阶段。最大探测使用一个与在加法增长和二分搜索阶段(这是对数;其倒数将是指数)完全对称的窗口增长函数。图1中给出了在最大探索阶段期间的窗口增长函数。在最大探测期间,窗口最初缓慢地增长以发现附近新的最大值,经过一段时间的缓慢增长,如果没有找到新的最大值(即,没出现包丢失),则它猜测新的最大值离得很远,所以它给窗口大小增加一个大的固定增量,使用加法增加切换到更快的增加速度。BIC-TCP的良好性能来自 W_{max} 附近的缓慢增加和在加法增加和最大探测期间的线性增加。

CUBIC

CUBIC是BIC-TCP的下一代版本。 它通过用三次函数(包含凹和凸部分)代替BIC-TCP的凹凸窗口生长部分,大大简化了BIC-TCP的窗口调整算法。实际上,任何奇数阶多项式函数都具有这种形状。三次函数的选择是偶然的,并且不方便。CUBIC的关键特征是其窗口增长仅取决于两个连续拥塞事件之间的时间。一个拥塞事件是指出现TCP快速恢复的时间。因此,窗口增长与RTT无关。 这个特性允许CUBIC流在同一个瓶颈中竞争,有相同的窗口大小,而不依赖于它们的RTT,从而获得良好的RTT公平性。而且,当RTT较短时,由于窗口增长率是固定的,其增长速度可能比TCP标准慢。 由于TCP标准(例如,TCP-SACK)在短RTT下工作良好,因此该特征增强了协议的TCP友好性。

CUBIC的窗口增长函数

BIC-TCP在高速网络中实现了良好的可扩展性,在自身的竞争流之间是公平的,并且具有低窗口振荡的稳定性。但BIC-TCP的窗口增长函数对于TCP来说还是过于激进,特别是在短RTT或低速网络中。于是有了CUBIC,CUBIC保留了BIC-TCP的稳定性和可扩展性的优点,同时简化了窗口控制和加强了TCP友好性。

CUBIC的窗口增长函数是一个三次函数,非常类似于BIC-TCP的窗口增长函数,CUBIC的函数图像如图2所示。CUBIC的详细运行过程如下,当出现丢包事件时,CUBIC同BIC-TCP一样,会记录这时的拥塞窗口大小作为 W_{max},接着通过因子ββ执行拥塞窗口的乘法减小,这里ββ是一个窗口降低常数,并进行正常的TCP快速恢复和重传。从快速恢复阶段进入拥塞避免后,使用三次函数的凹轮廓增加窗口。三次函数被设置在W_{max}处达到稳定点,然后使用三次函数的凸轮廓开始探索新的最大窗口,如果新的最大窗口存在的话。 CUBIC的窗口增长函数公式如下所示:W(t)=C(t−K)^{3}+W_{max} \qquad(1)\\这里,C是一个CUBIC的参数,t是从窗口上次降低开始到现在的时间,是一个弹性值,而K是上述函数在没有进一步丢包的情况下将 W增加到 W_{max}经历的时间,其计算公式如下:

K=\sqrt[3]{{\frac{W_{max}*\beta}{C}}} \qquad(2)\\

在拥塞避免阶段每收到一个ACK,CUBIC都会使用方程(1)计算在下个RTT的窗口增长速率。CUBIC使用 W(t+RTT) 作为拥塞窗口的候选值,假设当前拥塞窗口大小为 cwnd 。根据 cwnd 的值,CUBIC有三种运行模式。首先,如果 cwnd小于(标准)TCP在上次丢包事件之后t时刻到达的窗口大小,那么CUBIC处于TCP模式(我们将在下面描述如何根据时间确定标准TCP的窗口大小)。否则,如果 cwnd小于 W_{max} ,那么CUBIC在三次函数的凹轮廓区域,如果 cwnd 大于 W_{max} ,那么,CUBIC处于三次函数的凸轮廓区域。

凹区域

当在拥塞避免阶段收到一个ACK,如果协议不处于TCP模式,且 cwnd 小于 W_{max},那么,协议就处于凹区域,在这个区域, cwnd 的增量为:\frac{W(t+RTT)-cwnd}{cwnd}\\

凸区域

如果协议不处于TCP模式,且 cwnd大于饱和点 W_{max},那么协议处于凸区域, cwnd的增量为:\frac{W(t+RTT)-cwnd}{cwnd}\\其实凸区域的增长函数和凹区域的增长函数一样,只不过凸区域越过了饱和点,而其区域没有越过饱和点。

乘法降低

当出现数据包丢失时,CUBIC会通过乘以因子\beta来降低拥塞窗口,这里取 β=0.2,设置 \beta<0.5 的副作用是收敛较慢。虽然更适应性的设置会导致更快的收敛,但是会使协议的分析变得更加困难,并影响协议的稳定性。

快速收敛

为了提高CUBIC的收敛速度,在协议中加入了启发式。当新的流量加入网络时,网络中的现有流量需要放弃其带宽份额,以使新流量有一定的增长空间。下面详细描述一下快速收敛的过程。在发生丢包前,CUBIC会记录一个最大窗口值 W_{max} ,当发生丢包后,在降低窗口前,CUBIC又会记录当前的窗口值作为新的 W_{max} ,为了不至于混淆,可以将之前记录的 W_{max}标记位 W_{last\_max} 。当发生丢包时,CUBIC会比较 W_{last\_max}W_{max} 大小,如果 W_{max} 小于 W_{last\_max},这表明由于可用带宽的变化,该流所经历的饱和点正在降低。这种情况下,CUBIC的做法是通过进一步的减小 W_{max} 来释放更多的可用带宽。

参考文献

1、https://tools.ietf.org/pdf/rfc8312.pdf 2、https://dl.acm.org/doi/pdf/10.1145/1400097.1400105

+3
Published inTCP/IP协议栈

One Comment

  1. 匿名 匿名

    到此一游

    0

发表评论

您的电子邮箱地址不会被公开。