前言

上一节介绍了 TCP 的滑动窗口机制，它在接收端和发送端都存在，接收端根据自己的接收能力计算出一个接收窗口，通常叫通告窗口，然后通知给发送端。发送端会参考通告窗口计算出本地的发送窗口，每次发送的流量不能超过发送窗口的大小，这是 TCP 的流控机制。流控只是保证两个 TCP 通信端点之间数据传输的可靠。

而实际上，TCP 报文段到了网络层会封装成 IP 分组，经过 IP 网络传输才能到达对端。IP 网是分组交换网，每一个 IP 分组需要经过路由器逐跳转发，最终到达目的主机。当主机的发送流量超过了网络负载或者路由器的容量就会出现延迟、丢包现象，导致通信服务质量的下降，这就是大家经常提到的网络拥塞。

本文主要介绍 TCP 应对网络拥塞的各种算法，包含如下几个内容：

• 道路拥塞
• 网络拥塞的概念
• TCP 拥塞窗口
• Tahoe 算法
• Reno 算法
• NewReno 算法
• SACK 算法
• FACK 算法
• ECN 机制

由于网络拥塞摸不着、看不见，需要网络技术人员通过专业技术手段来判断，这对初学者来说，理解起来有点抽象。那我们首先探讨一下日常生活中的道路拥堵问题。

道路拥塞

我想你非常熟悉城市道路拥塞的现象吧，每天上下班城市道路拥堵不堪，每当节假日高速公路也是经常拥堵。城市道路容易产生拥塞的地方有：从快速干道进入辅道的交接处，从车道较多的道路进入车道较少的道路。这些都是因为道路变窄，不能承载较大的车流量导致的。高速公路容易产生拥塞的地方就是收费站的出入口，一条跨省的高速公路都会设立省界收费站，在节假日、旅游旺季经常造成拥堵，高速公路的拥堵往往是因为要排队出站结算、检查，排队进站拿卡导致的。

总结一下，道路拥塞主要表现在两方面：

1. 在不同级别的道路连接处，由快速道路进入慢速道路导致的，快速道路宽、路况好，慢速道路窄、路况不好，由于无法承载增加的车流量的；
2. 在高速公路收费站，由于要排队进站、排队出站导致拥堵。

以上两种情况，都是由于车流量大导致的拥塞，一旦出现拥堵后，如果车流量继续增加，拥堵会更糟糕。如何来解决道路拥堵的问题呢？目前看到的办法有（由于本人不是交通运输专业人员，只谈我们实际看到的解决办法）：

• 由专业人员指挥疏导、避免乱插队导致更大的拥堵；
• 道路改造，拓宽路面；
• 建设城市快速干道；
• 目前国家在取消省界收费站，可以解决省界收费站导致的拥堵。

如果用道路拥塞类比网络拥塞，道路类似网络线路；从城市道路进入高速公路的连接点类似本地网络进入广域网的连接点；高速公路上的收费站类似 IP 网络中路由器，你也可以把省界收费站比作 IP 网络中不同运营商之间的边界网关；机动车类似 IP 网络中的分组。下来我们具体分析一下 IP 网络拥塞。

网络拥塞的概念

我们再回忆一下第一篇中介绍的网络拓扑结构：

在光纤接入时代，家庭网络由家用路由器连接，通过 ONU 接入到运营商的 OLT，运营商的 OLT 继续连接到汇聚层路由器然后再接入骨干网。对于企业网来说，一般是直接从运营商拉一根光纤到企业机房，然后由企业网路由器连接企业内部的各个部门。

在 IP 网络中，每一个 IP 分组需要经过路由器逐跳转发，才能到达目的主机。路由器是存储转发设备，IP 分组从输入端口进入输入队列，经过路由器的交换，转发到输出端口的输出队列。当主机的发送流量超过了路由器的转发能力，IP 分组就会在路由器的输入端口队列中排队，长时间排队会导致延迟，如果排队的 IP 分组超过路由器的输入队列的长度，路由器就会丢弃该分组，导致丢包现象出现，最终结果就是通信服务质量的下降，我们把此现象叫做网络拥塞。

