TCP拥塞机制学习_tcp 丢包后cwd

TCP拥塞机制学习

写在前面

很早就想总结一下tcp方面的知识了，心动不如行动，这一块面试重点，而其也是coder的必修课。

一、TCP头部报文格式

了解任何一个协议都要从它的协议报文开始，我们先看一下他的格式和一些基本概念。

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

1.1 数据偏移（Data Offset)

该字段长4位，单位是4字节。表示tcp头部的长度，默认一般是20字节，最大就是1111（二进制）*4字节 = 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
2
3
4
5
6
7
8

1.3 窗口大小（Window)

该字段长度位16位，单位字节，即TCP数据包长度为64kb。此字段用来进行流量控制。代表本机期望一次接收的字节数。它可以通过Options字段的WSOPT选项拓展到1GB。

1.4 选项（Options)

受Data Offset 控制，长度最大为40字节= tcp头部最大字节数量60 - 默认20其它字节的。 一般Option的格式为TLV结构：

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

Request For Comments（RFC），是一系列以编号排定的文件。文件收集了有关互联网相关信息，以及UNIX和互联网社区的软件文件。RFC文件是由Internet Society（ISOC）赞助发行。基本的互联网通信协议都有在RFC文件内详细说明。RFC文件还额外加入许多在标准内的论题，例如对于互联网新开发的协议及发展中所有的记录。因此几乎所有的互联网标准都有收录在RFC文件之中。
1

1.5 SACK选项

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

1、SACK_Permitted选项，该选项只允许在TCP链接建立时，有SYN标志的包中设置，也就是三次握手的前两次握手包中，分别代表通信双方是否支持SACK。

2、SACK(选择性确认)选项位于Options中。该选项参数告诉对方已经接收到并缓存的不连续的数据块，发送发可以根据此信息检查究竟是哪些块丢失，从而发送相应的数据块。

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       |
          +--------+--------+--------+--------+
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3、SACK的工作原理

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

1.6 顺序号（Sequence Number)

占32bit，用来标识从TCP源端向TCP目标端发送的数据字节流，它表示在这个报文段中的第一个数据字节。

1.7 确认号（Acknowledgment Number)

占32比特。只有ACK标志为1时，确认号字段才有效。它包含目标端所期望收到源端的下一个数据字节。

二 滑动窗口和包守恒原则

2.1 滑动窗口

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

swnd = min(rwnd,cwnd*mss)
也就是滑动窗口等于拥塞窗口和接受窗口的最小值
1
2

如下图所示滑动窗口包含4部分：

• 已收到ack确认的数据；
• 已发还没收到ack的；
• 在窗口中还没发出去的（接收方还有空间）；
• 窗口以外的数据（接收方没空间）。

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

2.2 包守恒原则

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

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

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

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

三、TCP重传机制

3.1 超时重传【RFC2998】

RTT(Round Trip Time) 由三部分组成：链路的传播时间（propagation delay、就是发送和回来在链路的时间）、末端系统的处理时间（请求到后端服务处理消耗的时间）、路由器缓存中的排队和处理时间（queuing delay)。

RTT是针对链接的，也就是一个tcp链接对应一个RTT。	
1

TCP发送端得到了基于时间变化的RTT测量值，就能根据此设置RTO(Retransmission Time Out, 重传超时时间)。

RTO = x * RTO
1

当一个重传报文段再次被重传时，则增大x因子。通常情况下x值为1，多次重传x加倍增长为2，4，8等。通常x不超过最大退避因子，Linux下RTO不能超过TCP_RTO_MAX(默认为120s)。一旦收到对应的ACK， x重置为1。

触发机制：

每个数据包都有对应的计时器，一旦超过RTO而没有接收到ACK,就重发该数据包。这时候不仅会发生重传，其实还会降低当前的数据发送速率，因为它认定此时网络里面发生了阻塞。

对于顺序ack来说，比如你发了5、6、7、8四个包，但是6、7、8服务器接收到了，可以ack,但是由于5没收到，所以它还是不能先把6、7、8ack，可能导致客户端认为5~8都重传，效率低下。可以通过开启SACK采用快速重传，来避免这个问题。

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

3.1.1 rtt经典算法【RFC793】

1、首先，先采样RTT，记下最近几次的RTT值。

2、然后做平滑计算SRTT(Smoothed RTT)。公式为：（（其中的 α 取值在 0.8 到 0.9 之间，这个算法英文叫 Exponential weighted moving average，中文叫：加权移动平均）

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

其中：

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

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

3.1.2 Karn算法

