TCP 拥塞控制详解

本文主要介绍 TCP 拥塞控制算法，内容多来自网上各个大佬的博客及《TCP/IP详解》一书，在此基础上进行梳理总结，与大家分享。因水平有限，内容多有不足之处，请大佬轻喷。

一、TCP 首部格式

在了解 TCP 的拥塞控制之前，先来看看 TCP 的首部格式和一些基本概念。

TCP 头部标准长度是20字节。包含源端口、目的端口、序列号、确认号、数据偏移、保留位、控制位、窗口大小、校验和、紧急指针、选项等。

1.1 数据偏移（Data Offset）

该字段长4位，单位为4字节。表示为 TCP 首部的长度。所以TCP 首部长度最多为60字节。

1.2 控制位

目前的 TCP 控制位如下，其中 CWR 和 ECE 用于拥塞控制，ACK、RST、SYN、FIN 用于连接管理及数据传输。

CWR：用于 IP 首部的 ECN 字段。ECE 为 1 时，则通知对方已将拥塞窗口缩小。
ECE：在收到数据包的 IP 首部中 ECN 为 1 时将 TCP 首部中的 ECE 设置为 1，表示从对方到这边的网络有拥塞。
URG：紧急模式
ACK：确认
PSH：推送，接收方应尽快给应用程序传送这个数据。没用到
RST：该位为 1 表示 TCP 连接中出现异常必须强制断开连接。
SYN：初始化一个连接的同步序列号
FIN：该位为 1 表示今后不会有数据发送，希望断开连接。

1.3 窗口大小（Window）

该字段长度位16位，即 TCP 数据包长度位64KB。可以通过 Options 字段的 WSOPT 选项扩展到1GB。

1.4 选项（Options）

受 Data Offset 控制，长度最大为40字节。一般Option的格式为TLV结构：

Kind / Type（1 Byte）	Length（1 Byte）	Value

常见的 TCP Options 有，SACK 字段就位于该选项中。：

1.5 SACK 选项

SACK 包括了两个 TCP 选项，一个选项用于标识是否支持 SACK，是在 TCP 连接建立时发送；另一种选项则包含了具体的 SACK 信息。

1. SACK_Permitted选项，该选项只允许在TCP连接建立时，有SYN标志的包中设置，也即TCP握手的前两个包中，分别表示通信的两方各自是否支持SACK。

   TCP SACK-Permitted Option:
   Kind: 4
   Length: Variable
   +----------+----------+
   | Kind=4   | Length=2 |
   +----------+----------+

2. SACK(选择性确认) 选项位于 Options 中。该选项参数告诉对方已经接收到并缓存的不连续的数据块，发送方可根据此信息检查究竟是哪些块丢失，从而发送相应的数据块。受TCP 包长度限制，TCP 包头最多包含四组 SACK 字段。

   TCP SACK Option:
   Kind: 5
   Length: Variable
                     +--------+--------+
                     | Kind=5 | Length |
   +--------+--------+--------+--------+
   |      Left Edge Of lst Block       |
   +--------+--------+--------+--------+
   |     Right Edge Of lst Block       |
   +--------+--------+--------+--------+
   |                   .  .  .         |
   +--------+--------+--------+--------+
   |      Left Edge Of nth Block       |
   +--------+--------+--------+--------+
   |     Right Edge Of nth Block       |
   +--------+--------+--------+--------+

3. SACK 的工作原理
   如下图所示， 接收方收到 500-699 的数据包，但没有收到 300-499 的数据包就会回 SACK(500-700) 给发送端，表示收到 500-699 的数据。

二、滑动窗口和包守恒原则

2.1 滑动窗口

为了解决可靠传输以及包乱序的问题，TCP 引入滑动窗口的概念。在传输过程中，client 和 server 协商接收窗口 rwnd，再结合拥塞控制窗口 cwnd 计算滑动窗口 swnd。在 Linux 内核实现中，滑动窗口 cwnd 是以包为单位，所以在计算 swnd 时需要乘上 mss （最大分段大小）。

$$swnd = min(rwnd, cwnd * mss)$$

如下图所示滑动窗口包含4部分：
#1 已收到ack确认的数据。
#2 已发还没收到ack的。
#3 在窗口中还没有发出的（接收方还有空间）。
#4 窗口以外的数据（接收方没空间）

滑动后的示意图如下（收到36的ack，并发出了46-51的数据）：

2.2 包守恒原则

TCP 维护一个发送窗口，估计当前网络链路上能容纳的数据包数量，希望在有数据可发的情况下，回来一个确认包就发出一个数据包，总是保持发送窗口那么多包在网络中流动。

传输的理想情况是要同时达到最大的吞吐量和最小的往返延迟，要达到这个目的，连接必须同时满足两个条件：

1. 以链路瓶颈带宽BtlBw发包 （带宽利用率最高）
2. 保证链路中没有缓存队列（延迟最低）

包守恒原则是拥塞控制的基础。

三、TCP 重传机制

本文重点介绍 TCP 拥塞控制相关，传输流程不在该范围之内，有兴趣的同学可以查阅相关文档。不过 TCP 重传逻辑和拥塞控制中的快速重传有关，所以在真正介绍拥塞控制算法之前，先来了解下 TCP 重传逻辑。

3.1 超时重传 [RFC2988]

RTT（Round Trip Time）由三部分组成：链路的传播时间（propagation delay）、末端系统的处理时间、路由器缓存中的排队和处理时间（queuing delay）。TCP 发送端得到了基于时间变化的 RTT 测量值，就能据此设置 RTO。
$$RTO = γ * RTO$$
当一个重传报文段被再次重传时，则增大 RTO 的退避因子 $γ$ 。通常情况下 $γ$ 值为1，多次重传 $γ$ 加倍增长为2，4，8等。通常 $γ$ 不能超过最大退避因子，Linux 下 RTO 不能超过 TCP_RTO_MAX（默认为 120s）。一旦收到相应的 ACK， $γ$ 重置为1。