网络拥塞主要体现在两方面：

• 在有线网络（wired networks）中, 可能存在交换能力较差的路由器形成瓶颈。比如，从本地网络到广域网连接处；在不同的运营商的边界处；在国内线路到国际线路的出口处，如下图所示：

• 在无线网络（wireless networks）中，由于无线信号会受到天气、障碍物等环境因素的影响，会造成数据包错误，从而导致丢包。

当道路出现拥塞，你不可能把某一辆汽车丢弃掉，你也没法丢弃掉，只能是排队有序的通过，当然也有人会掉头绕道，因为经常看到车辆在逆行。

当网络出现拥塞，路由器会毫不客气地丢弃一部分分组。如何解决网络拥塞的问题呢？对于 IP 网络来说，有两方面可以考虑：

• 一方面是提升网络带宽，改善网络基础设施，这需要不断地研究新技术，比如现在吵的很热的 5G 技术，这依赖社会、科技的进步；
• 另一方面是在现有网络基础设施之上改善网络拥塞。也许你很容易想到，通过重传来解决分组丢失的问题，我们知道 TCP 就采用了超时重传机制。然而，如果是大量地重传丢失的分组，可能会造成拥塞更严重，出现拥塞崩塌（congestive collapse）。

所以，解决网络拥塞导致的问题，不仅要依靠重传，而且要进行拥塞控制，要尽量避免拥塞的发生，这也是本文重点要讨论的内容。

TCP 拥塞窗口

在 IP 网络中，当路由器发生拥塞或者丢弃了分组，并不会主动通知 TCP 的发送端，这就要求 TCP 必须有一种自学习能力，发送的数据不能超过网络的容量，这个容量经常用带宽时延积（BDP，Bandwidth Delay Product）来表示。在上一节，我们介绍过 TCP 可以估算出 RTT，如果再能估算出当前网络的带宽（Bandwidth），那么通过计算 Bandwidth * RTT 就能得到 BDP。

网络带宽是一个线路特性，是你向运营商购买宽带的时候设置好的，比如 50Mbps 或 100Mbmps，那为什么还要估算呢？因为在分组交换网中，网络并不是独占的，而是多台主机共享的，比如你的手机和笔记本共享 100Mbps 的家庭网络。就算在同一台主机，多个 TCP 连接也是共享同一个网络。再说，TCP 连接也不是独占一条物理链路的，只是一个逻辑连接，每一个 TCP 报文段，都要经过网络层封装成 IP 分组，每个 IP 分组都需要经过路由器的选路和存储转发，是一个动态选路的过程。这样，当某一个 TCP 连接发送了大量的数据包，会导致另外一个 TCP 连接的发送能力受到影响。

比如，你用笔记本下载电影，同时通过 IM 和朋友进行 VOIP 通信，可能你的语音质量会时好时坏，因为电影下载软件抢走了你的带宽。这就说明，对于某个 TCP 连接来说，当前可用的网络带宽是动态变化的，自己必须要实时的估算。

当 TCP 发现有丢包现象出现，就认为当前的网络带宽达到上限，网络出现了拥塞，所以必须降低发送流量。TCP 判断网络出现丢包的依据如下：

• 超时重传定时器到期；
• TCP 收到了重复 ACK；
• 通过 SACK 机制判断网络出现丢包。

