拥塞控制

## 1 为什么要进行拥塞控制

1. 在计算机网络中的链路容量（即带宽）、交换节点中的缓存和处理机等，都是网络的资源，在某段时间，若**对网络中某一资源的需求超过了该资源所能提供的可用部分**，**网络的性能就要变坏**，这种情况就叫做**拥塞**，网络出现拥塞的条件可以写成如下表达式：

$$
   \sum 对资源的需求 \gt 可用资源
   $$
2. **若网络中有许多资源同时出现供应不足**，**网络的性能就要明显变坏**，**整个网络的吞吐量将随输入负荷的增大而下降**。
3. **网络拥塞往往是由许多因素引起的**：

1. 例如，当某个节点缓存的容量太小时，到达该节点的分组因无存储空间暂存而不得不丢弃，现在设想将该节点缓存的容量扩展到非常大，于是凡到达该节点的分组均可在节点的缓存队列中排队，不收任何限制，由于输出链路的容量和处理机的速度并未提高，因此在这队列中的绝大多数分组的排队等待时间将会大大增加，结果上层软件只好把他们进行重传（因为早就超时了），由此可见，**简单地扩大缓存的存储空间同样会造成网络资源的严重浪费**，因而**解决不了网络拥塞的问题**。
   2. 又如，处理机处理的速率太慢可能引起网络的拥塞，简单地将处理机的速率提高，可能会使上述情况缓解一些，但往往又会将瓶颈转移到其他地方，问题的实质往往是**整个系统的各个部分不匹配**，**只有所有的部分都平衡了**，**问题才会得到解决**。
4. **拥塞常常趋于恶化**，**如果一个路由器某有足够的缓存空间**，**他就会丢弃一些新到的分组**，**但当分组被丢弃时**，**发送这一分组的源点就会重传这一分组**，**甚至可能还要重传多次**，**这样会引起更多的分组流入网络和被网络中的路由器丢弃**，可见**拥塞引起的重传并不会缓解网络的拥塞**，**反而会加剧网络的拥塞**。
5. 进行拥塞控制需要付出代价，这首先需要**获得网络流量内部分布的信息**，在实施拥塞控制时，还需要**在节点之间交换信息和各种命令**，以便**选择控制的策略和实施控制**，这样就**产生了额外的开销**，拥塞控制有时需要**将一些资源**（如缓存、带宽等）**分配给个别用户**（或一些类别的用户）**单独使用**，这样就**使得网络资源不能更好地实现共享**，十分明显，**在设计拥塞控制策略时**，**必须全面衡量得失**。
6. 拥塞控制在网络中起到的作用如下图所示：

![](/media/202206/2022-06-12_144714_479318.png)

1. 上图中横坐标表示**提供的负载**（Offered Load），代表**单位时间内输入给网络的分组数目**，因此提供的负载也称为**输入负载**或**网络负载**，纵坐标是**吞吐量**（Throughput），代表**单位时间内从网络输出的分组数目**。
   2. **具有理想拥塞控制的网络**，**在吞吐量饱和之前**，**网络吞吐量应等于负载**，**故吞吐量曲线是 $ 45^\circ$ 的斜线**，**但当提供的负载超过某一限度时**，**由于网络资源受限**，**吞吐量不再增长而保持为水平线**，**即吞吐量达到饱和**，**这就表明提供的负载中有一部分损失掉了**（例如，输入到网络的某些分组被某个节点丢弃了），虽然如此，**在这种理想的拥塞控制作用下**，**网络的吞吐量依然维持在其所能达到的最大值**。
   3. 但是，实际网络的情况就很不相同了，从上图中可以看出，**随着提供的负载增大**，**网络吞吐量的增长速率逐渐减小**，也就是说，**在网络吞吐量还未达到饱和时**，**就已经有一部分的输入分组被丢弃了**，**当网络的吞吐量明显地小于理想的吞吐量时**，**网络就进入了轻度拥塞的状态**，更值得注意的是，**当提供的负载达到某一数值时**，**网络的吞吐量反而随提供的负载的增大而下降**，**这时网络就进入了拥塞状态**，**当提供的负载继续增大到某一数值时**，**网络的吞吐量就下降到零**，**网络已无法工作**，这就是所谓的**死锁**（Deadlock）。
