Linux|TCP可靠传输-拥塞控制 Linux|linux

拥塞控制原理看到拥塞这个词，我们首先会想到什么呢？
在生活中，我们几乎每天都能听到早高峰、晚高峰引起的交通堵塞。那么引起堵塞的原因是什么呢？你肯定会说是这个时间段车流量过大，超出道路所能承受的车流量范围了。这是完全正确的，这里道路是一种资源，所有的车都需要这个资源，当需求大于可用资源时，自然就会引起堵塞。
那么在网络中我们提到的拥塞也就是这个意思。网络中对拥塞的定义是：在某段时间内，若对网络中某一资源的需求超过了该资源所能提供的可用部分，网络的性能下降了。这种情况就叫拥塞。
这是很好理解的，条件关系式如下：

文章图片
对资源的需求>可用资源

对于上述问题，我们首先想到的解决办法是：把节点缓存的存储空间增大，或者把链路更换为更好速率的链路不就好了。其实不然，因为网络拥塞是很复杂的问题，简单的采用上述方法，在很多情况下还可能起到相反的效果。
还是道路堵塞的例子：假入从商业区回到居住区总共有三条道路，每天有早上和晚上有非常多的车辆需要通过，必然会引起堵塞，假设此时拓宽道路，给予每辆车一个车道，成功解决了堵塞的问题，但是现在又有一个问题，这些车道总会交汇处呀，当所有的车辆都到这个交汇口的时候，是不是又是一场大堵塞，所以，这不是解决问题的有效方法。
网络拥塞也是这样：当某个节点的容量太小时，到达该节点的分组因无存储空间暂存而不得不被丢弃。现在设想将节点缓存的容量扩到非常大，于是凡到达该节点的分组均可在节点的缓存队列中排队，不受任何限制。由于输出链路的容量的处理机的速度并未提高，因此在这队列中的绝大多数分组的排队时间将会大大增加，等到超时时间到达时，上层软件只好把他们进行重传。由此可见，简单的扩大缓存的存储空间会造成网络资源的严重浪费，因而解决不了网络拥塞的问题。
综上所述，我们想到的都是只解决了局部问题，而局部问题的修改又会影响到其它方面，即牵一发而动全身。再者。拥塞常常趋于恶化，如果一个路由器没有足够的空间，它会丢弃一些新到的分组，但当分组被丢弃时，发送这一分组的源点就会重传这一分组，甚至可能还要重传多次。这样会引起更多的分组流入网络和被网络中的路由器丢弃。可见拥塞引起的重传并不会缓解网络的拥塞，反而可能会加剧拥塞。所以，拥塞控制是必须的(车辆限号是必须的)

拥塞控制就是防止过多的数据注入到网络中，这样可以是网络中的路由器或链路不致过载。拥塞控制的前提是网络能够承受现有的网络负荷。
拥塞控制是一个全局性的过程，涉及到所有的主机、所有的路由器，以及降低与网络传输性能有关的所有因素。
TCP的拥塞控制方法 TCP进行拥塞控制的算法有四种，即慢开始、拥塞避免、快重传和快恢复，这四种方法其实都是相互配合的，不是单独的解决问题
慢开始
这里所讨论的拥塞控制也叫做基于窗口的拥塞控制。为此，发送方维持一个叫做拥塞窗口的状态变量(即网络中能流畅传输的数据量)，拥塞窗口的大小取决于网络的拥塞程度，并且动态的在变化。发送方让自己的发送窗口等于拥塞窗口。(就跟行车一样，地图会告诉你当前道路的拥塞程度，并且它是动态变化的)
发送方控制发送窗口的原则是：只要网络没有出现拥塞，拥塞窗口就可以再增大一些，以便把更多的分组发送出去，这样就可以提高网络的利用率，但只要网络出现拥塞或有可能出现拥塞，就必须把拥塞窗口减小一些，以减少注入到网络中的分组数，缓解网络拥塞。
那么发送方又如何知道网络发送了拥塞呢？
TCP规定，判断网络拥塞的依据就是出现了超时。
那么拥塞窗口的大小如何变化呢？