TCP 的流控机制是 TCP 发送端发送的数据不能超过通告窗口，记作 awnd。为了避免网络拥塞，TCP 又引入了拥塞窗口（Congestion Window）的概念，记作 cwnd。那么，TCP 发送窗口要取 awnd 和 cwnd 的最小值，即 swnd = min(awnd, cwnd)，swnd 表示 TCP 的发送窗口。随着网络状况的不断变化，cwnd 也要实时的变化，当网络出现拥塞以后，cwnd 要减小；当网络恢复以后，cwnd 要增加，保证传输性能。调节 cwnd 并不是一件容易的事情，在不同的应用场景下，调节算法也有差异。为此，TCP 开发了一系列拥塞控制算法，不断地改善算法的性能，以便适应越来越多的应用场景。

下来，我们就共同探讨一下 TCP 常用的拥塞控制算法。

Tahoe 算法

在所有讨论 TCP 拥塞控制的文章中，都会提及 Tahoe 算法，那么 Tahoe 这个名字有一定来头吗？现在让我们一起回忆一下第一篇专栏《01 追本溯源：探寻协议栈的发展历程》，在 Socket 发展史一节中曾经介绍过：TCP/IP 协议栈是在 BSD 4.2 发布，并且在 BSD 4.3 Tahoe 版本中发布了 TCP 的拥塞控制和拥塞避免特性，人们用 BSD 的发行名称 Tahoe 来命名版本中发布的拥塞控制算法，这就是 Tahoe 的由来。

Tahoe 算法主要包含两部分，慢启动（Slow Start）和拥塞避免（Congestion avoidance），这两个算法需要配合使用。

慢启动（Slow start）

当 TCP 连接新建立时，TCP 并不知道当前网络的容量。要想快速的探测当前网络容量，TCP 可以尽自己最大能力发送数据包，直到出现丢包为止。这种策略是可以快速探测到网络容量，但也会造成网络拥塞，从拥塞到恢复又需要一个过程，此方法过于激进，不可取。

因此 TCP 并没有采用这么激进的策略，而是采取慢启动策略。在连接建立初期，给 cwnd 设置一个较小的窗口，叫做 IW（initial window）, RFC 5681 中定义的取值如下：

IW = 2*(SMSS) and not more than 2 segments (if SMSS>2190 bytes)
IW = 3*(SMSS) and not more than 3 segments (if 2190>=SMSS>1095 bytes)
IW = 4*(SMSS) and not more than 4 segments (otherwise)

SMSS（SENDER MAXIMUM SEGMENT SIZE）的取值可以是三次握手过程中，双方通过 MSS 选项协商的值，也可以是路径 MTU，取二者的最小值。每当 TCP 发送端收到一个 Good ACK，就根据如下规则增加 cwnd 窗口：

cwnd += min(N, SMSS)

每收到一个 Good ACK，就会 ACK 一部分 TCP 发送窗口中处于 sent unack 状态的数据，N 表示被 ACK 掉的数据字节长度。Good ACK 是指 TCP Header 中的 ACK Sequence 有新的变化，会促使 TCP 发送窗口的 SND.UNA 指针向右移动。

假如 cwnd 初始值是 1 个 SMSS，简写为 1，并且 awnd 窗口也很大。那么，收到第一个 Good ACK 后，cwnd 变成 2，可以发送两个报文段；第二轮收到两个 Good ACK 后，cwnd 变成 4，可以发送四个报文段；如果不丢包，理想情况下 cwnd 取值会变成 8，16，…，第k轮发送后，cwnd = 2^k, cwnd 是指数单调递增的。为此，慢启动只是 IW 小，但是 cwd 增长速度是非常快的。具体过程如下图所示：

拥塞避免（Congestion avoidance）

慢启动算法的 cwnd 是指数增长，如果 awnd 无限大，那么 cwnd 会越来越大，很快就会造成网络拥塞。为此，TCP 引入了拥塞避免机制。通过慢启动门限（ssthresh，slow start threshhold）来控制：

• 如果 cwnd < ssthresh ，执行慢启动算法；
• 如果 cwnd > ssthresh ，执行拥塞避免算法。

拥塞避免阶段，cwnd 是近似线性增长的，cwnd 增长的算法如下：

