note-计算机网络-拥塞控制方法详解

0. 与其他卡片的关联

• 前置卡片：
• 后续卡片：
• 相似主题：

1. 核心观点

（核心观点下四个小标题填写核心定义摘要，要求简明扼要）格式如下

• 展开详情

Ⅰ. 概念层

Ⅱ. 应用层

Ⅲ. 实现层

IV. 原理层

2. 背景/出处

• 来源：
  • 《自顶向下》
  • https://xiaolincoding.com/ 图解系列

3. 展开说明

基本概念

• 计算机网络-拥塞控制原因和代价

  • 时延过高
  • 路由器排队延迟导致重试数据占用带宽
  • 占满整个带宽导致其他线路路由器的速率为 0

• TCP 必须使用端到端拥塞控制而不是使网络辅助的拥塞控制

• TCP 所采用的方法是让每一个发送方根据所感知到的网络拥塞程度来限制其能向连接发送流量的速率。如果一个 TCP 发送方感知从它到目的地之间的路径上没什么拥塞，则 TCP 发送方增加其发送速率; 如果发送方感知沿着该路径有拥塞，则发送方就会降低其发送速率。但是这种方法提出了三个问题。

  • 第一，#一个 TCP 发送方如何限制它向其连接发送流量的速率呢？
  • 第二，#一个 TCP 发送方如何感知从它到目的地之间的路径上存在拥塞呢？
  • 第三，#当发送方感知到端到端的拥塞时，采用何种算法来改变其发送速率呢？

为了关注拥塞控制 (与流量控制形成对比)，我们后面假设 TCP 接收缓存足够大，以至可以忽略接收窗口的限制; 因此在发送方中未被确认的数据量仅受限于 ewnd。我们还假设发送方总是有数据要发送，即在拥塞窗口中的所有报文段要被发送。

一个 TCP 发送方如何限制它向其连接发送流量的速率呢？

拥塞窗口 cwnd是发送方维护的一个的状态变量，它会根据网络的拥塞程度动态变化的。

我们在前面提到过发送窗口 swnd 和接收窗口 rwnd 是约等于的关系，那么由于加入了拥塞窗口的概念后，此时发送窗口的值是 swnd = min(cwnd, rwnd)，也就是拥塞窗口和接收窗口中的最小值。

上面的约束限制了发送方中未被确认的数据量，因此间接地限制了发送方的发送速率。为了理解这一点，我们来考虑一个丢包和发送时延均可以忽略不计的连接。因此粗略地讲，在每个往返时间 (RTT) 的起始点，上面的限制条件允许发送方向该连接发送 ewnd 个字节的数据，在该 RTT 结束时发送方接收对数据的确认报文。因此，该发送方的发送速率大概是 cwnd/RTT 字节/秒。通过调节 cwnd 的值，发送方因此能调整它向连接发送数据的速率。

一个 TCP 发送方如何感知从它到目的地之间的路径上存在拥塞呢？

我们将一个 TCP 发送方的 " 丢包事件 " 定义为: 要么出现超时，要么收到来自接收方的 3 个冗余 ACK。当出现过度的拥塞时，在沿着这条路径上的一台 (或多台) 路由器的缓存会溢出，引起一个数据报 (包含一个 TCP 报文段) 被丢弃。丢弃的数据报接着会引起发送方的丢包事件 (要么超时或收到 3 个冗余 ACK)，发送方就认为在发送方到接收方的路径上出现了拥塞的指示。

拥塞算法正常情况下窗口如何增长？