7. 实践证明，拥塞控制是很难设计的，因为他是一个动态的问题，当前网络正朝着高速化的方向发展，这**很容易出现缓存不够大而造成分组的丢失**，但**分组的丢失是网络发生拥塞的征兆而不是原因**，在许多情况下，甚至正是**拥塞控制机制本身成为引起网络性能恶化甚至发生死锁的原因**。
8. 从大的方面来看，可以采用**开环控制**和**闭环控制**两种方法来设计拥塞控制策略：

1. **开环控制就是在设计网络时事先将有关发生拥塞的因素考虑周到**，**力求网络在工作时不产生拥塞**，**但一旦整个系统运行起来**，**就不再中途进行改正了**。
   2. **闭环控制是基于反馈环路的概念**，主要有以下几种措施：
      1. **监测网络系统以便检测到拥塞在何时**、**何处发生**：
         1. 有很多的方法可用来监测网络的拥塞，主要的一些指标是**由于缺少缓存空间而被丢弃的分组的百分数**、**平均队列长度**、**超时重传的分组数**、**平均分组时延**、**分组时延的标准差等**，**上述这些指标的上升都标志着拥塞的增长**。
      2. **把拥塞发生的信息传送到可采取行动的地方**：
         1. **一般监测到拥塞发生时**，**要将拥塞发生的信息传送到产生分组的源站**，当然，**通知拥塞发生的分组同样会使网络更加拥塞**。
         2. 另一种方法是**在路由器转发的分组中保留一个比特或字段**，**用该比特或字段的值表示网络没有拥塞或产生了拥塞**，**也可以由一些主机或路由器周期性地发出探测分组**，**以询问拥塞是否发生**。
         3. 此外，**过于频繁地采取行动以缓和网络的拥塞**，**会使系统产生不稳定的震荡**，**但过于迟缓地采取行动又不具有任何实用价值**，因此，**采取某种折中的方法**，**但选择正确的时间常数是非常困难的**。
      3. **调整网络系统的运行以解决出现的问题**。

## 2 拥塞控制方法

TCP 进行拥塞控制的算法有四种，即**慢开始**（Slow Start）、**拥塞避免**（Congestion Avoidance）、**快重传**（Fast Retransmit）和**快恢复**（Fast Recovery），为了集中精力讨论拥塞控制，我们假定：

1. **数据是单方向传送的**，**对方只传送确认报文**。
2. **接收方总是有足够大的缓存空间**，**因而发送窗口的大小由网络的拥塞程度来决定**。

### 2.1 慢开始

1. 下面讨论的拥塞控制也叫做**基于窗口的拥塞控制**，**发送方维持一个叫做拥塞窗口 $cwnd$**（Congestion Window）**的状态变量**，**拥塞窗口的大小取决于网络的拥塞程度**，**并且动态地在变化**，**发送方让自己的发送窗口等于拥塞窗口**。
2. 发送方控制拥塞窗口的原则是**只要网络没有出现拥塞**，**拥塞窗口就可以再增大一些**，**以便把更多的分组发送出去**，**这样就可以提高网络的利用率**，**但只要网络出现拥塞或有可能出现拥塞**，**就必须把拥塞窗口减小一些**，**以减少注入到网络中的分组数**，**以便缓解网络出现的拥塞**。
3. 我们知道，**当网络发生拥塞时**，**路由器就要丢弃分组**，因此**只要发送方没有按时收到应当到达的确认报文**（出现了超时），**就可以猜想网络可能出现了拥塞**。

> 现在通信线路的传输质量一般都很好，因传输出差错而丢弃分组的概率是很小的（远小于 1%），因此，判断网络拥塞的依据就是出现了超时。
   >
4. 慢开始算法的思路是这样的**当主机开始发送数据时**，**由于并不清楚网络的负荷情况**，**所以如果立即把大量数据字节注入到网络**，**那么就有可能引起网络发生拥塞**，经验证，**较好的方法是先探测一下**，即**由小到大逐渐增大发送窗口**，也就是说，**由小到大逐渐增大拥塞窗口数值**，**在刚刚开始发送报文段时**，**先把初始拥塞窗口 $cwnd$ 设置为不超过 2 至 4 个发送方的最大报文段**$SMSS$（Sender Maximum Segment Size）**的数值**，具体的规定如下：

