图解丨TCP拥塞控制之基础
TCP要点有四，一曰有连接，二曰可靠传输，三曰数据按照到达，四曰端到端流量控制。注意，TCP被设计时只保证这四点，此时它虽然也有些问题，然而很简单，然而更大的问题很快呈现出来，使之不得不考虑和IP网络相关的东西，比如公平性，效率，因此增加了拥塞控制，这样TCP就成了现在这个样子。
为什么要进行拥塞控制
要回答这个问题，首先必须知道什么时候TCP会出现拥塞。TCP作为一个端到端的传输层协议，它并不关心连接双方在物理链路上会经过多少路由器交换机以及报文传输的路径和下一条，这是IP层该考虑的事。然而，在现实网络应用中，TCP连接的两端可能相隔千山万水，报文也需要由多个路由器交换机进行转发。交换设备的性能不是无限的!, 当多个入接口的报文都要从相同的出接口转发时，如果出接口转发速率达到极限，报文就会开始在交换设备的入接口缓存队列堆积。但这个队列长度也是有限的，当队列塞满后，后续输入的报文就只能被丢弃掉了。对于TCP的发送端来说，看到的就是发送超时丢包了。
如何进行拥塞控制
拥塞窗口 cwnd
首先需要明确的是，TCP是在发送端进行拥塞控制的。TCP为每条连接准备了一个记录拥塞窗口大小的变量cwnd1，它限制了本端TCP可以发送到网络中的最大报文数量2。显然，这个值越大，连接的吞吐量越高，但也更容易导致网络拥塞。所以，TCP的拥塞控制本质上就是根据丢包情况调整cwnd，使得传输的吞吐率尽可能地大！而不同的拥塞控制算法就是调整cwnd的方式不同！
注1: 本文中的cwnd以发送端的最大报文段长度SMSS为单位的 注2: 这个数量也受对端通告的窗口大小限制
linux 用户可以使用 ss --tcp --info 查看链接的cwnd值
拥塞控制算法
TCP从诞生至今，已经有了多种的拥塞控制算法，直到现在还有新的在被提出！其中TCP Tahoe(1988)和TCP Reno(1990)是最初的两个算法。虽然看上去年代很就远了，但 Reno算法直到现在还在广泛地使用。
- Tahoe 提出了1）慢启动，2）拥塞避免，3）快速重传
- Reno 在Tahoe的基础上增加了4）快速恢复
Tahoe算法的基本思想是
- 首选设置一个符合情理的初始窗口值
- 当没有出现丢包时，慢慢地增加窗口大小，逐渐逼近吞吐量的上界
- 当出现丢包时，快速地减小窗口大小，等待阻塞消除
相关视频推荐
LinuxC++后台服务器开发架构师免费学习地址：C/C++Linux服务器开发/后台架构师【零声教育】-学习视频教程-腾讯课堂
【文章福利】：小编整理了一些个人觉得比较好的学习书籍、视频资料共享在qun文件里面，有需要的可以自行添加哦！（需要视频资料后台私信“1”自取）
Tahoe 拥塞避免 (congestion-avoidance)
当我们在理解拥塞控制算法时，可以假想发送端是一下子将整个拥塞窗口大小的报文发送出去，然后等待回应。
Tahoe采用的是加性增乘性减(Additive Increase, Multiplicative Decrease, AIMD)方式来完成缓慢增加和快速减小拥塞窗口：
发送端发送整窗的数据：
- 如果没有丢包，则 cwnd = cwnd + 1
- 如果出现丢包了，则 cwnd = cwnd / 2
为什么丢包后是除以2呢, 这里的2实际上是一个折中值！用下面的例子来解释！
物理传输路径都会有延时，这个延时也让传输链路有了传输容量(transit capacity)这样一个概念，同时我们把交换设备的队列缓存称为队列容量(queue capacity).比如下面这样一个连接，传输容量是M,队列容量是N.
当cwnd小于M时，不会使用R的队列，此时不会有拥塞发生；当cwnd继续增大时，开始使用R的队列，此时实际上已经有阻塞了！但是A感知不到，因为没有丢包！ 当cwnd继续增大到M + N时，如果再增大cwnd，就会出现丢包。此时拥塞控制算法需要减小cwnd，那么减小到多少合适呢？ 当然是减少到不使用R的缓存，或者说使得cwnd = M，这样可以快速解除阻塞。
这是理想的情况！ 实际情况是A并不知道M和N有多大(或者说有什么关系)，它只知道当cwnd超过M + N时会出丢包！于是我们折中地假定M = N，所以当cwnd = 2N时是丢包的临界点，为了解除阻塞，让cwnd = cwnd / 2 = N就可以解除阻塞3！
所以，cwnd的变化趋势就像上面这样，图中上方的红色曲线表示出现丢包。这样的稳定状态也称为拥塞避免阶段(congestion-avoidance phase)
现实算法实现中，拥塞避免阶段的cwnd是在收到每个ACK时更新的：cwnd += 1/cwnd，如果认真算，会发现这比整窗更新cwnd += 1要稍微少一点！
注3：后面会提到，Tahoe在此时会将cwnd先设置为1，然后再迅速恢复到cwnd / 2
Tahoe 慢启动 (Slow Start)
Tahoe需要为选定一个cwnd初始值，但是发送端并不知道多大的cwnd才合适。所以只能从1开始4，如果这个时候就开始加性增，那就太慢了，比如假设一个连接会发送5050个MSS大小的报文，按照加性增加，需要100个RTT才能传输完成(1+2+3+...+100=5050)。因此，Tahoe和Reno使用一种称为慢启动的算法迅速提高cwnd。也就是只要没有丢包，每发送一个整窗的数据，cwnd = 2 X cwnd。换句话说，在慢启动阶段(slow-start phase)，当发送端每收到一个ACK时，就让cwnd = cwnd + 1
注4RFC 2581 已经允许cwnd的初始值最大为2, RFC 3390 已经允许cwnd的初始值最大为4, RFC 6928已经允许cwnd的初始值最大为10
那么，慢启动阶段何时停止？或者说什么时候进入前面的拥塞避免阶段 ? Tahoe算法定义了一个慢启动阈值(slow-start threshold)变量，在cwnd < ssthresh时，TCP处于慢启动阶段，在cwnd > ssthresh后，TCP处于拥塞避免阶段。
ssthreshold的初始值一个非常大的值。连接建立后cwnd以指数增加，直到出现丢包后， 慢启动阈值将被设置为 cwnd / 2。同时cwnd被设置为1,重新开始慢启动过程。这个过程如下图所示, 可以看到，慢启动可是一点也不慢。
Tahoe 快速重传 (Fast Retransmit)
现实的网络网络环境拓扑可能十分复杂，即使是同一个TCP连接的报文，也有可能由于诸如等价路由等因素被路由器转发到不同的路径，于是，在接收端就可能出现报文的乱序到达，甚至丢包！举个例子，发送端发送了数据DATA[1]、DATA[2]、……、DATA[8]，但由于某些因素，DATA[2]在传输过程中被丢了，接收端只收到另外7个报文，它会连续回复多次 ACK[1](请求发送端发送DATA[2])。这个时候，发送端还需要等待DATA[2]的回复超时(2个RTT)吗？
快速重传的策略是，不等了！挡发送端收到第3个重复的ACK[1]时(也就是第4个ACK[1])，它要马上重传DATA[2],然后进入慢启动阶段，设置ssthresh = cwnd / 2 , cwnd = 1.
如上图所示，其中cwnd的初始值为8，当发送端收到第3个重复的ACK[1]时，迅速进入慢启动阶段，之后当再收到ACK[1]时，由于cwnd = 1只有1，因此并不会发送新的报文
Reno 快速恢复(Fast Recovery)
在快速重传中，当出现报文乱序丢包后，拥塞窗口cwnd变为1，由于该限制，在丢失的数据包被应答之前，没有办法发送新的数据包。这样大大降低了网络的吞吐量。针对这个问题，TCP Reno在TCP Tahoe的基础上增加了快速恢复(Fast Recovery)。
快速恢复的策略是当收到第3个重复的ACK后，快速重传丢失的包，然后
- 设置 sshthresh = cwnd / 2
- 设置 cwnd = cwnd /2
还是以上面的例子为例
与快速重传中不同的是，发送端在收到第3个重复的ACK后，cwnd变为5，EFS设置为7
这里EFS表示发送端认为的正在向对端发送的包(Estimated FlightSize)，或者说正在链路上(in flight)的包。一般情况下，EFS是与cwnd相等的。但在快速恢复的时候，就不同了。假设拥塞避免阶段时cwnd = EFS = N，在启动快速恢复时，收到了3个重复的ACK，注意，这3个ACK是不会占用网络资源的(因为它们已经被对端收到了)，所以EFS = N - 3,而既然是出发了快速恢复，那么一定是有一个包没有到达，所以EFS = N - 4，然后，本端会快速重传一个报文，EFS = N - 3，这就是上面EFS设置为7的来源。
其他部分没什么好说的，发送端会在EFS < cwnd时发送信的数据，而同时，这又会使得EFS = cwnd
TCP New Reno
根据Reno的描述，TCP发送端会在收到3个重复的ACK时进行快速重传和快速恢复，但还有有一个问题，重复的ACK背后可能不仅仅是一个包丢了！如果是多个包丢了，即使发送端快速重传了丢失的第一个包，进入快速恢复，那么后面也会收到接收端发出的多个请求其他丢失的包的重复ACK！这个时候？发送端需要再累计到3个重复的ACK才能重传！
问题出在哪里？发送端不能重收到的重复ACK中获得更多的丢包信息！它只知道第一个被丢弃的报文，后面还有多少被丢弃了？完全不知道！也许使用SACK(参考RFC6675)这就不是问题，但这需要两端都支持SACK。对于不支持SACK的场景，TCP需要更灵活！
RFC6582中描述的New Reno算法，在Reno中的基础上，引入了一个新的变量recover,当进入快速恢复状态时(收到3个重复的ACK[a])，将recover设置为已经发送的最后的报文的序号。如果之后收到的新的ACK[b]序号b不超过recover，就说明这还是一个丢包引起的ACK ！这种ACK在标准中也称之为部分应答(partial acknowledgments), 这时发送端就不等了，立即重传丢失的报文。
编辑
TCP在发送报文后，如果没有收到对端应答，那么在重传定时器超时后会触发重传，超时时间遵循二进制退避原则，也就是{1,2,4,8,16}这样成倍地扩大超时时间。退避是因为TCP认为丢包意味着网络有拥塞，为了不加重网络的拥塞，TCP选择等待更长的时间再进行重传。这和CSMA/CD中的二进制退避算法如出一辙。
网络中的网络设备(路由器、交换机)在收到了超过队列限制的报文后，后续的报文会被丢弃。从TCP采用的二进制退避算来看，TCP绝对算得上是网络里的谦谦君子了，它信守的规则是：既然已经堵了，我就等一会儿再发，如果还堵，我就再多等翻倍的时间！
对整个网络来说，这的确是减轻负担的好办法。要知道，在发送窗口已满的情况下，指数退避一次，意味着单位时间内发送的报文变成了原来的1/2,再退避一次，就只有原来的1/4！就像是汽车限号出行，单双号限行不好用，我就规定一辆车只能在4天中开1天...
But, TCP真的需要如此克制自己吗？，换个说法，为什么TCP一定要x2退避？难道重传定时器超时时间不能线性增大(每次增加X秒)，或者乘以一个更小的系数(比如x1.5) ？ 我们可以从CSMA/CD找到灵感。
CSMA/CD使用x2的原因很好理解，共享介质中的每个节点并不知道其他还有多少节点，使用x2退避就是利用二分法快速找到让整个系统稳定运行的时隙分配方案！
举个例子，假设系统中有4个节点发包速率相同，那么最终的稳定分配方案自然就是将一段时间分为4份，每个节点占用1个时隙。如果此时又加入4个相同的节点。那么显然，所有的8个节点都会发包冲突。如何才能不冲突呢？当然是分配给每个节点的时间再减小一半！当然这里举的例子节点都是2的整数幂。如果不是呢？此时2进制退避依然能很快地达到稳定，也许这个时候的时隙分配方案不是最合理的，但是正如前面说的，每个节点并不知道其他还有多少节点，对单个节点来说，二进制退避是最快速找到让每个节点都正常工作的方案！
编辑
二进制退避方案中隐含了对公平性的考虑，它是站在整个网络的角度，而不是其中某一台主机！
但对一台特定的主机，不遵守这个退避规则显然好处更多...比如使用固定的重传定时器时间。在这种网络中，没有拥塞时大家相安无事，一旦出现了拥塞，那么不退避的主机理论上就能发出更多的报文！
编辑
当然，这似乎牺牲了其他遵守规则主机的利益，它们的重传次数会增加。那么，如果大家都不遵守呢？结果就是大家的重传次数都增加了，拥塞甚至比大家都遵守还要糟糕，因为网络上的设备丢的包更多了！
这就有点囚徒困境的味道了，如果别人退避你不退避，你能获利，如果别人比退避而你退避，那么你就吃亏了，如果大家都不遵守，那么比都遵守还要糟糕......
当然，现实中的网络并不同于CSMA/CD中的共享介质，一个简单的区别就是，在CSMA/CD中，如果一个节点监听到信道繁忙，它是不是发送数据的，它需要等待；而在网络中，并不存在这样的共享介质，并且路由器是又缓冲队列的，因此两个主机还是可以都发送报文。
话虽如此，很多游戏为了保证实时性不会选择TCP ！毕竟，TCP太无私了，它是为了整个网络考虑的。而实时游戏需要的是什么！快速！那么如果它们有需要可靠传输怎么办？ 很简单，使用UDP，然后在用户态自己做ARQ就好了，想怎么折腾怎么折腾，比如KCP就是这么个东西。
