一、CUBIC
参考链接：CUBIC拥塞控制算法
1. BIC
1.1 基础原理
BIC是以对数形式增大拥塞窗口，改善了之前线性增加拥塞窗口。
- 最大值：TCP最近一次出现丢包时拥塞窗口的值
- 最小值：在一个RTT周期内没有出现丢包事件时窗口的大小
- 下一个最小值：最大值最小值的中间值。
当拥塞窗口增长到这个中间值且没有出现丢包的话，就说明网络还可以容纳更多的数据包。
否则，BIC-TCP通过乘以因子 β 来缩小窗口。缩小之前的窗口大小被设置为最大值Wmax ，并且缩小之后的窗口大小被设置为最小值Wmin
1.2 一些细节
-
步长限制：
- 为了防止拥塞窗口从Wmin 增长到 Wmax 的步长step太大，BIC-TCP还设置了一个常数Smax。
- 与此同时BIC-TCP还设置一个另一个控制参数Smin ，当窗口增量小于 Smin 时，BIC-TCP会将当前拥塞窗口值设为最大值。
-
最大值探索阶段：如果窗口增长超过最大值，则说明当前窗口最大值还不是一个饱和点，网络还可以容纳更多的数据包，窗口还有增长的空间，一个新的窗口最大值需要被探索。
- 使用一个与在加法增长和二分搜索阶段完全对称的窗口增长函数
- 在最大探测期间，窗口最初缓慢地增长以发现附近新的最大值
- 经过一段时间的缓慢增长，如果没有找到新的最大值（即没出现包丢失），则它猜测新的最大值离得很远，所以它给窗口大小增加一个大的固定增量，使用加法增加切换到更快的增加速度。
1.3 优缺点
- BIC-TCP在高速网络中具有良好的可扩展性、多个流竞争的公平性和低窗口振荡的稳定性。
- BIC-TCP的增长功能对于TCP来说仍然过于激进，特别是在短RTT或低速网络下。
- 窗口控制的几个不同阶段（二进制搜索增加、最大探测、Smax 和 Smin ）增加了协议实现和性能分析的复杂性。
2. CUBIC
1. 基本原理
CUBIC的关键特征是其窗口增长仅取决于两个连续拥塞事件之间的时间。
- 快速恢复阶段：
- 拥塞避免阶段：从快速恢复阶段进入拥塞避免后，使用三次函数的凸函数增加窗口。三次函数设置在 Wmax 处达到稳定点
- 新的最大窗口：如果存在新的最大窗口（网络带宽发生变化）, 然后使用三次函数的凹函数开始探索新的最大窗口。
- 拥塞窗口减小：当出现丢包事件时，CUBIC同BIC-TCP一样，会记录这时的拥塞窗口大小作为Wmax，接着通过常数因子β 执行拥塞窗口的乘法减小，这里 β 是一个窗口降低常数，并进行正常的TCP快速恢复和重传。
CUBIC的窗口增长公式：
W
(
t
)
=
C
(
t
?
K
)
3
+
W
m
a
x
(
1
)
W(t)=C(t-K)^{3} +W_{max} \qquad(1)
W(t)=C(t?K)3+Wmax?(1)
K = W m a x × β C 3 ( 2 ) K=\sqrt[3]{\frac{W_{max}\times \beta }{C} }\qquad(2) K=3CWmax?×β??(2)
| 参数 | 含义 |
|---|---|
| C | CUBIC的参数，用于控制W(t)的恢复速率，C越大越陡 |
| β \beta β | 窗口降低常数（窗口以什么比例降低） |
| W m a x W_{max} Wmax? | 出现丢包事件时的拥塞窗口大小 |
| t | 从窗口上次降低开始到现在的时间 |
K 是上述函数在没有进一步丢包的情况下将当前的拥塞窗口 W 增加到 W m a x W_{max} Wmax?经历的时间
2. 公式推导
首先，我们定义一个三次函数
W
(
t
)
=
C
(
t
?
A
)
3
+
B
W(t)=C(t-A)^{3} +B
W(t)=C(t?A)3+B
我们已知三个条件。
- 函数从 ( 0 , ( 1 ? β ) W m a x ) (0,(1-\beta )W_{max}) (0,(1?β)Wmax?)此点开始恢复
- 在经过K时间后，函数恢复到 W m a x W_{max} Wmax?
- 在K点达到极值点
所以：
{
W
(
K
)
=
W
m
a
x
W
′
(
K
)
=
0
函
数
过
(
0
,
(
1
?
β
)
W
m
a
x
)
}
\begin{Bmatrix}W(K)=W_{max} \\W' (K)=0 \\函数过(0,(1-\beta )W_{max} ) \end{Bmatrix}
????W(K)=Wmax?W′(K)=0函数过(0,(1?β)Wmax?)?????
将前两个条件带入得到：
W
(
t
)
=
C
(
t
?
K
)
3
+
W
m
a
x
W(t)=C(t-K)^{3} +W_{max}
W(t)=C(t?K)3+Wmax?
由第三个条件求得K
K
=
W
m
a
x
×
β
C
3
K=\sqrt[3]{\frac{W_{max}\times \beta }{C} }
K=3CWmax?×β??
下图是CUBIC的函数图像，图像以K为轴，极值为
W
m
a
x
W_{max}
Wmax?
3. 运行模式
在拥塞避免阶段每收到一个ACK，CUBIC都会使用公式(1)计算在下个RTT的窗口增长速率。CUBIC使用 W ( t + R T T ) W(t+RTT) W(t+RTT)作为拥塞窗口的候选值，假设当前拥塞窗口大小为 c w n d cwnd cwnd。
根据 cwnd的值，CUBIC有三种运行模式。
-
TCP友好型区域：如果cwnd 小于（标准）TCP在上次丢包事件之后 t 时刻到达的窗口大小，那么CUBIC处于TCP模式。
-
凸区域：如果cwnd 小于Wmax ，那么CUBIC在三次函数的凸函数区域。
-
凹区域：如果cwnd 大于Wmax ，那么CUBIC处于三次函数的凹区域。
3.1 TCP友好型区域
标准TCP协议在网络时延带宽积小或者RTT小的情况下表现仍不错，CUBIC被设计为在这两种情况下可以很好的兼容标准TCP协议。
算法执行过程中，每收到一个ACK后都会判断当前是否处于标准TCP阶段，即TCP友好域，以此来更好的兼容TCP。
因此需要通过TCP的AIMD（加法增、乘法减）特性并使用加法因子 α 和乘法因子 β 去估算在TCP传统拥塞算法下的拥塞窗口大小。
W
t
c
p
(
t
)
=
W
m
a
x
(
1
?
β
)
+
3
β
2
?
β
t
R
T
T
(
3
)
W_{tcp(t)} =W_{max} (1-\beta )+3\frac{\beta }{2-\beta } \frac{t}{RTT}\qquad(3)
Wtcp(t)?=Wmax?(1?β)+32?ββ?RTTt?(3)
由该函数可以看出，该函数是一个线性函数，这与TCP的线性调整拥塞窗口相符。
3.2 凸区域
当在拥塞避免阶段收到一个ACK，如果协议不处于TCP模式，且cwnd小于 W m a x W_{max} Wmax?，那么协议就处于凸区域，在这个区域，cwnd 的增量为：
W ( t + R T T ) ? c w n d c w n d \frac{W(t+RTT)-cwnd }{cwnd} cwndW(t+RTT)?cwnd?
3.3 凹区域
当前的cwnd 大于 W m a x W_{max} Wmax?时，协议就会进入凹区域。
由于 cwnd大于先前的饱和点 W m a x W_{max} Wmax? ，这表明自上次拥塞事件以来，网络条件可能受到干扰，这可能意味着在一些竞争流离开后，可用带宽会增加。
由于网络是高度异步的，可用带宽的波动总是存在的。凹区域使得窗口在开始时增长非常缓慢，并逐渐增加其增长率。
由于CUBIC正在搜索一个新的 W m a x W_{max} Wmax?，我们也将此阶段称为最大探测阶段。由于没有修改凹区域的窗口增长函数，因此两个区域的窗口增长函数保持不变。因此 cwnd的增量同样为：
W ( t + R T T ) ? c w n d c w n d \frac{W(t+RTT)-cwnd }{cwnd} cwndW(t+RTT)?cwnd?
4.一些细节
4.1 乘法因子
当出现数据包丢失时，CUBIC会通过乘法因子 β 来降低拥塞窗口，这里取β=0.2 。虽然自适应性的设置 β 会导致更快的收敛，但是会使协议的分析变得更加困难，并影响协议的稳定性。
4.2 快速收敛机制
新的流量加入网络时，网络中的现有流量需要放弃其部分带宽份额，以使新流量有一定的增长空间。
-
在发生丢包前，CUBIC会记录一个最大窗口值 W m a x W_{max} Wmax? 。
-
当发生丢包后，在降低窗口前，CUBIC又会记录当前的窗口值作为新的 W m a x W_{max} Wmax? 。
为了不至于混淆，可以将之前记录的 W m a x W_{max} Wmax?记为 W l a s t m a x W_{lastmax} Wlastmax?。当发生丢包时，CUBIC会比较 W l a s t m a x W_{lastmax} Wlastmax?和 W m a x W_{max} Wmax?的大小。
如果 W m a x W_{max} Wmax? 小于 W l a s t m a x W_{lastmax} Wlastmax? ，这表明由于可用带宽的变化，该流的窗口饱和点正在降低。这种情况下，CUBIC的做法是通过进一步的减小 W m a x W_{max} Wmax? 来释放更多的可用带宽，使得新加入的流量有一定的增长空间。