1. 若 $SMSS \gt 2190$**字节**，则**设置初始拥塞窗口 $cwnd = 2 \times SMSS$ 字节**，且**不得超过 2 个报文段**。
   2. 若 $SMSS \gt 1095$**且 $SMSS \le 2190$ 字节**，则**设置初始拥塞窗口 $cwnd = 3 \times SMSS$ 字节**，且**不得超过 3 个报文段。**
   3. 若 $SMSS \le 1095$ **字节**，则**设置初始拥塞窗口 $cwnd = 4 \times SMSS$ 字节**，且**不得超过 4 个报文段**。
5. 慢开始规定，**在每收到一个对新的报文段的确认后**，**可以把拥塞窗口增加最多一个 $SMSS$ 的数值**，即

$$
   拥塞窗口 cwnd 每次的增加量 = min(N, SMSS)
   $$

其中 $N$**是原先未被确认的**、**但现在被刚收到的确认报文段所确认的字节数**，不难看出，**当 $N \lt SMSS$ 时**，**拥塞窗口每次的增加量要小于 $SMSS$**，**用这样的方法逐步增大发送方的拥塞窗口 $cwnd$**，**可以使分组注入到网络的速率更加合理**。
6. 具体实例如下（实际上 TCP 是用字节数作为窗口大小的单位，但为叙述方便起见，我们用**报文段的个数作为窗口大小的单位**，这样可以使用较小的数字来阐明拥塞控制的原理）：

![](/media/202206/2022-06-12_162556_540173.png)

1. 在**一开始发送方先设置 $cwnd = 1$**，**发送第一个报文段 $M_1$**，**接收方收到后确认 $M_1$**。
   2. **发送方收到对 $M_1$ 的确认后**，**把 $cwnd$ 从 1 增大到 2**，**于是发送方接着发送 $M_2$ 和 $M_3$ 两个报文段**，**接收方收到后发回对 $M_2$ 和 $M_3$ 的确认**。
   3. **发送方每收到一个对新报文段的确认**（重传的不算在内）**就使发送方的拥塞窗口加 1**，**因此发送方在收到两个确认后**，$cwnd$**就从 2 增大到 4**，**并可发送 $M_4 \sim M_7$ 共 4 个报文段**。
   4. 因此使用慢开始算法后，**每经过一个传输轮次**（Transmission Round），**拥塞窗口 $cwnd$ 就加倍**。

> **一个传输轮次所经历的时间其实就是往返时间 RTT**（RTT 并非是恒定的数值），即**把拥塞窗口 $cwnd$ 所允许发送的报文段都连续发送出去**，**并收到了对已发送的最后一个字节的确认**，例如，拥塞窗口 $cwnd$ 的大小是 4 个报文段，那么这时的往返时间 RTT 就是发送方连续发送 4 个报文段，并收到这 4 个报文段的确认，总共经历的时间。
      >

> **慢开始的“慢”并不是指 $cwnd$ 的增长速率慢**，**而是指在 TCP 开始发送报文段时先设置 $cwnd = 1$**，**使得发送方在开始时只发送一个报文段**（目的是试探一下网络的拥塞情况），**然后再逐渐增大 $cwnd$**，**这当然比设置大的 $cwnd$ 值一下子把许多报文段注入到网络中要慢得多**，**这对防止网络出现拥塞是一个非常好的方法**。
      >

> 上图只是为了说明慢开始的原理，在 TCP 的实际运行中，**发送方只要收到一个对新报文段的确认**，**其拥塞窗口 $cwnd$ 就立即加 1**，**并可以立即发送新的报文段**，**而不需要等这个轮次中所有的确认都收到后再发送新的报文段**。
      >
   5. 为了**防止拥塞窗口 $cwnd$ 增长过大引起网络拥塞**，还**需要设置一个慢开始门限 $ssthresh$ 状态变量**，其用法如下：

1. **当 $cwnd \lt ssthresh$ 时**，**使用上述的慢开始算法**。
      2. **当 $cwnd \gt ssthresh$ 时**，**停止使用慢开始算法而改用拥塞避免算法**。
      3. **当 $cwnd = ssthresh$ 时**，**既可使用慢开始算法**，**也可使用拥塞避免算法**。