考虑了拥塞检测问题后，我们接下来考虑网络没有拥塞这种更为乐观的情况，即没有出现丢包事件的情况。在此情况下，在 TCP 的发送方将收到对于以前未确认报文段的确认。如我们将看到的那样，TCP 将这些确认的到达作为一切正常的指示，即在网络上传输的报文段正被成功地交付给目的地，并使用确认来增加窗口的长度 (及其传输速率)。注意到如果确认以相当慢的速率到达 (例如，如果该端到端路径具有高时延或包含一段低带宽链路)，则该拥塞窗口将以相当慢的速率增加。在另一方面，如果确认以高速率到达，则该拥塞窗口将会更为迅速地增大。因为 TCP 使用确认来触发 (或计时) 增大它的拥塞窗口长度，TCP 被说成是自计时 (self-clocking) 的。

如何既不造成拥塞又不浪费带宽

给定调节 ewnd 值以控制发送速率的机制，关键的问题依然存在:TCP 发送方怎样确定它应当发送的速率呢?如果众多 TCP 发送方总体上发送太快，它们能够拥塞网络，导致我们在图 3-48 中看到的拥塞崩溃。事实上，为了应对在较早 TCP 版本下观察到的因特网拥塞崩溃 [Jacobson1988]​，研发了该版本的 TCP(我们马上将学习它)。然而，如果 TCP 发送方过于谨慎，发送太慢，它们不能充分利用网络的带宽; 这就是说，TCP 发送方能够以更高的速率发送而不会使网络拥塞。那么 TCP 发送方如何确定它们的发送速率，既使得网络不会拥塞，与此同时又能充分利用所有可用的带宽?TCP 发送方是显式地协作，或存在一种分布式方法使 TCP 发送方能够仅基于本地信息设置它们的发送速率?TCP 使用下列指导性原则回答这些问题:

• 一个丢失的报文段表意味着拥塞，因此当丢失报文段时应当降低 TCP 发送方的速率
  • 回想在 3.5.4 节中的讨论，对于给定报文段，一个超时事件或四个确认 (一个初始 ACK 和其后的三个冗余 ACK) 被解释为跟随该四个 ACK 的报文段的 " 丢包事件 " 的一种隐含的指示。从拥塞控制的观点看，该问题是 TCP 发送方应当如何减小它的拥塞窗口长度，即减小其发送速率，以应对这种推测的丢包事件。
• 一个确认报文段指示该网络正在向接收方交付发送方的报文段，因此，当对先前未确认报文段的确认到达时，能够增加发送方的速率。
  • 确认的到达被认为是一切顺利的隐含指示，即报文段正从发送方成功地交付给接收方，因此该网络不拥塞。拥塞窗口长度因此能够增加。
• 带宽探测
  • 给定 ACK 指示源到目的地路径无拥塞，而丢包事件指示路径拥塞，TCP 调节其传输速率的策略是增加其速率以响应到达的 ACK，除非出现丢包事件，此时才减小传输速率。因此，为探测拥塞开始出现的速率，TCP 发送方增加它的传输速率，从该速率后退，进而再次开始探测，看看拥塞开始速率是否发生了变化。TCP 发送方的行为也许类似于要求 (并得到) 越来越多糖果的孩子，直到最后告知他/她 " 不行!"​，孩子后退一点，然后过一会儿再次开始提出请求。注意到网络中没有明确的拥塞状态信令，即 ACK 和丢包事件充当了隐式信号，并且每个 TCP 发送方根据异步于其他 TCP 发送方的本地信息而行动。

当发送方感知到端到端的拥塞时，采用何种算法来改变其发送速率呢？

• 慢启动
• 拥塞避免
• 拥塞发生
• 快速恢复

有一个叫慢启动门限 ssthresh （slow start threshold）状态变量。

• 当 cwnd < ssthresh 时，使用慢启动算法。
• 当 cwnd >= ssthresh 时，就会使用 #拥塞避免算法。
• 存在一个由超时指示的丢包事件就会 #超时重传
• 检测到三个冗余 ack 会进行 计算机网络-重传机制#快速重传，然后 #快速恢复

慢启动

TCP 发送方希望快速找到可用的带宽数量。