在 RTT 采样测量过程中，如果一个数据包初传后，RTO 超时重传，接着收到这个数据包的 ACK 报文，那么这个 ACK 报文是对应初传 TCP 报文还是对应重传 TCP 报文呢？这个问题就是重传二义性的问题。当没有使用 TSOPT 选项，单纯的 ACK 报文并不会指示对应初传包还是重传包，因此就会发生这个问题。 TCP Karn 算法是对经典算法在重传二义性问题上的一种改进。该算法分两部分。 1) 当出现超时重传，接收到重传数据的确认信息时不更新 RTT。即忽略了重传部分，避免重传二义性问题。 2) 对该数据之后的包采取退避策略，仅当接收到未经重传的数据时，该 SRTT 才用于计算 RTO。

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

3.1.3 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
1
2
3
4
5
6

RTT 测量（RTTM）

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

防回绕序列号（PAWS）

TCP 判断数据是新是旧的方法是检查数据的序列号是否位于 sun.una 到 sun.una 的范围内，而序列号空间的总大小约 4.29G。在万兆局域网中，4.29G 字节数据回绕只需几秒钟，这时 TCP 就无法准确判断数据的新旧。

PAWS 假设接收到的每个 TCP 包中的 TSval 都是随时间单调增的，基本思想就是如果接收到的一个 TCP 包中的 TSval 小于刚刚在这个连接上接收到的报文的 TSval，则可以认为这个报文是一个旧的重复包而丢掉。时间戳回绕的速度只与对端主机时钟频率有关。Linux 以本地时钟计数（jiffies）作为时间戳的值，假设时钟计数加 1 需要 1ms，则需要约 24.8 天才能回绕一半，只要报文的生存时间小于这个值的话判断新旧数据就不会出错。

SYN Cookie 的选项信息

TCP 开启 SYNCookie 功能时由于 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 基础快速重传

这个重传机制解决了超时重传的两个弊端：

1. 超时时间过长，导致了重传时间间隔过长；
2. 如果服务器收到乱序包，它也会发送ACK，只不过是发送的最后一个到达包到达的ack(也就是说普通的超时重传在收到乱序包时是不会有动作的，而是等待计时器超时，触发重传)。

这样它重传的机制就是如果客户端收到了三个重复ack，就认为存在包丢失，发起重传。

但是这里就会存在一个问题，就是重传多少个包，因为这里的ack是一样的，比如是5，但是6、7、8可能服务器以及收到了，只是受限于滑动窗口的策略，不能返回ack罢了。下面的sack解决了这个问题。

3.2.2 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.3 FACK重传

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

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

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

3.2.4 RACK重传

RACK(Recent ACKnowledgment)是一种新的基于时间的丢包探测算法，RACK的目的是取代传统的基于dupthresh门限的各种快速重传及其变种。前面介绍的各种基于dup ACK的快速重传算法及其变种通过修改dupthresh门限等手段，有些可以迅速的探测到丢包，有些可以精确的探测丢包，但是没有能同时达到迅速和精确两个目标的算法。

出现原因：
在现今的网络环境中乱序传输是一个比较常见的场景，使用dupthresh和dup ACK来做丢包探测的可靠性越来越低。同时因为传统的基于系列号空间的乱序度来探测丢包时，如果发生报文重传，初传报文和重传报文在系列号空间就会重叠。而RACK基于时间的乱序来探测丢包的时候，重传报文和初传报文在时间线上是不重叠的，因此RACK可以同时利用初传报文和重传报文来探测丢包。
1
2

基本思路 如果数据包 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 最小值。

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

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

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

3.2.5 乱序检测

乱序检测的目的时探测网络是否发生重排导致的丢包，并以此来更新 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 超时不管是时间等待代价，还是性能损耗代价都很大。

TCP的接收端收到一个报文段时，向发送端发送一个ACK来对其进行确认(也就是所谓的下一个期望数据的序号)。
通常TCP在接收到数据时并不立即发送ACK；相反，它推迟发送，以便将ACK与需要沿该方向发送的数据一起发送
（有时候称这种现象为数据捎带ACK），这就是经受时延的确认。但是在收到一个失序的报文段时，TCP需要立即
产生一个ACK(一个重复的ACK),这个重复的ACK不应该被延迟，目的在于让对方知道收到一个失序的报文段。这就是DupAck.
1
2
3
4

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

总结出现 dupack 不够的情况：

a. cwnd（拥塞窗口） 较小 ，导致网络中的流量小，从而发生dupack的概率小

b. 发送窗口里大量的数据包都被丢失了

c.在数据发送的尾端发生丢包时

但是，上面各种极端的 case 有共同的特点：

m. 无法产生足够的 dupack

n.没有新的数据包可以发送进入网络

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

3.4 伪超时与伪重传

在很多情况下，即使没有出现数据丢失也可能引发重传。这种不必要的重传称为伪重传，其主要造成原因是伪超时，即过早判定超时，其他因素如包失序、包重复，或 ACK 丢失也可能导致该现象。在实际 RTT 显著增长，超过当前 RTO 时，可能出现伪超时。在下层协议性能变化较大的环境中（如无线环境），这种情况出现得比较多。