下面介绍几种常用的 RTT 算法。

3.1.1 rtt 经典算法 [RFC793]

1）首先，先采样RTT，记下最近几次的RTT值。
2）然后做平滑计算SRTT（ Smoothed RTT）。公式为：（其中的 α 取值在0.8 到 0.9之间，这个算法英文叫Exponential weighted moving average，中文叫：加权移动平均）

$$SRTT = ( α * SRTT ) + ((1- α) * RTT)$$

3）开始计算RTO。公式如下：

$$RTO = min [ UBOUND, max [ LBOUND, (β * SRTT) ] ]$$

其中：

• UBOUND 是最大的 timeout 时间，上限值
• LBOUND 是最小的 timeout 时间，下限值
• β 值一般在1.3到2.0之间。

该算法的问题在于重传时，是用重传的时间还是第一次发数据的时间和ACK 回来的时间计算RTT样本值，另外，delay ack的存在也让 rtt 不能精确测量。

3.1.2 rtt 标准算法（Jacobson / Karels 算法）

该算法 [RFC6298] 特点是引入了最新的RTT的采样$rtt_s$和平滑过的$srtt$的差值做参数来计算。 公式如下：

1. 计算平滑RTT
   $$srtt = srtt + α (rtt_s – srtt)$$

2. 计算平滑RTT和真实的差距（加权移动平均）
   $$rttvar = (1-β)rttvar + β(|rtt_s-srtt|)$$

3. 计算RTO
   $$rto= µ * srtt + ∂ *rttvar$$

4. 考虑到时钟粒度，给RTO设置一个下界。
   $$rto = max(µ * srtt + max(G, ∂ *rttvar), 1000)$$
   这里$G$为计时器粒度，1000ms为整个RTO的下届值。（rfc6298 协议规范里采用保守的1000ms，不过协议也指出可以采用更小的rto值，linux源码中设为 TCP_RTO_MIN = HZ/5，即200ms）。在Linux下，α = 0.125，β = 0.25， μ = 1，∂ = 4 ——这就是算法中的“调得一手好参数”，nobody knows why, it just works…） （Linux的源代码在：tcp_rtt_estimator）。

5. 在首个 SYN 交换前，TCP 无法设置 RTO 初始值。根据 [RFC6298]，RTO 初始值为1s，而初始 SYN 报文段采用的超时间隔为3s。当计算出首个 RTT测量结果$rtt_s$，则按如下方法进行初始化：
   $$srtt = rtt_s$$

$$rttvar = rtt_s/2$$

3.1.3 Karn 算法

在RTT采样测量过程中，如果一个数据包初传后，RTO 超时重传，接着收到这个数据包的 ACK 报文，那么这个 ACK 报文是对应初传TCP报文还是对应重传TCP报文呢？这个问题就是重传二义性的问题。当没有使用 TSOPT 选项，单纯的 ACK 报文并不会指示对应初传包还是重传包，因此就会发生这个问题。
TCP Karn 算法是对经典算法在重传二义性问题上的一种改进。该算法分两部分。

1. 当出现超时重传，接收到重传数据的确认信息时不更新 RTT。即忽略了重传部分，避免重传二义性问题。
2. 对该数据之后的包采取退避策略，仅当接收到未经重传的数据时，该 SRTT 才用于计算 RTO。

因为单纯忽略重传数据时，如果在某一时间，网络闪动，突然变慢了，产生了比较大的延时，这个延时导致要重转所有的包（因为之前的RTO很小），但因为重转的不算，RTO就不会被更新，这是个灾难。而且一发生重传就对现有的RTO值翻倍的方式也很难估算出准确的 RTT。

3.1.4 TCP 时间戳选项（TSOPT）

根据 [RFC1323]，TSOPT 主要有两个用途，一个是 RTTM(round-trip time measurement)，即根据ACK报文中的这个选项测量往返时延；另外一个用途是 PAWS(protect against wrapped sequence numbers)，即防止同一个连接的系列号重叠。另外还有一些其他的用途，如SYN-cookie、 Eifel Detection Algorithm 等等。
TSOPT 为 Options 选项中一种，格式如下：

Kind: 8
Length: 10 bytes
+-------+-------+---------------------+---------------------+
|Kind=8 |  10   |   TS Value (TSval)  |TS Echo Reply (TSecr)|
+-------+-------+---------------------+---------------------+
    1       1              4                     4

RTT测量（RTTM）
当使用这个选项的时候，发送方在 TSval 处放置一个时间戳，接收方则会把这个时间通过 TSecr 返回来。因为接收端并不会处理这个 TSval 而只是直接从 TSecr 返回来，因此不需要双方时钟同步。这个时间戳一般是一个单调增的值，[RFC1323] 建议这个时间戳每秒至少增加1。其中在初始 SYN 包中因为发送方没有对方时间戳的信息，因此 TSecr 会以0填充，TSval 则填充自己的时间戳信息。

防回绕序列号（PAWS）
TCP 判断数据是新是旧的方法是检查数据的序列号是否位于sun.una到sun.una + $2^{31}$的范围内，而序列号空间的总大小为$2^{32}$，即约4.29G。在万兆局域网中，4.29G字节数据回绕只需几秒钟，这时TCP就无法准确判断数据的新旧。
PAWS 假设接收到的每个 TCP 包中的 TSval 都是随时间单调增的，基本思想就是如果接收到的一个 TCP 包中的 TSval 小于刚刚在这个连接上接收到的报文的 TSval，则可以认为这个报文是一个旧的重复包而丢掉。时间戳回绕的速度只与对端主机时钟频率有关。Linux以本地时钟计数（jiffies）作为时间戳的值，假设时钟计数加1需要1ms，则需要约24.8天才能回绕一半，只要报文的生存时间小于这个值的话判断新旧数据就不会出错。

