拥塞控制的一般原理_拥塞控制的四种算法

0、一些基础知识

0.1 名词解释

拥塞：在计算机通信中，当某一子网的分组数过多，超过了Link的Bandwidth时，所有的分组无法全都完成传输，会出现丢包、延时，甚至死锁的现象。因此，需要让发包的一方通过过去的先验知识去控制发包的行为， 这就是拥塞控制。

拥塞窗口（cwnd）:Congestion Window，发送端在一个RTT内能发送的窗口大小。拥塞窗口的大小取决于网络的拥塞程度，并且动态地在变化。发送方让自己的发送窗口等于拥塞窗口。如果再考虑到接收方的接收能力，那么发送窗口还可能小于拥塞窗口。
$$发送窗口=min（cwnd，rwnd）$$
rwnd是接收窗口。
发送方控制拥塞窗口的原则是：只要网络没有出现拥塞，拥塞窗口就再增大一些，以便把更多的分组发送出去。但只要网络出现拥塞，拥塞窗口就减少一些，以减少注入到网络中的分组数。

RTO:Retransmission Time Out，超时重传。

RTT:Round-trip time，往返时间。

ACK:Acknowledgement，TCP是一个具有可靠性的协议，发送方给接收方发送数据，每收到一个数据包，接收方就会给发送方发送一个确认tcp报文，置ACK为1（ACK是TCP报文中flags之一）。

MSS:maximum segment size,最大报文段长度。

一、TCP Tahoe

TCP Tahoe协议是TCP最早的TCP拥塞控制版本。其拥塞控制的实现主要包括三个机制：慢启动、拥塞避免和快速重传。

• 慢启动：当连接建立时，初始化cwnd，设置为一个MSS大小。设置ssthresh阈值的大小为64KB。
  ssthresh：slow start thresh，慢启动门限值。cwnd超过该值则进入拥塞避免。

• 拥塞避免：使用AI(加性增)机制，只要有一个数据包丢失则认为网络拥塞。（实际上这么认为是不对的，丢包也可能是随机丢包，所以这样会浪费很多的带宽） 此时，将ssthresh设置为当前cwnd大小的一半，并回到慢启动阶段。

• 快速重传：当收到三个重复ACK时，不必等待RTO，直接重传丢失的数据包。(此时认为收到3个重复的ACK时，该包已丢失。)

TCP Tahoe的cwnd的变化图如下：每次遇到丢包和3个重复ACK时，都会将拥塞窗口置0

在NS3中的仿真图如下：

TCP Tahoe会呈现出周期性的变化。

二、TCP Reno

相比于Tahoe，TCP Reno多了一个机制：快速恢复（Fast Recovery）。
快速恢复： 当收到三个重复的ACK进入快速恢复状态。Reno会把当前的ssthresh的值设置为当前cwnd的一半，但是并不会回到slow start阶段，而是将cwnd设置为（更新后的）ssthresh+3MSS，之后cwnd呈线性增长。

这里有一个快速恢复的解读：
快速恢复是基于数据包守恒的原则，即同一时刻能在网络中传输的数据包是恒定的，只有当旧数据包离开网络后，才能发送新数据包进入网络。一个重复ACK不仅意味着有一个包丢失了，还表示有发送的数据包离开了网络（因此需要cwnd需要+1，因为此时网络中能多承受一个包），已经在接收区的缓冲区中，不再占用网络资源，于是将拥塞窗口加一个数据包大小。

这里给一个TCP Reno的状态机：

TCP Reno的cwnd的变化图如下：每次遇到丢包时，都会将拥塞窗口置0；每次遇到3个重复ACK时，都将cwnd=ssthresh+3MSS

在NS3中的仿真图如下：

其cwnd窗口同样呈现周期性变化。AIMD机制导致了其锯齿状的cwnd曲线。

三、TCP NewReno——针对Reno将一次拥塞识别为多次拥塞的问题

NewReno是Reno的改进版，针对Reno存在的一些问题，提出相应的机制进行改进。

TCP Reno 提出的快速恢复算法提高了丢失报文后的吞吐量和顽健性，但是：
仅考虑了每次拥塞发生时只丢失一个报文的情形。实际网络中，一旦发生拥塞，路由器会丢弃大量的报文，即一次拥塞中丢失多个报文的情形很普遍。

如果在多个丢包的情形下使用Reno：
Cwnd和ssthresh多次进行减半，即乘性减，TCP的性能急剧下降。
并且由于窗口急剧下降，（当发送窗口小于3时）无足够的重复ACK可以触发快速恢复，只能等待超时重传。TCP Reno 终端会陷入仅通过传输超时来发现报文丢失的困境中。——等待超时是一件很久的事情，正常是3个RTT以上，极大的浪费了带宽。

因此，为了应对该情况，提出了TCP NewReno （这些算法都应该算是TCP Reno的变种，都是启发式的指定一些规则去解决某些情形）——总有一天这种设计架构会制约congestion control的发展，并且目前已经出现：
在只丢失一个数据包的情况下，NewReno和Reno的处理方法是一致的。
而在同一个时间段丢失了多个包时，NewReno做出了改进：
Reno快速恢复算法中，发送方只要收到一个新的ACK就会退出快速恢复状态而进入拥塞避免阶段，而在Neweno算法中，只有当所有丢失的包都重传并收到确认后才退出。

