[网络协议]拥塞控制算法（二）

为了防止网络的拥塞现象，TCP提出了一系列的拥塞控制机制。

最初由V. Jacobson在1988年的论文中提出的TCP的拥塞控制由“慢启动(Slow start)”和“拥塞避免(Congestion avoidance)”组成

后来TCP Reno版本中又针对性的加入了“快速重传(Fast retransmit)”、“快速恢复(Fast Recovery)”算法

再后来在TCP NewReno中又对“快速恢复”算法进行了改进

近些年又出现了选择性应答( selective acknowledgement,SACK)算法，还有其他方面的大大小小的改进，成为网络研究的一个热点。

二、Tahoe算法

Tahoe算法只有两个状态①慢启动（SA状态）和②拥塞避免状态（CA状态）

• SA状态：拥塞窗口倍增
• CA状态：每收到一个新的ACK（或者经过一个RTT）拥塞窗口线性增长
• 设置上次拥塞窗口的值设置为境界阈值（ssthresh），来区分SA和CA状态。

Tahoe算法的惩罚比较严重。

③快重传的思想是：只要发送方收到了三个重复的ACK，就会立马重传，而不用等到RTO到达（如果没有3个重复的ACK而包丢失了，就只能超时重传）； 并且将ssthresh的值设置为当前cwnd的一半，而cwnd减为1，重回slow start阶段。

三、Reno

参考链接：Reno、NewReno、SACK
TCP Reno加入了快重传、快恢复算法。Reno的学习可以参考哈工大计算机网络中的拥塞控制一节。

1. 快恢复：

①当发送方连续收到三个重复确认时，就执行“乘法减小”算法，把ssthresh门限减半。但是接下去并不执行慢开始算法。
②考虑到如果网络出现拥塞的话就不会收到好几个重复的确认，所以发送方现在认为网络可能没有出现拥塞。所以此时不执行慢开始算法，而是将cwnd设置为ssthresh的大小，然后执行拥塞避免算法。

而超时时仍然与Tahoe算法相同，将拥塞窗口设置为1MSS。

2. 缺点

1. 假设发送方的拥塞窗口大小为6。发送方在发送完包号为11-16的包后。收到了三个包12的确认ACK。于是发送方进入了快速恢复阶段，将拥塞窗口降为3。并且，发送方将13重传。但是并不将14、15、16也重传。
2. 发送方收到了13的确认ACK，于是发送方退出快速恢复阶段，进入拥塞避免阶段，拥塞窗口加1，变成4。并等待14的确认ACK。
3. 但是由于没有将14重传，因此，发送方无法等到14的确认ACK。则发送方等待超时，重新发送14，并进入慢启动阶段（ss阶段）。15、16包同理。由此可见降低了发送速率。

发送方收到三个冗余ACK后，将该段重发（而不是这之后的所有段），然后进入快速恢复阶段。发送方一旦收到一个新的ACK就从快速恢复状态退出，进入冲突避免状态。这就会导致发送速率降低。

四、NewReno

参考链接：NewReno、SACK

NewReno对Reno的这个缺点进行了改进。

1. Reno TCP的基础上对快速恢复算法进行修改

只有一个数据包丢失时：其机制和Reno是一样的

当同时有多个包丢失时：Reno快速恢复算法中发送方收到一个新的ACK就退出快速恢复状态，而New Reno算法中只有当所有报文都被应答后才退出快速恢复状态

改进的快速恢复算法具体步骤：

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

序号一和序号二中，拥塞窗口的变化是，基于数据包守恒的原则。即同一时刻能在网络中传输的数据包是恒定的，只有当旧数据包离开网络后，才能发送新数据包进入网络。也可以理解为是一个对于Reno的补充，降低拥塞窗口的变化。

一个重复ACK不仅意味着有一个包丢失了，还表示有发送的数据包离开了网络，已经在接收区的缓冲区中，不再占用网络资源，于是将拥塞窗口加一个数据包大小。

2. 添加了恢复应答判断功能

使TCP终端可以把一次拥塞丢失多个报文的情形与多次拥塞的情形区分开来，进而在每一次拥塞发生后拥塞窗口仅减半一次，从而提高了TCP的顽健性和吞吐量。

注意区分确认应答（恢复应答RSACK）（最大报文应答）和部分应答（PACK）。

五、SACK

SACK针对NewReno算法的一些问题进行了改进。
New Reno算法美国RTT只能恢复一个丢失段，虽然相比于Reno他能够恢复，但是恢复的效率慢。


为了实现告诉发送方乱序到底的段，SACK在选项中加入了多个TCP options。每个TCP option表示一个乱序到达的区间，长度为10。共标注了乱序到达的左边界和右边界加一。