### 2.2 拥塞避免

1. 拥塞避免的思路是**让拥塞窗口 $cwnd$ 缓慢地增大**，**即每经过一个往返时间 RTT 就把发送方的拥塞窗口 $cwnd$ 加 1**，**而不是像慢开始阶段那样加倍增长**，因此在拥塞避免阶段就有**加法增大**（Additive Increase）**的特点**，这表明在拥塞避免阶段，拥塞窗口 $cwnd$**按线性规律缓慢增长**，**比慢开始算法的拥塞窗口增长速率缓慢得多**。
2. 具体实例如下（**假定 TCP 的发送窗口等于拥塞窗口**，为了便于理解，下图中的窗口单位不使用字节而使用报文段的个数）：

![](/media/202206/2022-06-12_203554_934004.png)

1. **当 TCP 连接进行初始化时**，**把拥塞窗口 $cwnd$ 置为 1**，**慢开始门限的初始值设置为 16 个报文段**，即 $ssthresh = 16$。
   2. **在执行慢开始算法时**，**发送方每收到一个对新报文段的确认 ACK**，**就把拥塞窗口值加 1**，**然后开始下一轮的传输**（上图中的横坐标是传输轮次，而不是时间），**因此拥塞窗口 $cwnd$ 随着传输轮次按指数规律增长**。
   3. **当拥塞窗口 $cwnd$ 增长到慢开始门限值 $ssthresh$ 时**（图中的点 ①，此时拥塞窗口 $cwnd = 16$），**就改为执行拥塞避免算法**，**拥塞窗口按线性规律增长**。

> **「拥塞避免」并非完全能够避免了拥塞**，**而是说把拥塞控制窗口控制为按线性规律增长**，**使网络比较不容易出现拥塞**。
      >
   4. **当拥塞窗口 $cwnd = 24$ 时**，**网络出现了超时**（图中的点 ②），**发送方判断为网络拥塞**，**于是调整慢开始门限值 $ssthresh = \frac{cwnd}2 = 12$**，**同时设置拥塞窗口 $cwnd = 1$**，**进入慢开始阶段**。
   5. **按照慢开始算法**，**发送方每收到一个对新报文段的确认 ACK**，**就把拥塞窗口值加 1**，**当拥塞窗口 $cwnd = ssthresh = 12$ 时**（图中的点 ③，这是新的 $ssthresh$ 值），**改为进行拥塞避免算法**，**拥塞窗口按线性规律增大**。
   6. **当拥塞窗口 $cwnd = 16$ 时**（图中的点 ④），**出现了一个新的情况**，**就是发送方一连收到 3 个对同一报文段的重复确认**（图中记为 3-ACK），这是因为**有时个别报文段会在网络中丢失**，**但实际上网络并未发生拥塞**，**如果发送方迟迟收不到确认**，**就会产生超时**，**就会误认为网络发生了拥塞**，**这就导致发送方错误地启动慢开始**，**把拥塞窗口 $cwnd$ 又设置为 1**，**因而降低了传输效率**。

### 2.3 [快重传](https://notebook.ricear.com/project-26/doc-306/#2-2-2-%E5%BF%AB%E9%80%9F%E9%87%8D%E4%BC%A0)

1. **采用快重传算法可以让发送方尽早知道发生了个别报文段的丢失**，快重传算法首先要求**接收方不要等待自己发送数据时才进行捎带确认**，而是要**立即发送确认**，**即使收到了失序的报文段也要立即发出对已收到的报文段的重复确认**。
2. 具体实例如下：

![](/media/202206/2022-06-12_213006_093558.png)

1. 接收方收到了 $M_1$ 和 $M_2$ 后都分别及时发出了确认，先假定接收方没有收到 $M_3$ 但却收到了 $M_4$，本来接收方可以什么都不做，但按照快重传算法，**接收方必须立即发送对 $M_2$ 的重复确认**，**以便让发送方及早知道接收方没有收到报文段 $M_3$**。
   2. 发送方接着发送 $M_5$ 和 $M_6$，接收方收到后也仍要再次分别发出对 $M_2$ 的重复确认，这样，发送方共收到了接收方的 4 个对 $M_2$ 的确认，其中后 3 个都是重复确认。
   3. 快重传算法规定**发送方只要一连收到 3 个重复确认**，**就知道接收方确实没有收到报文段 $M_3$**，**因而应当立即进行重传**（即「快重传」），**这样就不会出现超时**，**发送方也就不会误认为出现了网络拥塞**，**使用快重传可以使整个网络的吞吐量提高约 20%**。