SYN Cookie的选项信息
TCP开启SYN Cookie功能时由于Server在收到SYN请求后不保存连接，故SYN包中携带的选项（WScale、SACK）无法保存，当SYN Cookie验证通过、新连接建立之后，这些选项都无法开启。
使用时间戳选项就可以解决上述问题。将WScale和SACK选项信息编码进32 bit的时间戳值中，建立连接时会收到ACK报文，将报文的时间戳选项的回显信息解码就可以还原WScale和SACK信息。

3.2 Fast Retransmit（快速重传）

快速重传算法概括为：TCP 发送端在观测到至少 dupthresh（一般为3） 个重复 ACK 后，即重传可能丢失的数据分组，而不需等待重传计时器超时。

3.2.1 SACK重传

1. 未启用 SACK 时，TCP 重复 ACK 定义为收到连续相同的 ACK seq。[RFC5681]
2. 启用SACK 时，携带 SACK 的 ACK 也被认为重复ACK。[RFC6675]

如下图所示（绿色为已发送并且被ack的数据包，黄色表示已发送还未确认的数据包，浅绿色为被Sack确认的数据包，蓝色表示还未发送的数据包），设 dupthresh = 3，SACKed_count = 6，从 unAcked 包开始的 SACKed_count - dupthresh 个数据包，即3个数据包会被标记为LOST。

记分板状态如下，红色表示该数据包丢失：

3.2.2 FACK 重传

FACK 是 SACK 的一个激进版本，它拥有标准 SACK 算法的一切性质，除此之外，它假设网络不会使数据包乱序，因此收到最大的被 SACK 的数据包之前，FACK 均认为是丢失的。
FACK 模式下，重传时机为 被SACKed 的包数 + 空洞数 > dupthresh。

如下图所示，设 dupthresh = 3，FACKed_count = 12，从unACKed 包开始的 FACKed_count - dupthresh 个数据包，即9个包会被标记为LOST。

记分板状态如下，红色表示该数据包丢失：

3.2.3 RACK 重传

基本思路
如果数据包 p1 在 p2 之前发送，没有收到 p1 的确认，当收到 p2 的 Sack 时，推断 p1 丢包。
算法简介
每一个 skb 记录发送时间 xmit_time，传输控制块维护全局变量：rack.xmit_time，rack.reo_wnd。rack.xmit_time是接收方已经收到的最新的那个 skb 的发送时间，rack.reo_wnd是乱序的时间窗口大小。

1. 每次收到新的 ACK 后，更新 reo_wnd，其中 rtt_min 为固定时间窗口的 rtt 最小值。
   $$reo_wnd = max(rtt_min / 4, 1ms)$$

2. 每当收到一个 ACK 或者 SACK 的时候，更新 rack.xmit_time。再去遍历发送队列上已经发送但还没有收到确认的数据包（skb），如果满足如下条件，那么标记这个数据包丢了。
   $$rack.xmit_time - skb.xmit_time > reo_wnd$$

3. 如果没有收到确认，那么就用定时器每个一段时间看看有哪些包丢了，如果满足如下条件，那么把这个skb标记为已经丢了：
   $$currentTime > skb.xmit_time + min_rtt + rack.reo_wnd + 1ms$$

注：目前linux内核中只实现了第一种判断方法，定时器还没有实现，这样的话就还没有解决对于尾部包丢失的问题。

3.2.4 乱序检测

乱序检测的目的时探测网络是否发生重排导致的丢包，并以此来更新 dupthresh 值。
只要能收到一个 ACK 或者 SACK，其序列号位于当前已经被 ACK 或 SACK 的数据包最大的序列号之前，就说明网络发生了重排造成了乱序，此时如果涉及的数据包大小大于当前能容忍的网络乱序值，即 dupthresh 值，就说明网络乱序加重了，此时应该更新 dupthresh 值。
之所以保持 dupthresh 的值递增，是考虑其初始值3只是一个经验值，既然真实检测到乱序，如果其值比3小，并不能说明网络的乱序度估计偏大，同时TCP保守地递增乱序度，也是为了让快速重传的进入保持保守的姿态，从而增加友好性。

一旦发现 dupthresh 值更新的情形，FACK的假设便不成立，必须在连接内永久禁用FACK 算法。

3.3 Early Retransmit for TCP（ER 机制）

要解决的问题:
当无法收到足够的 dupack 时，TCP标准的 Fast Retransmit 机制无法被触发，只能等待 RTO 超时才能进行丢包的重传。而 RTO 超时不管是时间等待代价，还是性能损耗代价都很大。

解决方法:
检测出无法收到足够 dupack 的场景，进而降低 dupack threshold 来触发快速重传。从而避免等待 RTO 超时重传，对性能造成较大的损耗。

总结出现dupack不够的情况：
a. cwnd较小
b. 发送窗口里大量的数据包都被丢失了
c. 在数据发送的尾端发生丢包时

但是，上面各种极端的case有共同的特点：
m. 无法产生足够的dupack
n. 没有新的数据包可以发送进入网络

ER 机制就是在判断条件 m 和 n 都成立后，选择降低触发 Fast Retransmit 的阈值，来避免只能通过 RTO 超时重传的问题。

3.4 TCP Tail Loss Probe（TLP 算法）

ER 算法解决了 dupack 较少时无法触发快速重传的问题，但当发生尾丢包时，由于尾包后没有更多数据包，也就无法触发 dupack。TLP 算法通过发送一个 loss probe 包，以产生足够的 SACK/FACK 数据包来触发重传。
TLP 算法会在 TCP 还是 Open 态时设置一个 Probe timeout（PTO），当链路中有未被确认的数据包，同时在 PTO 时间内未收到任何ACK，则会触发 PTO 超时处理机制。
TLP会选择传输序号最大的一个数据包作为 tail loss probe 包，这个序号最大的包可能是一个可以发送的新的数据包，也可能是一个重传包。TLP通过这样一个 tail loss probe 包，如果能够收到相应的 ACK，则会触发 FR 机制，而不是 RTO 机制。