发送方收到后，会维持一个计分板（scoreBoard），标注这些乱序到达的段，并重发没有到达的段。
除此之外，发送方会维护一个pipe，来动态维护管道中的outstanding的数量平衡，即与拥塞窗口的大小相等。

发送方考虑以下五种情况：

1. 收到冗余ACK且无SACK选项
2. 收到冗余ACK且有SACK选项
3. 收到PACK且无SACK选项：处于拥塞避免阶段，新段被确认，说明该段和该段被重传的段，都从管道中走出，所以pipe-2
4. 收到PACK且有SACK选项
5. 收到RACK

以下是SACK基本原理：

缺点：部署SACK的代价。

六、Vegas

参考链接：
TCP协议拥塞控制算法（Reno、HSTCP、BIC、Vegas、Westwood）
vegas教学视频

Vegas是基于延时反馈的TCP协议。经典的Vegas算法的基本思路：RTT增加，拥塞窗口减小；RTT减少，拥塞窗口变大。

传统的拥塞控制算法问题：

1. 由于拥塞控制的表现是波浪性的，注入数据的跳跃性比较大，所以带宽利用率不高。他们通过一些现象来感知拥塞——三个重复ACK或者超时。
2. 段连续丢失，往往会反复降低拥塞窗口

所以我们考虑使用延迟的变化来探测网络拥塞。
RENO算法使用平均往返延迟加上四倍的标准差作为其超时时间，Vegas以细颗粒度地来计算往返延迟。

Reno、NewReno、Tacho、SACK算法

• 都是仅仅依靠丢失超时、三个冗余ACK来判断是否拥塞。
• 所以，当开始调节时，网络已经发生了拥塞，他们对拥塞的处理并不是那么敏感。
• 而且他们拥塞窗口的降低较多，比较粗暴。

在Vegas算法中

1. 先发生冗余ACK
2. 再发生细颗粒度的超时事件
3. 再发生三个冗余ACK
4. 最后，粗颗粒度的超时事件

在Vegas算法中的变化：

1. Vegas是依赖于延迟的，所以，他会精确地测量段到段的确认回来，这段往返延迟。
2. 他基于延迟的变化，延迟比粗颗粒度的延迟更能感知网络的拥塞。
3. 温和：调节是加一减一或者调整到原来的八分之七。其波动性比较小，所以对网络带宽的利用率比较高。

1. 慢启动阶段

• 连接建立时，使用Vegas的TCP处于慢启动阶段，并记录第一个RTT——BaseRTT（往往是最小的，因为没有往网络中注入段和分组）
• 慢启动阶段：2个RTT倍增拥塞窗口，不会像Reno一样每一个RTT倍增一次拥塞窗口那么快。
  • 因为Reno算法对于网络不知道可用带宽大小，只能大尺度地倍增，才能探测到可用带宽。
  • 第一个RTT是增长期，用于增长拥塞窗口
  • 第二个RTT是测量期，用于计算期望和实际速度的差距
• 从慢启动阶段过渡到拥塞避免阶段
  • 计算期望速率和实际速率的差，再乘BaseRTT。如果这个值大于$\gamma$
  • 则窗口减少八分之一，进入拥塞避免阶段。

2. 拥塞避免阶段

在拥塞避免阶段，Vegas：

• 测量RTT
• 计算期望和实际速率（公式如图）BaseRTT一定是维护的最小RTT
  • 当 $Diff<\alpha$：化简后得：$RTT<BaseRTT$，网络速率比连接建立初要快。这个主机在拥塞路由器中对应的段的个数小于1
  • 当 $\alpha <Diff<\beta$：即源主机到目标主机之间有拥塞路由器
  • 当 $Diff<\beta$：这个主机在拥塞路由器中对应的段的个数大于3

其主要思路是主机在网络中段的个数不能太多，太多就会拥塞（降窗），太少网络利用率就不高（增窗）。

3. 重传

重传的情况有两种：

• 收到冗余ACK（不是第三个冗余确认），且段的RTT超过细颗粒度的延迟时间
  
• 重发之后的第一个数据段或者第二个数据段的确认（而且是非冗余确认），Vegas将再次检测数据发送时间间隔是否超过超时值。如果是，则重发。

重传与网络的拥塞相关联，所以：

• 我们把拥塞窗口降低八分之一
• 但是在一个RTT内，不会减少两次（而Reno算法只要收到三个重复RTT或者超时就会降窗）。连续降窗是完全没有必要的，因为降窗起作用需要时间。

4.仿真图

• vagas算法比较温和，比较礼貌，和CUBIC、Reno（比较迟钝、粗鲁）相比，抢用的带宽比较少，所以比较吃亏。
• 路径变化会引起网络延迟变化
• 所以vegas使用的场景并不多，linux也只是作为一个可选项。在一些特定的环境中使用vegas较多。