什么是网络拥塞？

当 TCP 数据包经由网络中的路由器传输的时候，如果路由器的收包速度大于处理速度，路由器一般会先把收到的数据包缓存起来等待后续处理。但是当网络传输速度过大时，则会导致路由器的缓存空间全部被占用从而只能丢弃一部分数据包，如果一个路由器或者交换机等网络节点由于性能或者带宽等因素的限制而不能及时处理这些业务数据的时候，就会强制丢包，这种场景就叫做 拥塞(congestion) 。

当负载超过Cliff之后，吞吐量就急剧下降，延迟相应急剧上升。Cliff点也就是网络的最大负载，一旦超过网络的整体性能就大打折扣

拥塞控制和流量控制的关系？

  1. 流量控制是点对点通信量的控制，是端到端的问题。流量控制所要做的就是抑制发送端发送数据的速率，以便使接收端来得及接收；拥塞控制是防止过多的数据注入到网络中，这样可以使网络中的路由器或链路不致过载。拥塞控制是一个全局性的过程，关注到传输链路上所有的主机、路由器，以及与降低网络传输性能有关的所有因素。
  2. 流量控制是以显式的方式在TCP头中通过 Window size 字段通告发送方，流量控制关注的是接收端和发送端；拥塞控制大多是通过隐式的方式控制发送端速率，接收端依据特定的收发包情况来推测网络拥塞状况 。

简单而言，流量控制考虑的是接收方的接收能力，拥塞控制考虑的是网络的传输能力 。网络拥塞本来应该由 IP 协议负责，但因为 IP 是一个不可靠且简单的协议，所以此责任不得不落于 TCP 身上。

具体而言，如果网络上的延时突然增加，那么，TCP 流量控制只重传数据，但是，重传会导致网络的负担更重，于是会导致更大的延迟以及更多的丢包，于是，这个情况就会进入恶性循环被不断地放大，最终导致整个网络的崩溃。

对应流量控制中的 rwnd ，TCP 会维护一个 cwnd 变量来控制拥塞窗口的大小。发送端实际可用的窗口大小 W = min(rwnd, cwnd) （不过为了方便描述，cwnd 通常指 MSS 大小的包的个数）

。已经发送但还没有被 ACK 确认的数据量叫做 flight size ，拥塞控制限制发送速率的方式就是让 flight size<=W ，另外有两点需要注意：

  1. 在没有使用 SACK 时，flight size 就是当前已经发送数据包的最大 seq 减去当前接收到的最大 ACK Number。

  2. 在使用 SACK 时，flight size 还需要扣除被 SACK 反馈的数据包。

W 的合理值应该接近网络的 带宽延迟积 。

数据包守恒原则： 在一个运行平稳的 TCP 连接中流动的数据包应该是守恒的，意思是当只有旧的数据包被成功传输到对端后，新的数据包才能加入到连接中。传输中的包称为 in_flight ，进行拥塞控制的时候，如果 in_flight>=cwnd 的，就表示拥塞窗口不允许在额外发送数据包了。

TCP 拥塞控制主要包含下面四个算法：慢启动，拥塞避免，快速恢复，快速重传 。

慢启动

一个 TCP 连接启动的时候并不知道 cwnd 应该取多大的值适合当前的网络状况，因此 TCP 发送方会从一个较小的初始值指数抬升 cwnd 到某一个值，这个 cwnd抬升的过程就叫做慢启动。慢启动算法如下：

  • 连接建立完成后，一开始初始化 cwnd = 1，表示可以传一个 MSS 大小的数据。
  • 当收到一个 ACK 确认应答后，cwnd 增加 1，于是一次能够发送 2 个
  • 当收到 2 个的 ACK 确认应答后， cwnd 增加 2，于是就可以比之前多发2 个，所以这一次能够发送 4 个
  • 当这 4 个的 ACK 确认到来的时候，每个确认 cwnd 增加 1， 4 个确认 cwnd 增加 4，于是就可以比之前多发 4 个，所以这一次能够发送 8 个。