3.5 伪超时与重传

在很多情况下，即使没有出现数据丢失也可能引发重传。这种不必要的重传称为伪重传，其主要造成原因是伪超时，即过早判定超时，其他因素如包失序、包重复，或ACK丢失也可能导致该现象。在实际RTT显著增长，超过当前RTO时，可能出现伪超时。在下层协议性能变化较大的环境中（如无线环境），这种情况出现得比较多。
TCP 为处理伪超时问题提出了许多方法。这些方法通常包含检测算法与响应算法。检测算法用于判断某个超时或基于计时器的重传是否真实，一旦认定出现伪超时则执行响应算法，用于撤销或减轻该超时带来的影响。
检测算法包含 DSACK 、Eifel检测算法、迁移RTO恢复算法(F-RTO) 三种。

3.5.1 DSACK 扩展

DSACK的主要目的是判断何时的重传是不必要的，并了解网络中的其他事项。通过 DSACK 发送端至少可以推断是否发生了包失序、 ACK丢失、包重复或伪重传。
D-SACK使用了 SACK 的第一个段来做标志，
a. 如果SACK的第一个段的范围被ACK所覆盖，那么就是D-SACK。
b. 如果SACK的第一个段的范围被SACK的第二个段覆盖，那么就是D-SACK。
[RFC2883] 没有具体规定发送端对DSACK怎样处理。 [RFC3708] 给出了一种实验算法，利用DSACK来检测伪重传，响应算法可采用Eifel响应算法。

3.5.2 Eifel检测算法 [RFC3522]

实验性的Eifel检测算法利用了 TCP 的 TSOPT 来检测伪重传。在发生超时重传后，Eifel 算法等待接收下一个 ACK，若为针对第一次传输（即原始传输）的确认，则判定该重传是伪重传。

与 DSACK 的比较：
利用 Eifel 检测算法能比仅采用 DSACK 更早检测到伪重传行为，因为它判断伪重传的 ACK 是在启动丢失恢复之前生成的。相反， DSACK 只有在重复报文段到达接收端后才能发送，并且在 DSACK 返回至发送端后才能有所响应。及早检测伪重传更为有利，它能使发送端有效避免“回退N”行为。

3.5.3 迁移RTO恢复算法(F-RTO)

前移RTO恢复（Forward-RTO Recovery，F-RTO）[RFC5682]是检测伪重传的标准算法。它不需要任何TCP选项，因此只要在发送端实现该方法后，即使针对不支持TSOPT的接收端也能有效地工作。该算法只检测由重传计时器超时引发的伪重传，对之前提到的其他原因引起的伪重传则无法判断。

F-RTO 的工作原理如下：

1. F-RTO 会修改TCP的行为，在超时重传后收到第一个 ACK 时，TCP会发送新（非重传）数据，之后再响应后一个到达的 ACK。
2. 如果其中有一个为重复 ACK，则认为此次重传没问题。
3. 如果这两个都不是重复 ACK，则表示该重传是伪重传。
4. 重复ACK是在接收端收到失序的报文段产生的。这种方法比较直观。如果新数据的传输得到了相应的ACK，就使得接收端窗口前移。如果新数据的发送导致了重复ACK，那么接收端至少有一个或更多的空缺。这两种情况下，接收新数据都不会影响整体数据的传输性能。

四、拥塞状态机

TCP 通过拥塞状态机来决定收到 ACK 时 cwnd 的行为（增长或者降低）。TCP 拥塞状态机有 Open,Disorder,Recovery,Lost和CWR五种状态。

4.1 Open

当网络中没有发生丢包，也就不需要重传，sender按照慢启动或者拥塞避免算法处理到来的ACK。

4.2 Disorder

当sender检测到 dupack 或者 SACK，将会转移到 Disorder 状态，当处在这个这个状态中时，cwnd 将维持不变。每收到一个 dupack 或 SACK，发送方将发送一个新包。

4.3 CWR

当 sender 收到 ACK 包含显示拥塞通知（ECN），这个 ECN 由路由器写在IP头中，告诉 TCP sender 网络拥塞，sender 不会立马降低 cwnd，而是根据快速恢复算法进行降窗，直到减为之前的一半。当cwnd正在减小cwnd，网络中有没有重传包时，这个状态就叫CWR，CWR可以被Recovery或者Loss中断。

4.4 Recovery

当sender因为快速重传机制触发丢包时，sender会重传第一个未被ACK的包，并进入Recovery状态。在Recovery状态期间，cwnd的处理同CWR大致一样，要么重传标记了lost的包，要么根据保守原则发送新包。直到网络中所有的包都被ACK，才会退出Recovery进入Open状态，Recovery状态可以被loss状态打断。

1. 经典 Reno 模式（非SACK模式）下，$SND_UNA > SND_HIGH$ 时退出Recovery 状态。

如上图，数据包A、B、C可能没有丢失只是被延迟接收，然而没有SACK机制下无法判断是A、B、C的重传触发的3次重复ACK还是新数据1、2、3丢失1（或者1、2或者1、2、3）导致的重复ACK，两种情况均会马上把拥塞状态机带入到Recovery状态，然而前一种是不必要的。如果在SND_UNA == SND_HIGH 即转为Open 态，那么当发生上述1、2、3的延迟到达后，紧接着的Recovery 状态会再次将拥塞窗口减半，最终降低到一个极低值。