### 2.4 快恢复

1. 在[2.2 拥塞避免](#2-2-拥塞避免)实例的图中我们可以看到在点 ④，**发送方知道现在只是丢失了个别的报文段**，于是**不启动慢开始**，而是**执行快恢复算法**，这时，**发送方调整门限值 $ssthresh = \frac{cwnd}2 = 8$**，同时**设置拥塞窗口 $cwnd = ssthresh = 8$**（见[2.2 拥塞避免](#2-2-拥塞避免)实例的图中的点 ⑤），**并开始执行拥塞避免算法**。

> [2.2 拥塞避免](#2-2-拥塞避免)实例的图中标注的「TCP Reno 版本」，表示区别于老的「TCP Tahao 版本」。
   >

> 有的快恢复实现是**把快恢复开始时的拥塞窗口 $cwnd$ 值再增大一些**（增大 3 个报文段长度），即**等于新的 $ssthresh + 3 \times MSS$**，这样做的理由是**既然发送方收到 3 个重复的确认**，**就表明有 3 个分组已经离开了网络**，**这 3 个分组不再消耗网络的资源而是停留在接收方的缓存中**（接收方发出 3 个重复的确认就证明了这个事实），可见**现在网络中并不是堆积了分组而是减少了 3 个分组**，因此**可以适当把拥塞窗口扩大些**。
   >

### 2.5 总结

1. 从[2.2 拥塞避免](#2-2-拥塞避免)实例的图中可以看出**在拥塞避免阶段**，**拥塞窗口是按照线性规律增大的**，这常称为**加法增大 AI**（Additive Increase），而**一旦出现超时或 3 个重复的确认**，**就要把门限值设置为当前拥塞窗口值的一半**，**并大大减小拥塞窗口的数值**，这常称为**乘法减小 MD**（Multiplicative Decrease），二者合在一起就是所谓的 AIMD 算法，**采用这样的拥塞控制方法使得 TCP 的性能有明显的改进**。
2. 综上所述，TCP 的拥塞控制可以归纳为如下图所示的流程图：

> 这个流程图比[2.2 拥塞避免](#2-2-拥塞避免)实例的图中所示的特例要更加全面些，例如，在[2.2 拥塞避免](#2-2-拥塞避免)实例的图中没有说明在慢开始阶段如果出现了超时（即出现了网络拥塞）或出现 3-ACK，发送方应采取什么措施，但从下面的流程图中我们就可以很明确地知道发送方应采取的措施。
   >

![](/media/202206/2022-06-13_152459_966877.png)
3. 本文中我们假定**接收方总是有足够大的缓存空间**，因而**发送窗口的大小由网络的拥塞程度来决定**，但实际上**接收方的缓存空间总是有限的**，**接收方根据自己的接收能力设定了接收方窗口 $rwnd$**，**并把这个窗口值写入 TCP 首部中的窗口字段**，**传送给发送方**，因此，**接收方窗口又称为通知窗口**（Advertised Window）。
4. **从接收方对发送方的**[流量控制](https://notebook.ricear.com/project-26/doc-303)**的角度考虑**，**发送方的发送窗口一定不能超过对方给出的接收方窗口值 $rwnd$**，**如果把拥塞控制和接收方对发送方的[流量控制](https://notebook.ricear.com/project-26/doc-303)一起考虑**，那么**发送方的窗口上限值应当取为接收方窗口 $rwnd$ 和拥塞窗口 $cwnd$ 这两个变量中较小的一个**，也就是说：

$$
   发送方窗口的上限值 = Min(rwnd, cwnd)
   $$

即：

1. 当 $rwnd \lt cwnd$ 时，是**接收方的接收能力限制发送方窗口的最大值**。
   2. 当 $rwnd \gt cwnd$ 时，是**网络的拥塞程度限制发送方窗口的最大值**。

## 3 主动队列管理 AQM

### 3.1 为什么要进行主动队列管理

1. 上面讨论的 TCP 拥塞控制并没有和网络层采取的策略联系起来，其实，他们之间有着密切的关系。
2. 例如，假定一个路由器对某些分组的处理时间特别长，那么这就可能使这些分组中的数据部分（即 TCP 报文段）经过很长时间才能到达终点，结果引起发送方对这些报文段的重传，重传会使 TCP 连接的发送端认为在网络中发生了拥塞，于是在 TCP 的发送端就采取了拥塞控制措施，但实际上网络并没有发生拥塞。
3. 网络层的策略对 TCP 拥塞控制影响最大的就是路由器的**分组丢弃策略**，在最简单的情况下，路由器的队列通常都是按照**先进先出**（First In First Out）的规则处理到来的分组，由于**队列长度总是有限的**，因此**当队列已满时**，**以后再到达的所有分组**（如果能够继续排队，这些分组都将排在队列的尾部）**将都被丢弃**，这就叫做**尾部丢弃策略**（Tail Drop Policy）。
4. **路由器的尾部丢弃往往会导致一连串分组的丢失**，**这就使发送方出现超时重传**，**使 TCP 进入拥塞控制的慢开始状态**，**结果使 TCP 连接的发送方突然把数据的发送速率降低到很小的数值**，**更为严重的是**，**在网络中通常有很多的 TCP 连接**（他们有不同的源点和终点），**这些连接中的报文段通常是复用在网络层的 IP 数据报中传送**，**在这种情况下**，**若发生了路由器中的尾部丢弃**，**就可能会同时影响到很多条 TCP 连接**，**结果使这许多 TCP 连接在同一时间突然都进入到慢开始状态**，**这在 TCP 的术语中称为****全局同步**（Global Syncronization），**全局同步使得全网的通信量突然下降了很多**，**而在网络恢复正常后**，**其通信量又突然增大很多**。

### 3.2 主动队列管理原理

1. 为了**避免发生网络中的全局同步现象**，在1998年**提出了主动队列管理**（Active Queue Management, AQM），所谓「主动」就是**不要等到路由器的队列长度已经达到最大值时才不得不丢弃后面到达的分组**，这样就太被动了，**应当在队列长度达到某个值得警惕的数值时**（即**当网络拥塞有了某些拥塞征兆时**），**就主动丢弃到达的分组**，这样就**提醒了发送方放慢发送的速率**，因而**有可能使网络拥塞的程度减轻**，**甚至不出现网络拥塞**。
2. AQM可以有不同实现方法，其中曾流形多年的就是**随机早期监测**（Random Early Detection, RED）：
   1. 实现RED时**需要使路由器维持两个参数**，即**队列长度最小门限**和**最大门限**，**当每一个分组到达时**，**RED就按照规定的算法先计算当前的平均队列长度**：
      1. **若平均队列长度小于最小门限**，**则把新到达的分组放入队列进行排队**。
      2. **若平均队列长度超过最大门限**，**则把新到达的分组丢弃**。
      3. **若平均队列长度在最小门限和最大门限之间**，**则按照某一丢弃概率$p$把新到达的分组丢弃**（这就体现了丢弃分组的随机性）。
   2. 由此可见，RED**不是等到已经发生网络拥塞后才把所有在队列尾部的分组全部丢弃**，**而是在检测到网络拥塞的早期征兆时**（即**路由器的平均队列长度达到一定数值时**），**就以概率$p$丢弃个别的分组**，**让拥塞控制只在个别的TCP连接上进行**，因而**避免发生全局性的拥塞控制**。
   3. 在RED的操作中，**最难处理的就是丢弃概率$p$的选择**，因为$p$**不是个常数**，**对每一个到达的分组**，**都必须计算丢弃概率$p$的值**，但多年的实践证明，**RED的使用效果并不太理想**，**目前已经不再推荐使用**。
3. **对路由器进行主动队列管理是必要的**，**其实际上就是对路由器中的分组排队进行智能管理**，**而不是简单地把队列的尾部丢弃**，**现在已经有几种不同的算法来代替旧的RED**，**但都还在实验阶段**，**目前还没有一种算法能够成为IETF的标准**。

## 参考文献

1. 《计算机网络-第 7 版-谢希仁》