对于满算法来说：当主机开始发送数据时，由于并不清楚网络的负荷情况，所以如果立即把大量数据字节注入到网络中，那么就有可能出现拥塞。所以较好的方法是由小到大慢慢增大发送窗口。
旧规定是先将拥塞窗口设置为1到2个发送方的最大报文段SMSS(sender MSS)的数值，新规定把拥塞窗口设置为2到4个SMSS的数值。具体规定如下：
若SMSS>2190字节，则拥塞窗口的大小不得超过两个报文段；
若SMSS>1095字节且SMSS<=2190字节，则拥塞窗口的大小不得超过3个报文段；
若SMSS<=1095字节，则拥塞窗口的大小不得超过4个报文段；
慢开始规定，在每收到一个队新的报文段的确认后，可以把拥塞窗口增加最多一个最长报文段(SMSS),即：
拥塞窗口(cwnd)每次的增加量=min(N,SMSS)
其中N是原先未被确认的、但现在被刚收到的确认报文段所确认的字节数

举例：一开始先设置cwnd=1，发送方发送第一个报文段M1，接收方确认M1。cwnd由1增大2，发送方接着发送M2和M3两个报文段、接收方再发送两个确认，接着cwnd由2增大到4。因此，每一次确认时候，拥塞窗口都会增加一倍，如图：

文章图片

注意：这里是为了方便理解网络拥塞，将传输单位设置以报文段为单位，并非字节,所以这里不是对很多报文段进行一次确认，而是对每个报文段都进行确认(在报文段内部，仍然遵从滑动窗口的原则)
这里我们将每一轮往返叫做一个轮次，轮次的往返时间RTT是将本轮里边的所有报文段从发送出去到收到确认总共所经历的时间，不是单个报文段。另外，在实际运行中，轮次的划分并不是图解那样，发送方只要收到一个队新报文段的确认，其拥塞窗口就立即加1，并且立即发送新的报文段，而不需要等待这个轮次中所有确认都收到之后才发送新的报文段。
在介绍其它方法之前，在这里新引入一个新概念：慢开始门限(ssthresh)，即：当拥塞窗口大到哪个程度时，会采取处理措施。用法如下:

当cwnd 当cwnd>ssthresh时，停止使用慢开始算法而改用拥塞避免算法。
当cwnd=ssthresh时，既可以使用慢开始算法，也可以使用拥塞避免算法

拥塞避免和快重传和快恢复
在慢开始方法中，cwnd的增加是成倍增加的，这就可能因为增长过大而引起网络拥塞，而避免用塞算法就是为了避免这种情况产生。它的思路是这样：在cwnd大于某一个界定值后(后续讲解)，之后每一轮次结束后，我们只将cwnd加1，而不是成倍增加。
现在用一个具体例子来说明cwnd是怎样变化的？
我们还是以报文段为单位，假定发送窗口等于拥塞窗口。
我们将慢开始门限的初始值设置为16个报文段，即ssthresh=16。现在开始执行慢算法，如图：

文章图片

根据ssthresh算法规定，现在达到了达到了设置的门限值，需要使用拥塞避免算法，如图：

文章图片

假如当拥塞窗口为24时，网络出现了超时，发送方判断为网络拥塞，于是调整门限值ssthresh=cwnd/2,即12,同时重启慢开始算法，设置cwnd为1，当拥塞窗口再达到十二时，再执行拥塞避免算法(和前面过程一样)，如图：

文章图片

解释：有时，个别报文段会在网络中丢失，发送方迟迟收不到确认，就会产生超时，但是实际上网络并未发生拥塞，而TCP对网络拥塞的依据就是超时。这个时候就会错误的开启慢开始算法，直接将拥塞窗口将为1，大大降低了传输效率。
为了避免这个情况的发生，有了快重传算法，它的算法思想是：要让发送方尽快知到发生了个别报文段的丢失。

快重传算法规定：接收方不要等待自己发送数据时捎带确认，而是要立即发送确认信息(捎带确认指的是确认信息数据很少但是TCP头部和IP首部就占40字节，效率低下，解决办法是当接受端要发送数据时捎带这个确认信息)，即使收到了失序的报文段也要立即发送出已收到的报文段的重复确认。