2. SACK/FACK模式下，$SND_UNA >= SND_HIGH$ 时退出Recovery 状态。
   因为即使发生经典 Reno 模式下的A、B、C失序到达，由于存在 SACK 信息，状态机会将此三个重复 ACK 记为三个重复的DSACK，在 SACK 模式下，判断是否进入 Recovery 状态的条件是被 SACK 的数据包数量大于 dupthresh，而 DSACK 不被计入到 SACKed 数量中。FACK 模式下只影响进入 Recovery 状态的时机，其核心仍建立在 SACK 之上，所以不影响退出的时机。

4.5 Loss

当RTO后，TCP sender进入Loss状态，所有在网络中的包被标记为lost，cwnd重置为1，通过slow start重新增加cwnd。Loss与Recovery状态的不同点在于，cwnd会重置为1，但是Recovery状态不会，Recovery状态下拥塞控制通过快速恢复算法逐步降低cwnd至sshthresh。Loss状态不能被其它任何状态中断，只有当网络中所有的包被成功ACK后，才能重新进入Open状态。

五、拥塞控制

拥塞的发生是因为路由器缓存溢出，拥塞会导致丢包，但丢包不一定触发拥塞。
拥塞控制是快速传输的基础。一个拥塞控制算法一般包括慢启动算法、拥塞避免算法、快速重传算法、快速恢复算法四部分。

5.1 慢启动算法

不同拥塞算法慢启动的逻辑有所不同，经典的 NewReno 慢启动的算法如下：

1. 连接建好的开始先初始化 cwnd = 10，表明可以传10个MSS大小的数据。
2. 每当收到一个ACK，cwnd 加1。这样每当过了一个 RTT，cwnd 翻倍，呈指数上升。
3. 还有一个ssthresh（slow start threshold），是一个上限。当cwnd >= ssthresh时，就会进入“拥塞避免算法”。

Linux 3.0后采用了 Google的论文《An Argument for Increasing TCP’s Initial Congestion Window》 的建议——把cwnd 初始化成了 10个MSS。 而Linux 3.0以前，比如2.6，Linux 采用了 [RFC3390] 的建议，cwnd 跟 MSS 的值来变，如果MSS < 1095，则cwnd = 4；如果MSS > 2190，则 cwnd = 2；其它情况下，则是3。

5.2 拥塞避免算法

当 cwnd 增长到 sshthresh 时，就会进入“拥塞避免算法”。拥塞避免算法下 cwnd 成线性增长，即每经过一个往返时间RTT就把发送方的拥塞窗口 cwnd 加1，而不是加倍。这样就可以避免拥塞窗口快速增长的问题。

每收到一个 ack 时 cwnd 的变化：
cwnd = cwnd + 1 / cwnd

5.3 快速重传算法

快速重传算法主要用于丢包检测，以便能更快重传数据包，更早的调整拥塞状态机状态，从而达到持续升窗的目的。
具体重传策略见第三节 重传机制。

5.4 快速恢复算法

当检测到丢包时，TCP 会触发快速重传并进入降窗状态。该状态下 cwnd 会通过快速恢复算法降至一个合理值。从历史发展来看，分为四个个阶段。

5.4.1 BSD初始版本

1. 收到3次重复ACK，ssthresh 设为 cwnd/2，cwnd = cwnd / 2 + 3;
2. 每收到一个重复ACK，窗口值加1;
3. 收到非重复ACK，窗口设为ssthresh，退出

优点：在快速恢复期间，可以尽可能多的发送数据
缺点：由于快速恢复未完成，尽可能多发送可能会加重拥塞。

5.4.2 [RFC3517] 版本

1. 收到3次重复ACK，ssthresh 设为 cwnd/2，cwnd = cwnd / 2 + 3;
2. 每收到一个重复ACK，窗口值加1/cwnd;
3. 收到非重复ACK，窗口设为ssthresh，退出

优点：在快速恢复期间，可以尽少量的发送数据（有利于拥塞恢复），且在快速恢复时间段的最后阶段，突发有利于抢带宽。
缺点：快速恢复末期的突发不利于公平性。

5.4.3 Linux rate halving算法

Linux 上并没有按照 [RFC3517] 标准实现，而是做了一些修改并运用到内核中。