TCP 为处理伪超时问题提出了许多方法。这些方法通常包含检测算法与响应算法。检测算法用于判断某个超时或基于计时器的重传是否真实，一旦认定出现伪超时则执行响应算法，用于撤销或减轻该超时带来的影响。 检测算法包含 DSACK 、Eifel 检测算法、迁移 RTO 恢复算法(F-RTO) 三种。

四 拥塞状态机

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

4.1 Open

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

4.2 Disorder(乱序)

当 sender 检测到 dupack 或者 SACK，将会转移到 Disorder 状态，当处在这个这个状态中时，cwnd 将维持不变。每收到一个 dupack 或 SACK，发送方将发送一个新包。也就是发现了网络中的数据包出现了乱寻，如果乱序没超过乱序容忍，系统认为只是出现了乱序，不会改变cwd大小。如果超过了容忍，那么就会转到cwr状态。

4.3 CWR(阻塞窗口减小状态)

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

4.4 Recovery

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

4.5 Lost

当超时（超过RTO）后，TCP sender进入Loss状态，所有在网络中的包被标记为lost，cwnd重置为1，通过slow start重新增加cwnd，Loss与Recovery状态的不同点在于，cwnd会重置为1，但是Recovery状态不会，它会降到之前的一半。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，而不是加倍。这样就可以避免拥塞窗口快速增长的问题。

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

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

5.3 快速重传算法

快速重传算法主要用于丢包检测，以便能更快重传数据包，更早的调整拥塞状态机状态，从而达到持续升窗的目的。（最早期的重传机制是根据每个数据包的定时器来实现的，只有当计时器超时时，才会出发超时重传，但是这个时间过长，降低了tcp的效率，所以才诞生了快速重传算法。超时重传的时候，ssthresh = cwd/2 , 而cwd = 1 开始）。

5.4 快速恢复算法

当检测到丢包时，TCP 会触发快速重传并进入降窗状态。该状态下 cwnd 会通过快速恢复算法降至一个合理值。（发生了重传说明有的包没有到达，有可能是网络阻塞，也有可能是单个包丢失，所以即使发送了重传也不能说明该包丢失，但是如果发生了超时重传那么就是丢包了，这时候基本是cwd=1）从历史发展来看，分为四个个阶段。

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)。

优点：在快速恢复期间，取消窗口陡降过程(也就是不在采用cwnd = cwnd/2+3)，可以更平滑的发送数据

缺点：降窗策略没有考虑 PIPE 的容量特征，考虑以下两点：

a.如果快速恢复没有完成，窗口将持续下降下去

b.如果一次性 ACK/SACK 了大量数据，in_flight 会陡然减少，窗口还是会陡降，这不符合算法预期。

也就是它的算法，严重以来了in_flight 变量，而这个变量也是不可控的

它“承若”不再陡降窗口，它将窗口缓慢降到原来的一半，然后在进入正常状态后再缓慢上升。
1

5.4.4 prr 算法 [RFC6937]

PRR 算法是最新 Linux 默认推荐的快速恢复算法。prr 算法是一种按比例降窗的算法，其最终效果是：

1.在快速恢复过程中，拥塞窗口非常平滑地向 ssthresh 收敛；

2.在快速恢复结束后，拥塞窗口处在 ssthresh 附近；

解决了什么问题：

1.不再仅仅halving，而是完全根据拥塞算法计算出的ssthresh，来将窗口逼近于它；
2.执行的过程不再受当前的in_flight控制，而是根据快速重传以来的发送/接收ACK的总数量来将窗口按照等比例的方式逼近ssthresh；
3.如果窗口降到了ssthresh以下(比如没有数据包可发送或大量包被标记LOST)，算法执行慢启动将其拉升到ssthresh附近；
4快速恢复阶段，最多“还”可以发送(或者说重传)多少数据，不再限定为1，而是取决于“当前收到的ACK/SACK总量，发出数据总量，窗口与ssthresh的关系”。

PRR 降窗算法实时监控以下的变量：

in_flight：它是窗口的一个度量，in_flight 的值任何时候都不能大于拥塞窗口的大小。（就是代表发送出去，但是没有ack的包，理解为在空中的意思）。

prr_delivered：本次收到 ACK 进入降窗函数的时候，一共被 ACK 或者 SACK 的数据段数量。它度量了本次从网络中清空了哪些数据段，从而影响 in_flight。

prr_out：进入快速恢复状态后已经被发送了多少数据包。在 transmit 例程和 retransmit 例程中递增。

to_be_out：当前还可以再发多少数据包。（可以根据滑动窗口获取）

降窗流程 根据上述原理可以得到 prr 算法降窗流程如下：