现在假设cwnd=4，接受方收到了报文段M1和M2,并且及时的发出了确认信息，此时M3报文段丢失了，但是M4报文段却收到了。按照原来的办法，此时接收方什么都不做，静静等待发送方的超时重传就可以了，但是之前说了，我们为了避免重启慢开始算法，降低传输效率，这里不能等到超时，所以此时接收方必须立即发送对M2的重复确认(为什么要发M2的确认呢？之前讲过，发送的确认序号代表的是这个序号之前的数据我已经全部接收到了，这是我期望下次接收的数据起始序号)，发送方收到了对M2的重复确认时，就会怀疑M3报文段是不是没有收到，，因为收到了两次确认信息，这是接受端接着发送M5和M6，接收方收到M5和M6之后，再分别发送对M2的确认信息。这个时候接受端已经收到了四次对M2的确认，其中三次是重复确认。快重传规定，只要发送方收到三个连续的重复确认，就知道接收方确认没有收到M3报文段，此时立即进行快重传。从而避免超时的情况。如图：

文章图片

在执行快重传之后，我得使用快恢复算法进行恢复，快恢复指的是根据当前网络情况重新调整ssthresh，一般是将ssthresh调整为cwnd的一般，同时设置拥塞窗口等于门限值，并开始执行拥塞避免算法。如图：

文章图片

【Linux|TCP可靠传输-拥塞控制】注意：有些快恢复算法是将拥塞窗口设置的比原来大一点，增大三个MSS的长度。

理由：既然发送方收到了3个重复的确认，就表明有三个分组已经离开了网络。这三个分组不再消耗网络的资源而是停留在接收方的缓存中，可见在网络中是减少了三个分组而不是堆积了三个分组，因此可以增大一些。

最后需要说明的是：我们所说的AIMD算法指的是加法增大AI，指的是拥塞避免算法因为它是线性增大的。而一旦收到了3个重复的确认，就改门限值为拥塞窗口的一般，称为乘法减小MD。
整体流程图如下：

文章图片

由此我们可以得出，发送方的发送窗口的大小取决于接收方窗口(rwnd)和拥塞窗口(cwnd)的联合限制，它的上限值是这两个值中较小的一个，即：

文章图片

主动队列管理AQM 在前面的叙述中，我们所说的超时都是基于传输层的考虑，那么在网络层会不会也出现这样的问题呢？答案是会的
路由器的队列通常都是按先进先出(FIFO)的规则处理到来的分组。但是队列总是有限的，当队列已经满时，以后再到达的分组将会被丢弃，这叫做尾部丢弃策略，但是，路由器这种做法是非常不厚道的，你倒是一丢弃轻松了，但是你给通信双方造成了非常大的麻烦。如下：

路由器的尾部丢弃的一连串分组，会使发送方出现超时重传，使TCP进入拥塞控制的慢开始状态(注意:我们现在讨论的是网络层的超时，传输层的快重传算法不适用),效率突然大大折扣。更为严重的是，如果网络中有很多的TCP连接，这些连接中的报文段通常是复用在网络层的IP数据报中传送，结果使这许多TCP连接在同一时间突然都进入到了慢开始状态。这在TCP中称为全局同步。全局同步使得全网的通信量突然都下降了很多，在网络恢复后，通信量又增加很多。

为了避免这种全局同步现象，就有了主动队列管理AQM(Active Queue Management),其思想如下：

主动就是不要等路由器的队列长度已经达到最大值是才不得不丢弃后边的数据分组，这样太被动了，应该在队列长度达到某个值就得警惕可能发生网络拥塞，采取相应的处理措施，降低网络拥塞发生的概率。
AQM的实现方法一般是随机早期检测RED(Random Early Dection)
实现RED需要路由器维持两个参数，即队列的最小门限和最大门限，每当一个分组到达时，就先计算当前队列的平均长度。具体描述如下：

若平均队列长度小于最小门限，则把新到达的分组放入队列进行排队。

若平均队列长度超过最大门限，则把新到达的分组丢弃。

若平均队列长度在最小门限和最大门限之间，则按照某一丢弃概率p把新到的分组丢弃。

附：丢弃概率p的处理是很难处理的，所以此方法已经不建议使用，但是对路由器进行主动队列管理AQM仍是必要的。