1. 收到3次重复ACK，sshthresh设置为cwnd/2，窗口维持不变。
2. 每收到两个ACK（不管是否重复），窗口值减1：cwnd = cwnd - 1。
3. 新窗口值取cwnd = MIN(cwnd, in_flight+1)。
4. 直到退出快速恢复状态，cwnd = MIN(cwnd, ssthresh)。

   六、常见的拥塞算法

   6.1 New Reno 算法

   New Reno算法包含第五节中介绍的慢启动算法、拥塞避免算法、快速重传算法和prr算法。在此就不赘述。

   

   6.2 CUBIC 算法

   CUBIC 算法和 Reno 算法区别主要在于慢启动和拥塞避免两个阶段。因为Reno算法进入拥塞避免后每经过一个RTT窗口才加 1，拥塞窗口增长太慢，导致在高速网络下不能充分利用网络带宽。所以为了解决这个问题，BIC 和 CUBIC算法逐步被提了出来。

   (BIC 算法基于二分查找，实现复杂，不看了。)

   cubic 算法源码见 tcp_cubic 文件。

   6.2.1 CUBIC 算法原理

   

   CUBIC 的窗口增长函数是一个三次函数，非常类似于 BIC-TCP 的窗口增长函数。CUBIC 的详细运行过程如下，当出现丢包事件时，CUBIC 同 BIC-TCP 一样，会记录这时的拥塞窗口大小作为$W_{max}$，接着通过因子 $β$ 执行拥塞窗口的乘法减小，这里 $β$ 是一个窗口降低常数，并进行正常的 TCP 快速恢复和重传。从快速恢复阶段进入拥塞避免后，使用三次函数的凹轮廓增加窗口。三次函数被设置在 $W_{max}$ 处达到稳定点，然后使用三次函数的凸轮廓开始探索新的最大窗口。

   CUBIC 的窗口增长函数公式如下所示：

   $$W(t) = C(t - K)^3 + W_{max}$$

   其中，W(t) 代表在时刻 t 的窗口大小，C是一个 CUBIC 的常量参数，t 是从上次丢包后到现在的时间，以秒为单位。K 是上述函数在没有进一步丢包的情况下将 W 增加到 $W_{max}$ 经历的时间，其计算公式如下：

   $$K = \sqrt[3]{ \frac {W_{max} * (1 - β) } {C} }$$

   其中 $β$ 也是常量。

   6.2.2 Wmax 的更新

   每次丢包后，CUBIC-TCP 会开启一个新的时段，并取$max(last_max_cwnd , cwnd)$作为当前 $W_{max}$ 饱和点，记录在 bic_origin_point 字段中，源码如下：

   static inline void bictcp_update(struct bictcp *ca, u32 cwnd, u32 acked)
   {
       // ...
     if (ca->epoch_start == 0) {  //丢包后，开启一个新的时段
       ca->epoch_start = tcp_jiffies32;	/* record beginning */
       ca->ack_cnt = acked;			/* start counting */
       ca->tcp_cwnd = cwnd;			/* syn with cubic */
   
       //取max(last_max_cwnd , cwnd)作为当前Wmax饱和点
       if (ca->last_max_cwnd <= cwnd) {
         ca->bic_K = 0;
         ca->bic_origin_point = cwnd;
       } else {
         /* Compute new K based on
   			 * (wmax-cwnd) * (srtt>>3 / HZ) / c * 2^(3*bictcp_HZ)
   			 */
         ca->bic_K = cubic_root(cube_factor
                    * (ca->last_max_cwnd - cwnd));
         ca->bic_origin_point = ca->last_max_cwnd;
       }
     }
       //...
   }

   6.2.3 hystart 混合启动算法

   标准的慢启动在BDP网络环境下表现不好，不好的原因主要有两个：

   1. 标准慢启动的拥塞窗口指数式的增长方式过于激进容易导致大量丢包，丢包恢复性能损耗太大。
      在ssthreshold值设置的过高时，慢启动一段时间后，cwnd的指数增长会显得过快。有可能在上一个RTT，cwnd刚好等于BDP；下一个RTT，cwnd就等于2BDP了。这样就可能导致多出的一个BDP的数据包被丢弃。这类丢包属于突发丢包（burst packet losses）。
   2. 被优化过的慢启动机制，丢包时在数据包重传恢复的时候碰巧试图去减小服务器的负载，导致数据包恢复慢。

   总结这些原因都是因为慢启动过程过于盲目，不能及时的预测拥塞，导致了大量丢包，所以混合慢启动机制的主要作用是在慢启动阶段试图找到“合理 ”的退出慢启动进入拥塞避免状态点（safe exit point）。

   Hystart 算法通过 ACK train 信息判断一个 Safe Exit Point for Slow Start. 同时为了避免计算带宽，通过一个巧妙的转换(具体建议看论文)，只要判断时间差是否超过 Forward one-way delay($D_{min}$)来决定是否退出慢启动。

   Hystart 算法通过以下两个条件来判断是否应该退出慢启动

   1. 一个窗口内的数据包的总传输间隔是否超过$D_{min}$
   2. 数据包的RTT sample(默认8个样本)是否出现较大幅度的增长。
      如果前面8个样本中的最小rtt大于全局最小rtt与阈值的和，那么表示网络出现了拥塞，应立马进入拥塞避免阶段

   6.3 BBR算法

   BBR 全称 bottleneck bandwidth and round-trip propagation time。基于包丢失检测的 Reno、NewReno 或者 cubic 为代表，其主要问题有 Buffer bloat 和长肥管道两种。和这些算法不同，bbr 算法会时间窗口内的最大带宽 max_bw 和最小RTT min_rtt，并以此计算发送速率和拥塞窗口。

   6.3.1 BBR 算法原理

   如下图所示，当没有足够的数据来填满管道时，RTprop决定了流的行为；当有足够的数据填满时，那就变成了BtlBw来决定。这两条约束交汇在点 inflight = BtlBw*RTprop，也就是管道的BDP（带宽与时延的乘积）。当管道被填满时，那些超过的部分（inflight-BDP）就会在瓶颈链路中制造了一个队列，从而导致了RTT的增大。当数据继续增加直到填满了缓存时，多余的报文就会被丢弃了。拥塞就是发生在BDP点的右边，而拥塞控制算法就是来控制流的平均工作点离BDP点有多远。

   
   RTProp : round-trip propagation time
   BtlBW : bottleneck bandwidth

   基于丢包的拥塞控制算法工作在bandwidth-limited区域的右边界区域，尽管这种算法可以达到最大的传输速率，但是它是以高延迟和高丢包率作为代价的。在存储介质较为小的时候，缓存大小只比BDP大一点，此时这种算法的时延并不会很高。然而，当存储介质变得便宜之后，交换机的缓存大小已经是ISP链路BDP的很多很多倍了，这导致了bufferbloat，从而导致了RTT从毫秒级升到了秒级。

   当一个连接满足以下两个条件时，它可以在达到最高的吞吐量的同时保持最低时延：

   1. 速率平衡：瓶颈带宽的数据到达速率与BtlBw相等；
   2. 填满管道：所有的在外数据（inflight data）与BDP（带宽与时延的乘积）相等

   bbr 算法关于拥塞窗口的核心就是计算 BtlBW 和 RTprop，根据这两者值计算 BDP。BtlBw和RTprop可能是动态变化的，所以需要实时地对它们进行估计。

   计算 RTprop

   目前TCP为了检测丢包，必须实时地跟踪RTT的大小。在任意的时间t，

   $$RTT_t = RTprop_t + η _t$$

   其中$η_t$表示“噪音”。造成噪声的因素主要有：链路队列，接收方的时延ACK配置，ACK聚合等因素等待。RTprop是路径的物理特性，并且只有路径变化才会改变。由于一般来说路径变化的时间尺度远远大于RTprop，所以RTprop可以由以下公式进行估计：

   $$\overline{RTprop} = RTprop + min(η _t) = min(RTT_t) ∀ t ∈ [T−W_R,T] $$

   即，在一个时间窗口中对RTT取最小值。一般将该窗口大小设置为几十秒至几分钟。

   计算 BtlBW

   bottleneck bandwidth的估计不像RTT那样方便，没有一种TCP spec要求实现算法来跟踪估计bottleneck带宽，但是，可以通过跟踪发送速率来估计bottleneck带宽。当发送方收到一个ACK报文时，它可以计算出该报文的RTT，并且从发出报文到收到ack报文这段时间的data Inflight。这段时间内的平均发送速率就可以以此计算出来：$$delivery_rate = delta_delivered/ delta_t$$
   这个计算出的速率必定小于bottleneck速率（因为delta delivered是确定的，但是delta t会较大）。因此，BtlBw可以根据以下公式进行估计。
   $$\overline{BtlBw} = max(delivery_rate_t)∀t∈[T-W_B, T]$$
   其中，时间窗口大小的值一般为6~10个RTT。

   TCP必须记录每个报文的离开时间从而计算RTT。BBR必须额外记录已经发送的数据大小，使得在收到每一个ACK之后，计算RTT及发送速率的值，最后得到RTprop和BtlBw的估计值。

   6.3.2 pacing_rate 和 cwnd

   bbr 算法输出 pacing_rate 和 cwnd 两个数据。pacing_rate 决定发包速率，cwnd 为窗口大小。每一次ACK 都会根据当前的模式计算 pacing_rate 和 cwnd。注意在计算 pacing_rate 和 cwnd 时有 pacing_gain 和 cwnd_gain 两个参数，

   bottleneck_bandwidth = windowed_max(delivered / elapsed, 10 round trips)
   min_rtt = windowed_min(rtt, 10 seconds)
   
   pacing_rate = pacing_gain * bottleneck_bandwidth
   cwnd = max(cwnd_gain * bottleneck_bandwidth * min_rtt, 4)

   

   6.3.3 BBR 状态机

   BBR 算法也是基于状态机。状态机有STARTUP、DRAIN、PROBE_BW、PROBE_RTT四种状态。不同状态下 pacing_gain 和 cwnd_gain 的取值会有所不同。

   

   STARTUP：初始状态，该状态下类似于传统拥塞控制的慢启动阶段。该状态下pacing_gain和cwnd_gain为 2/ln(2)+1。因为这是最小的能够达到 Reno 或者 CUBIC算法启动速度的值。

   /* We use a high_gain value of 2/ln(2) because it's the smallest pacing gain
    * that will allow a smoothly increasing pacing rate that will double each RTT
    * and send the same number of packets per RTT that an un-paced, slow-starting
    * Reno or CUBIC flow would:
    */
   static const int bbr_high_gain  = BBR_UNIT * 2885 / 1000 + 1;

   DRAIN：该状态为排除状态。在STARTUP状态下三轮没有涨幅超过25%时会进入该状态。该状态下BtlBw会根据bbr_drain_gain逐渐降低，直到 inflight 降到 BDP 为止。

   /* The pacing gain of 1/high_gain in BBR_DRAIN is calculated to typically drain
    * the queue created in BBR_STARTUP in a single round:
    */
   static const int bbr_drain_gain = BBR_UNIT * 1000 / 2885;

   PROBE_BW：该状态下会照常计算当前的bw，即瞬时带宽。然而在计算pacing rate 以及 cwnd 时，并不会像在STARTUP状态时那样用一个很大的增益系数去扩张pacing rate和cwnd，而是顺序的在[5/4，3/4，1，1，1，1，1，1]中选一个，感官上bw就在其停止增长的地方上下徘徊了。

   /* The gain for deriving steady-state cwnd tolerates delayed/stretched ACKs: */
   static const int bbr_cwnd_gain  = BBR_UNIT * 2;
   /* The pacing_gain values for the PROBE_BW gain cycle, to discover/share bw: */
   static const int bbr_pacing_gain[] = {
     BBR_UNIT * 5 / 4,	/* probe for more available bw */
     BBR_UNIT * 3 / 4,	/* drain queue and/or yield bw to other flows */
     BBR_UNIT, BBR_UNIT, BBR_UNIT,	/* cruise at 1.0*bw to utilize pipe, */
     BBR_UNIT, BBR_UNIT, BBR_UNIT	/* without creating excess queue... */
   };

   PROBE_RTT：当PROBE_BW检测到连续10s没有更新min rtt时就会进入该状态。该状态的目标是保持BBR的公平性并定期排空瓶颈队列，以收敛到真实的min_rtt。进入该模式时，BBR 会将 cwnd 的上限设置为4个数据包。在flight pkg <= 4后开始进行rtt探测，探测时间为200ms，探测结束后BBR 便会记录min rtt，并离开PROBE_RTT进入相应的模式。代码见bbr_update_min_rtt函数。

   Q：为什么PROBE_BW阶段 bbr_cwnd_gain 为 2？
   保证极端情况下，按照pacing_rate 发送的数据包全部丢包时也有数据继续发送，不会产生空窗期。

   Q：为什么在探测最小RTT的时候最少要保持4个数据包
   4个包的窗口是合理的，infilght分别是：刚发出的包，已经到达接收端等待延迟应答的包，马上到达的应答了2个包的ACK。一共4个，只有1个在链路上，另外1个在对端主机里，另外2个在ACK里。路上只有1个包。

   6.3.5 BBR 算法表现

   BBR将它的大部分时间的在外发送数据都保持为一个BDP大小，并且发送速率保持在估计得BtlBw值，这将会最小化时延。但是这会把网络中的瓶颈链路移动到BBR发送方本身，所以BBR无法察觉BtlBw是否上升了。所以，BBR周期性的在一个RTprop时间内将pacing_gain设为一个大于1的值，这将会增加发送速率和在外报文。如果BtlBw没有改变，那么这意味着BBR在网络中制造了队列，增大了RTT，而deliveryRate仍然没有改变。（这个队列将会在下个RTprop周期被BBR使用小于1的pacing_gain来消除）。如果BtlBw增大了，那么deliveryRate增大了，并且BBR会立即更新BtlBw的估计值，从而增大了发送速率。通过这种机制，BBR可以以指数速度非常快地收敛到瓶颈链路。
   如下图所示，在1条10Mbps，40ms的流在20s稳定运行之后将BtlBw提高了1倍（20Mbps），然后在第40s又将BtlBw恢复至20Mbps。

   

   下图展示了1个10Mbps，40ms的BBR流在一开始的1秒内，发送方（绿线）和接收方（蓝线）的过程。红线表示的是同样条件下的CUBIC发送。垂直的灰线表示了BBR状态的转换。下方图片展示了两种连接的RTT在这段时间的变化。注意，只有收到了ACK（蓝线）之后才能确定出RTT，所以在时间上有点偏移。图中标注了BBR何时学习到RTT和如何反应。

   

   下图展示了在上图中展示的BBR和CUBIC流在开始8秒的行为。CUBIC（红线）填满了缓存之后，周期性地在70%~100%的带宽范围内波动。然而BBR（绿线）在启动过程结束后，就非常稳定地运行，并且不会产生任何队列。

   

   下图展示了在一条100Mbps，100ms的链路上，BBR和CUBIC在60秒内的吞吐量与随机丢包率（从0.001%~50%）的关系。在丢包率只有0.1%的时候，CUBIC的吞吐量就已经下降了10倍，并且在丢包率为1%的时候就几乎炸了。而理论上的最大吞吐量是链路速率乘以（1-丢包率）。BBR在丢包率为5%以下时还能基本维持在最大吞吐量附近，在15%丢包率的时候虽然有所下降但还是不错。

   

   6.4 Westwood算法

   TCP Westwood算法简称TCPW，和 bbr 算法类似是基于带宽估计的一种拥塞控制算法。TCPW 采用和 Reno 相同的慢启动算法、拥塞避免算法。区别在于当检测到丢包时，根据带宽值来设置拥塞窗口、慢启动阈值。

   6.4.1 如何测量带宽 bw_est

   和 bbr 算法不同，tcpw 带宽计算相当粗糙。tcpw 每经过一个RTT 测量一次带宽。假设经过时间为 delta，该时间内发送完成的数据量为 bk，则采样值为 bk / delta。然后和 rtt 一样，带宽采样值会经过一个平滑处理算出最终的带宽值。

   $$bw_ns_est(k) = (7/8) * bw_ns_est(k-1) + (1/8) * bk / delta;$$ $$bw_est(k) = (7/8) * bw_est(k-1) + (1/8) * bw_ns_est(k) ; $$

   6.4.2 如何确认单位时间的发送量bk

   tcpw 采用一种粗糙的估算方式。在收到回包后，会根据当前的snd_una 和之前的 snd_una 之间的差值来估算被 ACK 的字节数，即关于SACK的信息会被丢失。具体逻辑见westwood_acked_count函数。

   static inline u32 westwood_acked_count(struct sock *sk)
   {
     const struct tcp_sock *tp = tcp_sk(sk);
     struct westwood *w = inet_csk_ca(sk);
   
     w->cumul_ack = tp->snd_una - w->snd_una;
   
     /* If cumul_ack is 0 this is a dupack since it's not moving
   	 * tp->snd_una.
   	 */
     if (!w->cumul_ack) {
       w->accounted += tp->mss_cache;
       w->cumul_ack = tp->mss_cache;
     }
   
     if (w->cumul_ack > tp->mss_cache) {
       /* Partial or delayed ack */
       if (w->accounted >= w->cumul_ack) {
         w->accounted -= w->cumul_ack;
         w->cumul_ack = tp->mss_cache;
       } else {
         w->cumul_ack -= w->accounted;
         w->accounted = 0;
       }
     }
   
     w->snd_una = tp->snd_una;
   
     return w->cumul_ack;
   }

   6.4.3 计算 ssthresh

   计算ssthresh 公式很简单： $$ssthresh = bw_est * Rtt_{min}$$
   源码如下：

   /*
    * TCP Westwood
    * Here limit is evaluated as Bw estimation*RTTmin (for obtaining it
    * in packets we use mss_cache). Rttmin is guaranteed to be >= 2
    * so avoids ever returning 0.
    */
   static u32 tcp_westwood_bw_rttmin(const struct sock *sk)
   {
     const struct tcp_sock *tp = tcp_sk(sk);
     const struct westwood *w = inet_csk_ca(sk);
   
     return max_t(u32, (w->bw_est * w->rtt_min) / tp->mss_cache, 2);
   }

   七、参考文档

   TCP 的那些事儿（上）
   TCP 的那些事儿（下）
   TCP系列08—连接管理—7、TCP 常见选项(option)
   TCP timestamp
   Early Retransmit for TCP
   TCP Tail Loss Probe(TLP)
   TCP重点系列之拥塞状态机
   Congestion Control in Linux TCP
   TCP拥塞控制图解
   TCP进入快速恢复时的窗口下降算法
   tcp中RACK算法
   TCP系列23—重传—13、RACK重传
   TCP系列18—重传—8、FACK及SACK reneging下的重传
   TCP RTO计算方法以及go实现验证
   Calculating TCP RTO