慢启动的算法记住一个规则就行： cwnd 以一个 mss 开始，每当传输的报文被首次确认就增加 1 个 mss。TCP 向网络发送第一个报文段，并等待一个确认，该确认到达时，TCP 将 cwnd 增加一个 mss。并发送出两个最大长度的报文段。这两个报文段被确认则发送方对每一个确认的报文段增加一个 mss，此时 cwnd 变为 4 个 mss。

慢启动算法的变化过程如下图：

可以看出慢启动算法，发包的个数是指数性的增长。

拥塞避免算法

前面说道，当拥塞窗口 cwnd 「超过」慢启动门限 ssthresh 就会进入拥塞避免算法。

一般来说 ssthresh 的大小是 65535 字节。

那么进入拥塞避免算法后，它的规则是：每当收到一个 ACK 时，cwnd 增加 1/cwnd。

接上前面的慢启动的栗子，现假定 ssthresh 为 8：

• 当 8 个 ACK 应答确认到来时，每个确认增加 1/8，8 个 ACK 确认 cwnd 一共增加 1，于是这一次能够发送 9 个 MSS 大小的数据，变成了线性增长。

拥塞避免算法的变化过程如下图：

所以，我们可以发现，拥塞避免算法就是将原本慢启动算法的指数增长变成了线性增长，还是增长阶段，但是增长速度缓慢了一些。

就这么一直增长着后，网络就会慢慢进入了拥塞的状况了，于是就会出现丢包现象，这时就需要对丢失的数据包进行重传。

当触发了重传机制，也就进入了「拥塞发生算法」。

拥塞发生

当网络出现拥塞，也就是会发生数据包重传，重传机制主要有两种：

• 超时重传
• 快速重传

这两种使用的拥塞发送算法是不同的，接下来分别来说说。

超时重传

当发生了「超时重传」，则就会使用拥塞发生算法。

这个时候，ssthresh 和 cwnd 的值会发生变化：

• ssthresh 设为 cwnd/2，
• cwnd 重置为 1 （是恢复为 cwnd 初始化值，我这里假定 cwnd 初始化值 1）

怎么查看系统的 cwnd 初始化值？

Linux 针对每一个 TCP 连接的 cwnd 初始化值是 10，也就是 10 个 MSS，我们可以用 ss -nli 命令查看每一个 TCP 连接的 cwnd 初始化值，如下图

拥塞发生算法的变化如下图：

接着，就重新开始慢启动，慢启动是会突然减少数据流的。这真是一旦「超时重传」，马上回到解放前。但是这种方式太激进了，反应也很强烈，会造成网络卡顿。

就好像本来在秋名山高速漂移着，突然来个紧急刹车，轮胎受得了吗。。。

发生快速重传的拥塞发生算法

还有更好的方式，前面我们讲过「快速重传算法」。当接收方发现丢了一个中间包的时候，发送三次前一个包的 ACK，于是发送端就会快速地重传，不必等待超时再重传。

TCP 认为这种情况不严重，因为大部分没丢，只丢了一小部分，则 ssthresh 和 cwnd 变化如下：

• cwnd = cwnd/2 ，也就是设置为原来的一半;
• ssthresh = cwnd;
• 进入快速恢复算法

快速恢复

快速重传和快速恢复算法一般同时使用，快速恢复算法是认为，你还能收到 3 个重复 ACK 说明网络也不那么糟糕，所以没有必要像 RTO 超时那么强烈。

正如前面所说，进入快速恢复之前，cwnd 和 ssthresh 已被更新了：

• cwnd = cwnd/2 ，也就是设置为原来的一半;
• ssthresh = cwnd;

然后，进入快速恢复算法如下：

• 拥塞窗口 cwnd = ssthresh + 3 （ 3 的意思是确认有 3 个数据包被收到了）；
• 重传丢失的数据包；
• 如果再收到重复的 ACK，那么 cwnd 增加 1；
• 如果收到新数据的 ACK 后，把 cwnd 设置为第一步中的 ssthresh 的值，原因是该 ACK 确认了新的数据，说明从 duplicated ACK 时的数据都已收到，该恢复过程已经结束，可以回到恢复之前的状态了，也即再次进入拥塞避免状态；