cwnd(t+1) = cwnd(t) +SMSS*SMSS/cwnd(t)

在 TCP 连接新建立初期，ssthresh 的初始值一般设为 awnd 或者更大。当出现了超时重传或快速重传，将 cwnd 设置为 1 * SMSS，将 ssthresh 更新为 cwnd/2，TCP 重新进入慢启动阶段。

RFC5681 更新 ssthresh 的方法如下：

ssthresh = max(flight size/2, 2*SMSS)

其中 flight size 表示 TCP 发送窗口中已发送未确认的数据，基本代表了当前 cwnd 的大小。ssthresh 取值至少是 2 个 SMSS 的大小。

在 Tahoe 算法中，TCP 进入慢启动阶段有两种情况：

• 一是新连接刚建立初期；
• 二是出现了超时重传或快速重传，即 TCP 认为发生了丢包。

Tahoe 算法的拥塞避免策略也是比较粗暴的，比如有些真实的网络环境就是有固定丢包，而并没有发生拥塞。对于这种情况来说，并不需要进入慢启动，而是执行完快速重传，继续保持之前的 swnd 发送即可。

为此，Reno 算法对超时重传和快速重传导致的丢包，分成两种情况处理。

Reno 算法

Reno 算法是在 Tahoe 算法基础之上，对 TCP 拥塞控制机制进行了改善，并且随 BSD 4.3 Reno 版本发布。

Reno 算法将超时重传和快速重传导致的丢包分开处理，如下：

• 如果 TCP 的发送端出现了超时重传，将 cwnd 设置为 1 * SMSS，将 ssthresh 设置成新的 cwnd/2，重新进入慢启动阶段；
• 如果 TCP 的发送端收到 3 个重复 ACK，进行快速重传，将丢弃的数据包重传给对方；
• 如果 TCP 的发送端收到大于 3 个重复 ACK，比如 4 个重复 ACK，说明接收端收到了新的报文段，只是丢失的报文段还没有收到，说明网络中有多余的容量空出，可以继续向网络发送数据。由于丢失的报文段已经重发完成，所以进入快速恢复（fast recovery）阶段。

在 快速恢复（fast recovery）阶段，做如下处理：

1. 将 ssthresh 设置成新的 cwnd/2，将 cwnd 设置成 ssthresh + 3*SMSS；
2. 发送一个待发送的报文段；
3. 每收到一个重复 ACK，cwnd 增加一个 SMSS，继续执行第 2 步。如果收到一个 Good ACK，则结束快速恢复，将 cwnd 设置成 ssthresh，进入拥塞避免阶段。

Tahoe 和 Reno 算法执行过程如下图所示：

图中用 5 个红色数字标出了 5 个点，从 1 ~ 2 是慢启动过程；从 2 ~ 3 是拥塞避免阶段；从 3 ~ 4 是 Reno 算法的快速重传；从 3 ~ 5 是 Tahoe 算法的快速重传；4 以后是 Reno 算法的快速恢复、拥塞避免过程；5 以后是 Tahoe 算法的慢启动、拥塞避免过程。

现在我们借助上一节学过的 TCP 滑动窗口，分析一下 Reno 算法的执行过程。下图展示了 TCP 通信中可能的一种状态。

假设 SMSS = 1460；假设此时发送端的 swnd 就是 cwnd，那么 cwnd = 8*SMSS；假设此时的 ssthresh 还是初始值，比如是 65535。

现在我们分析下 Reno 算法的执行过程：
接收端收到 9 号包以后，发现丢失了 6、7、8 三个包，立即向发送端发送 ACK=6，len=0 的响应。

发送端收到此 ACK 以后，SND.UNA 会向右移动两个位置，cwnd = 81460 + 14601460/8*1460，cwnd=(8 + 1/8)*1460。假设 10、11 号包大小都是 1460，而 12 号包是 180 字节，则 SND.NXT 向右移动三个位置，可以继续发送第 10、11、12 号包。