慢启动算法
  • 注意，是 每个 ACK 都会使 cwnd 翻倍，而不是每一批 ACK（拥塞避免采用）。可见，慢启动会进行指数增长，cwnd 短时间内迅速增大，为防止其过大，还需要引入 慢启动阈值(ssthresh) ，一旦达到阈值，便进入 拥塞避免 。
  • 如果延迟确认，则也会进行指数增长，不过是 1.5 的幂。
  • Linux 3.0后把 cwnd 初始化成了 10个 MSS。

拥塞避免

当拥塞窗口 cwnd 「超过」慢启动门限 ssthresh 就会进入拥塞避免算法。一般来说 ssthresh 的大小是 65535 字节。

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

拥塞避免

显然，慢启动是指数增加算法，而拥塞避免是线性增加算法，两种方法合起来常称为 AIMD算法（加法增大乘法减少）。这样就可以避免增长过快导致网络拥塞，慢慢的增加调整到网络的最佳值。

拥塞处理

拥塞窗口增大的过程中，也随时有可能发生拥塞。TCP 中，一般使用两种事件作为拥塞发生的标志：1）超时重传 ；2）收到三次重复 ACK ；收到三次重复 ACK 情况下的拥塞程度低于超时重传，因为当发送方收到三次重复 ACK 时，说明一个段发生了丢失或延迟，但三个段已经被接收，说明网络拥堵有所恢复。

TCP 如下处理这两种拥塞情况：

  1. RTO超时：
    • sshthresh = cwnd /2
    • cwnd 重置为 1
    • 进入慢启动过程
  2. 收到三次重复 ACK（TCP Reno）：
    • cwnd = cwnd /2
    • sshthresh = cwnd
    • 进入快速恢复算法

快速恢复

快速恢复和快速重传一般同时使用。快速恢复算法如下：

  • cwnd = sshthresh + 3 * MSS （3的意思是确认有3个数据包被收到了）
  • 重传 Duplicated ACK 指定的数据包
  • 如果再收到 duplicated Acks，那么 cwnd = cwnd +1
  • 如果收到了新的 ACK，那么，cwnd = sshthresh ，然后就进入拥塞避免的算法。
Reno 快速恢复

cwnd=ssthresh+3，为什么加3？

因为既然发送方收到三个重复的确认，就表明有三个分组已经离开了网络。这三个分组不再消耗网络资源而是停留在接收方的缓存中。可见现在网络中并不是堆积了分组而是减少了三个分组。因此可以适当把拥塞窗口扩大些。后续收到冗余 ACK 仍增加的原因同理。

然而上面这个算法也存在问题，那就是——它依赖于 3 个重复的 ACK 。注意，3 个重复的 ACK 并不代表只丢了一个数据包，很有可能是丢了好多包。但这个算法只会重传一个，而剩下的那些包只能等到 RTO 超时，于是，进入了恶梦模式——超时一个窗口就减半一下，多个超时会超成TCP的传输速度呈级数下降，而且也不会触发 Fast Recovery 算法了。SACK 或 D-SACK 的方法虽然可以让 Fast Recovery 在做决定时更聪明一些，但是并不是所有的 TCP 的实现都支持SACK（SACK需要两端都支持），所以，需要一个没有SACK的解决方案。New Reno 对此做出了改进。

New Reno下的快速恢复：

  • 当发送方这边收到了3个 Duplicated ACK，进入快速重传模式，重传冗余 ACK 指示的那个包。如果只有这一个包丢了，那么，重传这个包后回来的 ACK 可以确认所有已经被发送方传输出去的数据。如果没有的话，说明有多个包丢了。我们叫这个 ACK 为 Partial ACK。
  • 一旦发送方这边发现了 Partial ACK 出现，那么，发送方就可以推理出来有多个包被丢了，于是乎继续重传窗口内未被确认的第一个包。直到再也收不到 Partial Ack，才真正结束快速恢复这个过程。

另一种带有 SACK 的快速恢复是 FACK 算法，自行了解，我也不懂。

参考：拥塞算法，TCP概述，小林coding，拥塞简介，《计算机网络自顶向下》