3.1具体实现

在TCP NewReno中提出两个概念：部分应答（PACK，Partial ACK）、恢复应答（RACK，Recovery ACK）。

记TCP发送端快速恢复阶段中接收到的ACK报文（非冗余ACK）为ACKx。

记在接收到ACKx时TCP终端已发出的序列号（SN）最大的报文是PKTy。

• 部分应答：当ACKx不是PKTy的应答报文，即它们对应的Number不相等，则称报文ACKx为部分应答

• 恢复应答：当ACKx恰好是PKTy的应答报文，即它们对应的Number相等，则称报文ACKx为恢复应答

在TCP NewReno中，接收到PACK并不会退出快速恢复，接收到RACK才会退出快速恢复阶段。因此在一次拥塞导致多个loss报文时，只会降低一次的cwnd。

• 基本步骤如下：
  1.重新定义恢复阶段
  2.进入恢复阶段后，发送端重传被认定为丢失的报文，设置慢启动阈值（ssthresh）和拥塞窗口大小（cwnd）。ssthresh = cwnd/2，cwnd = ssthresh + 3MSS。
  3.收到一个重复ACK，cwnd=cwnd+MSS。
  4.当收到PACK（部分应答）时，发送端重传PACK所确认报文的下一个报文，如果拥塞窗口允许，继续发送新的数据包。
  5.当收到RACK（确认应答）时，发送端认为拥塞中所有被丢弃的报文都已经被重传，拥塞结束，设置cwnd=ssthresh并退出快速恢复状态。

TCP NewReno的cwnd窗口变化如下：

需要在同时发生多个丢包时，才看得出与Reno的差别。

四、TCP Cubic

TCP Cubic是目前Linux系统、Windows系统上默认的拥塞控制算法。

4.1 为什么会有Cubic呢?

在当时带宽比较受限的年代（KB级别），TCP NewReno等拥塞控制算法并不会造成很多的带宽浪费（本来的瓶颈带宽就不大）。但随着网络速度的发展，传统的TCP NewReno等算法在拥塞避免阶段每个RTT只增长一个拥塞窗口的操作已经无法匹配网络的速率，一些短流的拥塞窗口还没达到BDP就已经结束了。因此，需要有新的算法来提高网络带宽的利用率。

4.2 BIC算法

CUBIC算法的前身是BIC算法。BIC算法认为：TCP调制cwnd窗口的本质是找到一个适合当前网络的一个发送窗口，传统的AIMD其实是一个类似遍历搜索的过程。BIC认为这个最适合的窗口值位于1至无穷大之间，因此将cwnd窗口的选择问题类似与一个二分搜索的问题。

相比于Reno，BIC算法改进了Reno在快速恢复阶段后的行为，在BIC中，不进入拥塞避免阶段，而是进入一个二分搜索的阶段。

二分搜索阶段：当发生丢包时，认为cwnd窗口的最大值为$W_{max}$，乘法减小后的窗口值为最小值$W_{min}$。BIC算法认为最适合的窗口值位于$W_{min}$和$W_{max}$之间，因此在该区间进行二分搜索，即下一个cwnd为$cwnd=(W_{min}+W_{max})/2$。然后再更新$W_{min}=cwnd$。

但当当前的最大拥塞窗口比较大时，发生丢包后下一次窗口的更新幅度比较大，可能会造成传输的抖动，即$(W_{max}+W_{min})/2$与$W_{min}$相差比较大。此时，BIC设置了一个cwnd增幅限制$S_{max}$，当$[(W_{max}+W_{min})/2-W_{min}]>S_{max}$时，cwnd为$cwnd=W_{min}+S_{max}$，而不是$W_{mid}$。

BIC还有一个缺点，就是$W_{max}$可能并不是网络的瓶颈带宽，此时就需要BIC去探测网络的带宽，直至发生丢包，该阶段称为$Max-Probe$阶段。

虚线为二分搜索阶段的$W_{max}$窗口值。上图右侧为$Max-Probe$阶段，最初缓慢的增加，当一直未丢包时，猜测最大带宽离得很远，因此逐渐增加探测的速度。

4.3 CUBIC算法

CUBIC论文链接：CUBIC: a new TCP-friendly high-speed TCP variant
CUBIC针对BIC算法进行改进，替换了BIC的增长函数，使其更光滑，并且降低BIC算法在不同阶段（二分搜索、最大探索、$S_{max}$、$S_{min}$）的复杂度。CUBIC用三次函数代替了BIC原有的窗口增长函数。
CUBIC的窗口增长函数如下：

CUBIC的cwnd增长函数为：
$$W(t)=C(t-K{)}^3+W_{\max }$$
其中$t$为从上一次窗口减少到现在的时间，$K$为无丢包时，拥塞窗口从$W$增加至$W_{max}$的时间周期。可以观察到当$t=K$时，$W(t)=W_{max}$。其中，K为：
$$K=\sqrt[3]{\frac{W_{\max }\ast \beta }{C}}$$
其中，$\beta$与TCP的公平性有关，而$C$与Cubic的收敛速度有关。

五、

PRR

参考链接：
万字详文：TCP 拥塞控制详解
TCP NewReno

今天的文章拥塞控制的一般原理_拥塞控制的四种算法分享到此就结束了，感谢您的阅读。