接收端收到 10、11、12 号包后，发现 6、7、8 三个包还在丢，连续发了三个 ACK=6，len=0 的响应。

此时的发送端已经收到了 4 个重复 ACK=6，len=0，按照 Reno 算法：

• 在收到 3 个重复 ACK=6 时，设置 cwnd = cwnd/2，即 cwnd = (4 + 1/16)。启动快速重传，将 6 号包重传给客户端；
• 在收到 4 个重复 ACK=6 时，TCP 会启动快速恢复，如果有未发送的数据包，会继续发送；
• 如果接收端收到了重传的 6 号包，就会发送 ACK=7, len=0 的响应。收到此响应的发送端，就要结束快速恢复，进入拥塞避免。

一切看起来很顺利，实际上并不那么美好。假如在快速恢复阶段，发送端发送了 13、14 号包，接收端又会发送 2 次 ACK=7, len=0 的响应。此时的发送端又会收到 3 个重复的 ACK=7, len=0，设置 cwnd = cwnd/2，即 cwnd = (2 + 1/32)，启动快速重传，然后进入快速恢复。

cwnd 经过连续两次减半操作，几乎回到了初始值 IW。仅仅是因为连续丢了 3 个包，cwnd 就要经受连续的减半操作，这极大的降低传输性能。现在看来，Reno 算法只能适应丢失 1 个包的场景，当有连续丢包出现，Reno 算法是存在缺陷的，因此 NewReno 算法又做了进一步的改善。

NewReno 算法

TCP NewReno 算法在 RFC 6582 中定义。NewReno 算法对快速恢复的修正方法是记录当前发送的最大序列号，叫做恢复点（Recovery Point），只有当 ACK 的序列号大于此恢复点，才停止快速恢复，进入拥塞避免。

有了 NewReno 算法的修正，一切就完美了吗？那就让我们继续下面的讨论。

SACK 算法

在 Reno 和 NewReno 算法中，当 TCP 出现超时重传或快速重传，只能判断出“网络可能发生了丢包，需要重传”，但是并不知道丢失哪些报文段，所以只能从已发送未确认的第一个报文段开始重传，由于不知道准确的丢包信息，每个 RTT 周期只能重传一个报文段。这对于同一个窗口丢失了多个报文段的场景来说，不利于快速重传所有丢失的报文段。我们再分析下图所示的情景：

从图中可以看出，在标号 1 和 2 的位置，Segment 2 和 Segment 3 丢失了，在标号 3 的位置，进入了快速重传，重传了 Segment 2；经过几轮交互以后，在标号 4 的位置，进入了快速重传，重传了 Segment 3。如果在标号 3 的位置，同时重传了 Segment 2 和 Segment 3 ，是不是会更好呢？

于是 TCP 又开发了 SACK（Selected acknoledgement）算法，在 RFC 2883 中有详细的说明。

在连接建立阶段，通过 “是否支持 SACK 的标志选项”来告诉对方是否支持 SACK 机制，标志选项的 Kind = 4。当接收端发现有报文段丢失，通过 TCP 选项来汇报自己已经接收到的报文段，选项格式如下：

                  +--------+--------+
                  | Kind=5 | Length |
+--------+--------+--------+--------+
|      Left Edge of 1st Block       |
+--------+--------+--------+--------+
|      Right Edge of 1st Block      |
+--------+--------+--------+--------+
|                                   |
/            . . .                  /
|                                   |
+--------+--------+--------+--------+
|      Left Edge of nth Block       |
+--------+--------+--------+--------+
|      Right Edge of nth Block      |
+--------+--------+--------+--------+

保存接收报文段的 SACK 选项的 Kind 是 5，报文段是以 [begin, end] 区间的形式表示，表示 begin 和 end 之间的报文段都已经到达接收端，begin 和 end 都占用 4 个字节长度。

