TCP之拥塞窗口
- 滑动窗口(在我们的上一篇文章中有讲)，接收方通过通告发送方自己的可以接受缓冲区大小（这个字段越大说明网络吞吐量越高），从而控制发送方的发送速度。
- 拥塞窗口，也就是本文要讲的。
概念
一个连接的TCP双端只是网络最边缘的两台主机，他们不知道整个网络是如何工作的，因此他们不知道彼此之间的有效吞吐量。因此，他们必须找到一种方法来确定它。我们称之为拥塞窗口 (CWND)。这是在我们必须停止并等待确认之前可以发送的字节数。
拥塞窗口是决定任何时候可以发出的字节数的因素之一。拥塞窗口由发送方维护，是阻止发送方和接收方之间的链路因流量过多而过载的一种手段。这不应与发送方维护的滑动窗口相混淆，滑动窗口的存在是为了防止接收方过载。拥塞窗口是通过估计链路上有多少拥塞来计算的。
拥塞窗口对于设备来说是本地的，并且永远不会在连接上共享，这与在每个段中发送的接收器窗口不同。在任何给定时间，设备最多可以发送由接收器窗口和拥塞窗口之间的最小值指定的字节数，如下面的公式所示：
transmittable bytes = min(cwnd, rwnd)
这意味着如果拥塞窗口小于接收窗口，则设备可以在等待确认之前传输多达拥塞窗口中定义的字节数。相反，如果接收窗口小于拥塞窗口，则设备可以在等待确认之前最多传输接收器窗口中定义的字节数。
拥塞窗口根据网络拥塞动态变化。每次未确认段时，都假定是由于网络拥塞。拥塞窗口随时间演变的方式被定义为一个算法，这取决于实现。我们现在将介绍最常见的一种。该算法遵循以下规则：
- 拥塞窗口从一个段的大小开始（大约 1KB）
- 定义了一个拥塞窗口阈值（ssthresh）
- 如果收到确认，并且当前拥塞窗口大小小于 ssthresh，则拥塞窗口加倍
- 如果收到确认，但拥塞窗口大于或等于 sshthresh，则拥塞窗口增加其初始值（例如 1KB）
- 如果一个段没有被确认从而触发重传，拥塞窗口就会减半并且 ssthresh 被放置在这个值
- 拥塞窗口不能大于接收器窗口
该规则中包括我们经常听过的几种算法：
- 慢启动(slow-start)
- 拥塞避免(congestion avoidance)
- 快速重传(fast retransmit)
- 快速恢复(fast recovery)
算法
通过下面的图片，可以方便大家更加快速的理解拥塞窗口的算法机制。
慢启动
当主机开始发送数据时，如果立即将大量数据字节注入到网络，那么就有可能引起网络拥塞，因为现在并不清楚网络的负荷情况。因此，较好的方法是先探测一下，即由小到大逐渐增大发送窗口，也就是说，由小到大逐渐增大拥塞窗口数值。通常在刚刚开始发送报文段时，先把拥塞窗口 cwnd 设置为一个最大报文段MSS的数值。而在每收到一个对新的报文段的确认后，把拥塞窗口增加至多一个MSS的数值。用这样的方法逐步增大发送方的拥塞窗口 cwnd ，可以使分组注入到网络的速率更加合理。
每经过一个传输轮次，拥塞窗口 cwnd 就加倍。一个传输轮次所经历的时间其实就是往返时间RTT。不过“传输轮次”更加强调：把拥塞窗口cwnd所允许发送的报文段都连续发送出去，并收到了对已发送的最后一个字节的确认。
另，慢开始的“慢”并不是指cwnd的增长速率慢，而是指在TCP开始发送报文段时先设置cwnd=1，使得发送方在开始时只发送一个报文段（目的是试探一下网络的拥塞情况），然后再逐渐增大cwnd。
下面，我们从示例图着手，来分析慢启动的过程。
- 在协商连接时，两个设备交换它们的接收器窗口(在这种情况下它们都有 32KB)
- 双端都以 1KB 的拥塞窗口开始，但由于在该示例中客户端将是唯一发送数据的客户端，因此它将是唯一一个显着使用此值的客户端。
- 在第 2 行，客户端收到一个 ACK并将其 CWND 加倍(现在是 2k)
- 服务器在第 3 行收到一个ACK时也做同样的事情
- 客户端发送两段 1k 的数据，它们稍后在第 6 行和第 7 行确认，其中客户端上的拥塞窗口加倍（4k，然后是 8k）
- 然后，客户端再次发送 1k 数据并立即得到确认，有效地再次将拥塞窗口加倍（现在第 9 行为 16k）。
- 这在第 10-11 行重复，其中 CWND 达到 32k。
- 此时，除非接收端窗口也增长，否则拥塞窗口不能再增长。
慢启动的整个过程如下：
- 初始化 cwnd = 1
- 经过1个RTT,即收到一个ACK，cwnd = 2^(1) = 2
- 经过2个RTT, cwnd = 2^(2) = 4
- 经过3个 RTT, cwnd = 2^(3) = 8
拥塞避免
让拥塞窗口cwnd缓慢地增大，即每经过一个往返时间RTT就把发送方的拥塞窗口cwnd加1，而不是加倍。这样拥塞窗口cwnd按线性规律缓慢增长，比慢开始算法的拥塞窗口增长速率缓慢得多。
无论在慢启动阶段还是在拥塞避免阶段，只要发送方判断网络出现拥塞（其根据就是没有收到确认），就要把慢启动ssthresh设置为出现拥塞时的发送方窗口值的一半（但不能小于2）。然后把拥塞窗口cwnd重新设置为1，执行慢开始算法。这样做的目的就是要迅速减少主机发送到网络中的分组数，使得发生 拥塞的路由器有足够时间把队列中积压的分组处理完毕。
“拥塞避免”并非指完全能够避免了拥塞。利用以上的措施要完全避免网络拥塞还是不可能的。“拥塞避免”是说在拥塞避免阶段将拥塞窗口控制为按线性规律增长，使网络比较不容易出现拥塞
- cwnd = i
- 经过 1 RTT, cwnd = i+1
- 2 RTT, cwnd = i+2
- 3 RTT, cwnd = i+3
快速重传
TCP 有一个快速传输特性——在它的计时器到期之前重新传输丢失的段。为了允许快速传输，我们需要为发送方和接收方设置一些规则。
- 作为接收者，它应该始终发送它期望接收的序列号。例如，当接收方接收到第 1 段时，它以 ACK2 响应，
- 作为发送方，它应该忽略定时器并在收到 3 个重复的ACK 后立即开始重传丢失的段。
用一句话概况，就是发送端在收到3个重复无序的ACK时候，它假定数据包丢失并重传该数据包，而无需等待重传计时器到期。
而在此时，拥塞窗口的变化过程如下：
- ssthresh设置为拥塞窗口的1/2
- 拥塞窗口大小设置为ssthresh
- 重新进入拥塞避免阶段
快速恢复
- 当收到第3个重复的ACK时，将ssthresh设置为当前拥塞窗口cwnd的一半。重传丢失的报文段。设置cwnd为ssthresh加上3倍的报文段大小。
- 每次收到另一个重复的ACK时，cwnd增加1个报文段大小并发送1个分组（如果新的cwnd允许发送）。
- 当下一个确认新数据的ACK到达时，设置cwnd为ssthresh（在第1步中设置的值）。这个ACK应该是在进行重传后的一个往返时间内对步骤1中重传的确认。另外，这个ACK也应该是对丢失的分组和收到的第1个重复的ACK之间的所有中间报文段的确认。这一步采用的是拥塞避免，因为当分组丢失时我们将当前的速率减半。
算法
快速重传和快速恢复的目的是：快速恢复丢失的数据包。如果没有快速重传和快速恢复这俩算法，那么tcp可能
Tahoe
Tahoe算法是TCP的早期版本。除了具备TCP的基本架构和功能外，引入了慢启动、拥塞避免以及快速重传机制。在该算法中，快速重传机制策略如下：
- ssthresh设置为拥塞窗口的1/2
- 拥塞窗口大小设置为1
- 重新进入慢启动阶段
Reno
Reno与Tahoe相比，增加了快速恢复阶段，也就是说，完成快速重传后，进入了拥塞避免阶段而不是慢 启动阶段。Reno 在快速重传阶段，重新发送数据之后：
- ssthresh设置为拥塞窗口的1/2
- 拥塞窗口设置为之前的1/2
- 进入快速恢复阶段
- 在快速恢复阶段，每收到重复的ACK，则cwnd加1；收到非重复ACK时，置cwnd = ssthresh，转入拥塞避免阶段；
- 如果发生超时重传，则置ssthresh为当前cwnd的一半，cwnd = 1，重新进入慢启动阶段。
Reno快速恢复阶段退出条件：收到非重复ACK。
NewReno
在Reno版本中，若同时有多个数据包丢失，则大部分必须等到TimeOut之后，才进行重传。这是因为在Reno中，同时有多个数据包丢失时，只要收到部分丢失数据的ACK，便退出快速恢复。而之所以能收到部分丢失数据的ACK，这是因为在快速重传阶段，只重新发送了部分丢失的数据。而在Reno结束快速恢复，进入拥塞避免阶段之后，对于其他未重新发送的数据包来说，常常没有足够的重复ACK来触发快速重传机制。只好等等TimeOut，而TimeOut对于TCP性能有非常大的影响，在等待TimeOut这段时间，无法发送新的数据包，而在TimeOut之后，CWND被重新设置为1。
基于上述原因，NewReno优化了该机制，NewReno在收到部分丢失数据的ACK后，并不会退出快速恢复阶段，而是等待所有丢失的包都重新发送之后，才退出快速恢复阶段。这就使得NewReno在遇到多个数据包同时丢失时，不需要等待TimeOut，便可重新发送所有丢失的数据包，进而减小TimeOut对性能的影响。
SACK
除了NewReno的方法之外，要解决大量数据包丢失的问题，还有一个解决方案，就是让发送端知道，哪些数据包已经送达，哪些数据包已经丢失。SACK修改在接收端发送重复的ACK时，同时在ACK中携带连续的已经收到的数据序列号范围，而连续数据序号范围与连续数据序号范围之间的间隔就是已经丢失的数据。
滑动窗口与拥塞窗口
共同点：提高网络性能。
不同点：
- 流量控制：在TCP连接上实现对发送流量的控制，考虑点对点之间对通信量的控制，端到端，即：控制发送端的数据发送速率，使接收端可以来得及接收，保证网络高效稳定运行。
- 拥塞控制：处理网络拥塞现象，考虑网络能够承受现有的网络负荷，全局性变量，涉及所有的路由器、主机以及与降低网络传输性能有关的因素。防止过多的数据注入到网络，使网络中的路由器或链路不致过载，确保通信子网可以有效为主机传递分组。
Q&A
1、在一个窗口内重复丢包会造成影响吗？会。如果只丢一个包，那么收到非重复ACK时，就能确认完本窗口内所有的包。然后进入拥塞 避免阶段。这就是Reno想达到的。而如果丢失多个包，那么收到非重复ACK时，不能确认完本窗口内所有的包。但是，也会退出快速恢复， 进入拥塞避免阶段。
这个时候可能会发生两种情况：
- 多次进行快速重传和快速恢复。又发现丢包，再次进入快速重传和快速恢复。注意，每次进入快速重传和快速恢复时，ssthresh和CWND都要减半。多次丢包最终会导致ssthresh指数减小。通过画cwnd(t)图可以发现，不仅这段时间吞吐量非常低，而且导致恢复完后拥塞避免的起点非常低，从而导致之后的吞吐量也很低。
- 经过多次快速重传和快速恢复，接着发生传输超时。
2、为什么发生拥塞时，还增加cwnd？
在检测到丢包时，窗口为CWND。这时候网络中最多有cwnd个包(传输中 < CWND)。每当收到一个重复的ACK，则说明有数据包离开网络，达到接收端了。那么，此时网络中还可以再容纳1个包。由于发送端滑动窗口不能移动了，所以如果想保持继续保持固定个数的传输数据包，可以使CWND + 1。这样一来，可以提高吞吐量。而实际上，在fast recovery期间发送的新数据包比起发生丢包的CWND来说，已经是大大减少了。
END