这 3 条重复 ACK 传递一个关键信息：

快速恢复的核心思想

有 3 个数据包（P3、P4、P5）已经成功到达对端，不再占用链路资源，链路空出 3 个 MSS 的空位。

设计逻辑：

1. 先把长期上限 ssthresh 砍半，控制后续最大发包上限，防止持续拥堵；

2. 当前链路已经空出 3 个位置，短期可以临时放宽窗口，补上这 3 个空位，不浪费带宽；

   所以临时窗口 = 减半后的阈值 + 3，对应已经成功送达的 3 个包腾出的带宽。

• 每一条重复 ACK，都代表又一个新数据包成功到达接收端，链路又多出一块空闲带宽。
  • 既然链路有空位，就临时增大 cwnd，允许发送方持续发新数据填满链路，避免链路闲置、带宽浪费。

重传的丢失包成功到达接收端，接收端就能一次性确认全部缺失数据，回复一个全新、更大的 ACK 号。

这个 ACK 代表：

1. 数据包缺口全部补齐，丢包问题解决；
2. 链路不再持续腾出空闲位置，不需要临时放大窗口了；

快速恢复算法

快速恢复算法的变化过程如下图：

很多人问题，快速恢复算法过程中，为什么收到新的数据后，cwnd 设置回了 ssthresh ？

我在评论区看到@muum641651 (opens new window) 回答的不错，这里贴出来给大家。

我的理解是：

1. 在快速恢复的过程中，首先 ssthresh = cwnd/2，然后 cwnd = ssthresh + 3，表示网络可能出现了阻塞，所以需要减小 cwnd 以避免，加 3 代表快速重传时已经确认接收到了 3 个重复的数据包；
2. 随后继续重传丢失的数据包，如果再收到重复的 ACK，那么 cwnd 增加 1。加 1 代表每个收到的重复的 ACK 包，都已经离开了网络。这个过程的目的是尽快将丢失的数据包发给目标。
3. 如果收到新数据的 ACK 后，把 cwnd 设置为第一步中的 ssthresh 的值，恢复过程结束。

首先，快速恢复是拥塞发生后慢启动的优化，其首要目的仍然是降低 cwnd 来减缓拥塞，所以必然会出现 cwnd 从大到小的改变。

其次，过程 2（cwnd 逐渐加 1）的存在是为了尽快将丢失的数据包发给目标，从而解决拥塞的根本问题（三次相同的 ACK 导致的快速重传），所以这一过程中 cwnd 反而是逐渐增大的。

附录

MSS 单位

ssthresh=65535 字节 这里是换算成字节给初学者直观理解

cwnd=1、2、4、8，数字代表多少个 MSS 报文，纯计数，无字节。

这是内核实际运行的标准单位，Linux TCP 内部 cwnd、ssthresh 底层都是以 MSS 为单位。

这里是换算成字节给初学者直观理解：

65535 字节是早年经典的慢启动阈值字节值，只是把 ssthresh(单位MSS) × MSS大小 换算成总字节。

举个例子：

MSS=1460，若 ssthresh=44（MSS），44×1460=64240 字节，接近 65535。

MSS

• MTU：链路层最大帧总长度（包含 IP 头 + TCP 头 + 数据），以太网默认 1500 字节

• IP 头部默认 20 字节，TCP 头部默认 20 字节，合计 40 字节

  标准以太网 MSS = 1500 - 20 (IP) - 20 (TCP) = 1460

公式：

MSS = MTU - IP首部长度 - TCP首部长度

TCP 分岔

• 计算机网络-TCP分岔

4. 应用/启发

（个人思考、引发的问题或工作/生活中的应用点）

5. 待办/进一步探索