SACK 一般要和 TSOPT 选项配合使用。对于最多支持 40 字节的 TCP Option，SACK 最多能可以包含 3 个 blocks，计算方法如下：

2bytes padding + TSOPT(2+8bytes) + SACK(2 + 3*8 bytes) + 2 bytes padding

当一个窗口内有多个报文段丢失:

• 对于接收端来说，在 ACK 中报告其接收到的不连续的报文段，使发送方准确地知道哪些报文段被正确接收。
• 对于发送端来说，使用选择性重传机制，可以在一个窗口中一次性重传所有丢失的报文段。

FACK 算法

前一小节介绍的 SACK 算法可以帮助发送端准确地计算出丢失的报文段，在快速重传的时候可以一次性重传所有丢失的报文段。如果在一个窗口内重传的报文段很多，也可能导致网络拥塞更加恶化。为此，Matthew Mathis and Jamshid Mahdavi 发明了 FACK（Forward Acknowledgement）算法，用做快速重传过程中的流控机制。

FACK 需要配合 SACK 才能工作，用变量 snd.fack 记录 SACK 中最大的Sequence Number，用变量 retran_data 记录已经重传的报文段大小，那么通过 snd.nxt – snd.fack + retran_data 可以计算出网络中正在传输的数据的大小(flight size)。

对于支持 FACK 算法的 TCP 来说，触发快速重传的条件有两个：

• 一是 TCP 发送端收到了 3 个重复 ACK。

• 二是流入网络中的数据大于 3 个最大报文段的长度，代码如下：

  if ((snd.fack - snd.una) > (3 * MSS) || (dupacks == 3)) {
  ...
  }
  

到目前为止，我们讨论的拥塞控制算法都是需要 TCP 自己学习，那么真的没有显式通知机制吗？最后，让我们再探讨一下 ECN 机制。

ECN 机制

早期的路由器在丢包以后，没有显式的通知机制，所以 TCP 开发了很多算法自己来探测网络丢包。目前路由器支持了 ECN(explict congestion notify) 机制，可以让 TCP 发送端提前得知是否产生了网络拥塞。

在 RFC 3168 中定义了 ECN 的设计目标，是通过 TCP 发送端和接收端以及中间路由器的配合，感知网络拥塞，并主动的降低 TCP 的发送速率，尽早避免拥塞，使网络性能达到最大化利用。

针对 ECN 功能，IP 头和 TCP 头都有相应的修改。在 IP 头中包含了 ECN 标志位，在 TCP 头中包含了 ECE 标志位。ECE 标志位和 ECN 标志位需要相互配合使用，详情可以参考 RFC 3168 ，本文不再展开介绍了。

总结

本文重点是介绍 TCP 的拥塞控制机制，然而对于初学者来说，一下难以接受这么抽象的概念。所以，我们首先讨论了生活中的道路拥堵问题，网络拥塞的现象类似生活中的道路拥堵，我们说 IP 分组类似机动车辆，各种收费站、检查站类似路由器，收费站会造成道路拥堵，路由器会造成网络拥塞。

当发生了网络拥塞，并不会显式通知 TCP 的发送端，这就需要 TCP 有自学习的能力，自己判断是否发生了网络拥塞。本文讨论的 Tahoe 算法、Reno 算法、NewReno 算法都是用来解决网络拥塞问题的，这些算法的核心点就是慢启动、拥塞避免、快速重传、快速恢复。SACK 算法、FACK 算法是在这些算法基础之上的进一步完善，以便适应更多的应用场景。

最后我们简单介绍了一下 ECN 机制，这是需要主机和路由器同时支持的一种显式地拥塞通知机制。由于 ECN 内容也很多，我们没有展开介绍，你有兴趣的话可以继续阅读 RFC 3168。

思考时间

1. 请解释 DSACK 的工作原理。

2. 请尝试学习 Google 开发的 BBR 算法。