1.收到多次（默认为 3）重复 ACK，根据回调函数更新 ssthresh (reno 算法为 cwnd/2)，窗口维持不变;

2.每收到 ACK（不管是否重复），按上述算法计算 Extra; 3. 新窗口值取 cwnd = in_flight + Extra; 4. 直到退出快速恢复，cwnd = ssthresh;

优点：在快速恢复期间，取消了窗口陡降过程，可以更平滑发送数据，且降窗速率与 PIPE 容量相关。 缺点：不利于在拥塞恢复到正常时突发流量的发送。

5.5 计分板算法

记分板算法是为了统计网络中正在传输的包数量，即tcp_packets_in_flight。只有当 cwnd > tcp_packets_in_flight 时，TCP 才允许发送重传包或者新数据包到网络中。tcp_packets_in_flight和packets_out, sacked_out, retrans_out, lost_out有关。其中packets_out表示发出去的包数量，sacked_out为sack的包数量，retrans_out为重传的包数量，lost_out为loss的包数量，这里的loss包含rto,FR和RACK等机制判断出来的丢失包。

5.6 拥塞窗口校验

在 [RFC2861] 中，区分了 TCP 连接数据传输的三种状态：

• network-limited：TCP 的数据传输受限于拥塞窗口而不能发送更多的数据。
• application-limited：TCP 的数据传输速率受限于应用层的数据写入速率，并没有到达拥塞窗口上限。
• idle：发送端没有额外的数据等待发送，当数据发送间隔超过一个 RTO 的时候就认为是 ilde 态。

cwnd 代表了对网络拥塞状态的一个评估，拥塞控制要根据 ACK 来更新 cwnd 的前提条件是，当前的数据发送速率真实的反映了 cwnd 的状况，也就是说当前传输状态是 network-limited。假如 tcp 隔了很长时间没有发送数据包，即进入 idle，那么当前真实的网络拥塞状态很可能就会与 cwnd 反映的网络状况有差距。另外在 application-limited 的场景下，受限数据的 ACK 报文还可能把 cwnd 增长到一个异常大的值，显然是不合理的。基于上面提到的两个问题，[RFC2861]引入了拥塞窗口校验(CWV，Congestion Window Validation)算法。

算法如下：当需要发送新数据时，首先看距离上次发送操作是否超过一个 RTO，如果超过，则 1. 更新 sshthresh 值，设为 max(ssthresh, (3/4) * cwnd)。 2.每经过一个空闲 RTT 时间，cwnd 值减半，但不小于 1 SMSS。

对于应用受限阶段（非空闲阶段），执行相似的操作： 1. 已使用的窗口大小记为 Wused。 2. 更新 ssthresh 值，设为 max(ssthresh, (3/4) * cwnd)。

1. cwnd 设为 cwnd 和 Wused的平均值。

上述操作均减小了 cwnd，但 ssthresh 维护了 cwnd 的先前值。避免空闲阶段可能发生的大数据量注入，可以减轻对有限的路由缓存的压力，从而减少丢包情况的产生。注意 CWV 减小了 cwnd 值，但没有减小 ssthresh，因此采用这种算法的通常结果是，在长时间发送暂停后，发送方会进入慢启动阶段。Linux TCP 实现了 CWV 算法并默认启用。

六 常见的拥塞算法

6.1 New Reno 算法

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

6.2 CUBIC 算法

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

6.3 BBR 算法

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

bbr是反馈驱动的！bbr内置了自主的调速机制，不受TCP拥塞控制状态机的控制，bbr算法是自闭的，它可以自己完成VJ的所有状态探测以及切换，无需外界干涉，且对外界的干涉视而不见。
bbr周期性的试图探测是否有更多的带宽，如果有，那么就利用它，如果没有，就退回到之前的状态。
所以说，bbr的窗口调整是主动的。

    当你看到Reno/CUBIC和bbr的区别的时候，可能会想起中断和轮询的区别，bbr和轮询之间的不同点是，bbr有事实的反馈。


    好了，这就是Reno/CUBIC和bbr的区别，它们同样完成了”To find current bandwidth“，”To avoid congestion“以及”To probe more bandwidth“的逻辑，只是一个是事件驱动的被动实现，一个是反馈驱动的主动实现。和同事聊天时，在聊到高血压的时候，有一个很类似的事实：有一些人只有当觉得自己头晕的时候才会采取降血压的措施，另一些人则不断喝水并且少烟酒让自己血压维持在正常水平...
1
2
3
4

总结： 其实所有的拥塞算法要解决的都是找到最大带宽，然后尽量在最大带宽的条件下尽可能多和快的发送数据。

参考文献

万字解说tcp拥塞机制

TCP进入快速恢复时的窗口下降算法

TCP拥塞控制的问题？