计算机网络基础（31）
TCP提供可靠的运输层。它使用的方法之一就是确认从另一端收到的数据。但数据和确认都有可能会丢失。TCP通过在发送时设置一个定时器来解决这种问题。如果当定时器溢出时还没有收到确认，它就重传该数据。
对于实现而言，关键之处就在于超时和重传的策略，即怎样决定超时间隔和如何确定重传频率。
TCP管理4种不同的定时器：
重传定时器：当希望收到另一端的确认时使用。坚持定时器：使窗口信息保持不断流动，即使另一端关闭了其接收窗口。保活定时器：检测一个空闲连接的另一端何时崩溃或重启。2MSL定时器：测量一个连接处于TIME_WATI状态的时间。
指数退避：书中检查连续重传之间不同的时间差，它们取整后分别是1、3、6、12、24、48和多个64秒，其中第一次发送后设置的超时时间设置为1.5秒。（2的N次方*1.5秒）
1.往返时间测量
RTT(往返时间)：指发送端发送TCP报文段开始到接收到对方的确定所使用的时间。
TCP超时与重传中最重要的部分就是对一个给定连接的往返时间的测试。由于路由器和网络流量均会变化，因此我们认为这个时间可能经常会发生变化，TCP应该跟踪这些变化并相应地改变其超时时间。
RTO(超时重传时间)：发送端发送TCP报文段后，在RTO时间内没有收到对方确定，即重传该报文段。
最早的TCP曾经用了一个非常简单的公式来估计当前网络的状况，如下：
R&-aR+(1-a)M
其中a是一个经验系数为0.9，称为平滑因子，b通常为2。这个数值是可以被修改的。这个公式是说用旧的RTT(R)和新的RTT(M)综合到一起来考虑新的RTT(R)的大小。每次进行新测量时，这个被平滑的RTT将得到更新。每个新估计的90%来自前一个估计，而10%则取自新的测试。
但是，在RTT变化范围很大时，使用这个方法无法跟上这种变化，从而引起不必要的重传。当网络已经处于饱和状态时，不必要的和重传会增加网络的负载，对网络而言就像在火上浇油。于是就有下面的修正公式：
A&-A+gErr
D&-D+h(|Err|-D)
RTO=A+4D
A 平滑的RTT(均值估计器)D 平滑的方差g 增量h 方差的增益
RTO值基于RTT的均值和方差，这更好的响应了RTT的变化。
karn算法（重传多义性）
假如发送一个分组，当发生超时，RTO指数退避，重传该分组，然后收到ACK。此时但并不能确定这个ACK是针对第一个分组还是重传分组，这就是重传多义性问题。
karn算法针对这个问题
(1)对于超时重传的数据报的确认，不更新RTT。
(2)要注意的是：重传的情况下，RTO不用上面的公式计算，而采用一种叫做“指数退避”的方式。RTO指数退避，下一次传送就使用这个RTO值。
(3)重传数据确认之后，再次发送的数据如果正常被确定，恢复Jacobson 1988公式，更新RTO和RTT。
2.拥塞避免算法
该算法假定由于分组受到损坏引起的丢失是非常少的，因此分组丢失就意味着源主机和目的主机之间的某处网络上发生了拥塞。有两种分组丢失的指示：
发生超时接收到重复的确认
数据在传输的时候不能只使用一个窗口协议，我们还需要有一个拥塞窗口来控制数据的流量，使得数据不会一下子都跑到网路中引起“拥塞”。也曾经提到过，拥塞窗口最初使用指数增长的速度来增加自身的窗口，直到发生超时重传，再进行一次微调。但是没有提到，如何进行微调，拥塞避免算法和慢启动门限就是为此而生。
所谓的慢启动门限就是说，当拥塞窗口超过这个门限的时候，就使用拥塞避免算法，而在门限以内就采用慢启动算法。所以这个标准才叫做门限，通常，拥塞窗口记做cwnd，慢启动门限记做ssthresh。下面我们来看看拥塞避免和慢启动是怎么一起工作的。
拥塞避免算法和慢启动算法是两个目的不同、独立的算法。我们希望降低分组进入网络的传输速率，于是可以调用慢启动来作到这一点，拥塞避免算法和慢启动算法通常一起使用：
每个连接维持两个变量: 拥塞窗口( cwnd )& 慢启动门限( ssthresh )[下图中假设为16]
算法概要：
对一个给定的连接，初始化cwnd为1个报文段，ssthresh为65535个字节。TCP输出例程的输出不能超过cwnd和接收方通告窗口的大小。拥塞避免是发送方使用的流量控制，而通告窗口则是接收方进行的流量控制。前者是发送方感受到的网络拥塞的估计，而后者则与接收方在该连接上的可用缓存大小有关。当拥塞发生时（超时或收到重复确认），ssthresh被设置为当前窗口大小的一半[下图中的12]（cwnd 和接收方通告窗口大小的最小值，但最少为2个报文段）。此外，如果是超时引起了拥塞，则 cwnd被设置为1个报文段（这就是慢启动）。当新的数据被对方确认时，就增加cwnd，但增加的方法依赖于我们是否正在进行慢启动或拥塞避免。如果cwnd小于或等于ssthresh，则正在进行慢启动，否则正在进行拥塞避免。 慢启动一直持续到我们回到当拥塞发生时所处位置的半时候才停止（因为我们记录了在步骤2 中给我们制造麻烦的窗口大小的一半），然后转为执行拥塞避免。
cwnd增加方式
慢启动初始cwnd为1，每收到一个确定就加1，成指数增长。
拥塞避免算法在每个RTT内增加 1/cwnd 个报文，成线性增长。
慢启动根据收到的ACK次数增加cwnd，而拥塞避免算法在一个RTT不管收有多少ACK也只增加一次。
3.快速重传和快速恢复算法
如果收到3个重复ACK，可认为该报文段已经丢失，此时无需等待超时定时器溢出，直接重传丢失的包，这就叫快速重传算法。而接下来执行的不是慢启动而是拥塞避免算法，这就叫快速恢复算法。
(1)当收到第3个重复的ACK时，将ssthresh设置为当前拥塞窗口cwnd的一半，重传丢失的报文段，设置cwnd为ssthresh加上3倍的报文段大小。
(2)每次收到另一个重复的ACK时，cwnd增加1个报文段大小并发送1个分组(如果新的cwnd允许发送)。
(3)当下一个确认新数据的ACK到达时，设置cwnd为ssthresh(在第1步中设置的值)。这个ACK应该是在进行重传后的一个往返时间内对步骤1中重传的确认。另外，这个ACK也应该是对丢失的分组和收到的第1个重复的ACK之间的所有中间报文段的确认。这一步采用的是拥塞避免，因为当分组丢失时我们将当前的速率减半。
4.ICMP（Internet
Control Message Protocol）Internet控制报文协议）差错
TCP能够遇到的最常见的ICMP差错就是源站抑制、主机不可达和网络不可达。
(1)源站抑制的ICMP将拥塞窗口cwnd置为1个报文段，并发起慢启动，慢启动门限ssthresh不变，窗口将打开直至开放了所有的通路(受窗口大小和往返时间的限制)或者发生了拥塞。
(2)主机不可达或网络不可达的ICMP将被忽略，因为这两上差错都被认为是短暂现象。
5.重新分组
当TCP超时并重传时，它不一定需要重传同样的报文段。相反，TCP允许进行重新分组而发送一个较大的报文段，这将有助于提高性能（当然，这个较大的报文段不能够超过接收方声明的MSS）
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：5409次
排名：千里之外
转载：39篇
(2)(1)(2)(6)(37)
为了防止网络的拥塞现象，TCP提出了一系列的拥塞控制机制。最初由V. Jacobson在1988年的论文中提出的TCP的拥塞控制由“慢启动(Slow start)”和“拥塞避免(Congestion avoidance)”组成，后来TCP Reno版本中又针对性的加入了“快速重传(Fast retransmit)”、“快速恢复(Fast Recovery)”算法，再后来在TCP NewReno中又对“快速恢复”算法进行了改进，近些年又出现了选择性应答(
selective acknowledgement,SACK)算法，还有其他方面的大大小小的改进，成为网络研究的一个热点。
&&&&&& TCP的拥塞控制主要原理依赖于一个拥塞窗口(cwnd)来控制，在之前我们还讨论过TCP还有一个对端通告的接收窗口(rwnd)用于流量控制。窗口值的大小就代表能够发送出去的但还没有收到ACK的最大数据报文段，显然窗口越大那么数据发送的速度也就越快，但是也有越可能使得网络出现拥塞，如果窗口值为1，那么就简化为一个停等协议，每发送一个数据，都要等到对方的确认才能发送第二个数据包，显然数据传输效率低下。TCP的拥塞控制算法就是要在这两者之间权衡，选取最好的cwnd值，从而使得网络吞吐量最大化且不产生拥塞。
&&&&& 由于需要考虑拥塞控制和流量控制两个方面的内容，因此TCP的真正的发送窗口=min(rwnd, cwnd)。但是rwnd是由对端确定的，网络环境对其没有影响，所以在考虑拥塞的时候我们一般不考虑rwnd的值，我们暂时只讨论如何确定cwnd值的大小。关于cwnd的单位，在TCP中是以字节来做单位的，我们假设TCP每次传输都是按照MSS大小来发送数据的，因此你可以认为cwnd按照数据包个数来做单位也可以理解，所以有时我们说cwnd增加1也就是相当于字节数增加1个MSS大小。
&&&&&&慢启动：最初的TCP在连接建立成功后会向网络中发送大量的数据包，这样很容易导致网络中路由器缓存空间耗尽，从而发生拥塞。因此新建立的连接不能够一开始就大量发送数据包，而只能根据网络情况逐步增加每次发送的数据量，以避免上述现象的发生。具体来说，当新建连接时，cwnd初始化为1个最大报文段(MSS)大小，发送端开始按照拥塞窗口大小发送数据，每当有一个报文段被确认，cwnd就增加1个MSS大小。这样cwnd的值就随着网络往返时间(Round
Trip Time,RTT)呈指数级增长，事实上，慢启动的速度一点也不慢，只是它的起点比较低一点而已。我们可以简单计算下：
&& 开始&&&&&&&&&& ---&&&&& cwnd = 1
&& 经过1个RTT后&& ---&&&&& cwnd = 2*1 = 2
&& 经过2个RTT后&& ---&&&&& cwnd = 2*2= 4
&& 经过3个RTT后&& ---&&&&& cwnd = 4*2 = 8
如果带宽为W，那么经过RTT*log2W时间就可以占满带宽。
&&&&&&拥塞避免：从慢启动可以看到，cwnd可以很快的增长上来，从而最大程度利用网络带宽资源，但是cwnd不能一直这样无限增长下去，一定需要某个限制。TCP使用了一个叫慢启动门限(ssthresh)的变量，当cwnd超过该值后，慢启动过程结束，进入拥塞避免阶段。对于大多数TCP实现来说，ssthresh的值是65536(同样以字节计算)。拥塞避免的主要思想是加法增大，也就是cwnd的值不再指数级往上升，开始加法增加。此时当窗口中所有的报文段都被确认时，cwnd的大小加1，cwnd的值就随着RTT开始线性增加，这样就可以避免增长过快导致网络拥塞，慢慢的增加调整到网络的最佳值。
上面讨论的两个机制都是没有检测到拥塞的情况下的行为，那么当发现拥塞了cwnd又该怎样去调整呢？
首先来看TCP是如何确定网络进入了拥塞状态的，TCP认为网络拥塞的主要依据是它重传了一个报文段。上面提到过，TCP对每一个报文段都有一个定时器，称为重传定时器(RTO)，当RTO超时且还没有得到数据确认，那么TCP就会对该报文段进行重传，当发生超时时，那么出现拥塞的可能性就很大，某个报文段可能在网络中某处丢失，并且后续的报文段也没有了消息，在这种情况下，TCP反应比较“强烈”：
1.把ssthresh降低为cwnd值的一半
2.把cwnd重新设置为1
3.重新进入慢启动过程。
从整体上来讲，TCP拥塞控制窗口变化的原则是AIMD原则，即加法增大、乘法减小。可以看出TCP的该原则可以较好地保证流之间的公平性，因为一旦出现丢包，那么立即减半退避，可以给其他新建的流留有足够的空间，从而保证整个的公平性。
其实TCP还有一种情况会进行重传：那就是收到3个相同的ACK。TCP在收到乱序到达包时就会立即发送ACK，TCP利用3个相同的ACK来判定数据包的丢失，此时进行快速重传，快速重传做的事情有：
1.把ssthresh设置为cwnd的一半
2.把cwnd再设置为ssthresh的值(具体实现有些为ssthresh+3)
3.重新进入拥塞避免阶段。
&&&& 后来的“快速恢复”算法是在上述的“快速重传”算法后添加的，当收到3个重复ACK时，TCP最后进入的不是拥塞避免阶段，而是快速恢复阶段。快速重传和快速恢复算法一般同时使用。快速恢复的思想是“数据包守恒”原则，即同一个时刻在网络中的数据包数量是恒定的，只有当“老”数据包离开了网络后，才能向网络中发送一个“新”的数据包，如果发送方收到一个重复的ACK，那么根据TCP的ACK机制就表明有一个数据包离开了网络，于是cwnd加1。如果能够严格按照该原则那么网络中很少会发生拥塞，事实上拥塞控制的目的也就在修正违反该原则的地方。
具体来说快速恢复的主要步骤是：
1.当收到3个重复ACK时，把ssthresh设置为cwnd的一半，把cwnd设置为ssthresh的值加3，然后重传丢失的报文段，加3的原因是因为收到3个重复的ACK，表明有3个“老”的数据包离开了网络。&
2.再收到重复的ACK时，拥塞窗口增加1。
3.当收到新的数据包的ACK时，把cwnd设置为第一步中的ssthresh的值。原因是因为该ACK确认了新的数据，说明从重复ACK时的数据都已收到，该恢复过程已经结束，可以回到恢复之前的状态了，也即再次进入拥塞避免状态。
快速重传算法首次出现在4.3BSD的Tahoe版本，快速恢复首次出现在4.3BSD的Reno版本，也称之为Reno版的TCP拥塞控制算法。
&&&&& 可以看出Reno的快速重传算法是针对一个包的重传情况的，然而在实际中，一个重传超时可能导致许多的数据包的重传，因此当多个数据包从一个数据窗口中丢失时并且触发快速重传和快速恢复算法时，问题就产生了。因此NewReno出现了，它在Reno快速恢复的基础上稍加了修改，可以恢复一个窗口内多个包丢失的情况。具体来讲就是：Reno在收到一个新的数据的ACK时就退出了快速恢复状态了，而NewReno需要收到该窗口内所有数据包的确认后才会退出快速恢复状态，从而更一步提高吞吐量。
SACK就是改变TCP的确认机制，最初的TCP只确认当前已连续收到的数据，SACK则把乱序等信息会全部告诉对方，从而减少数据发送方重传的盲目性。比如说序号1，2，3，5，7的数据收到了，那么普通的ACK只会确认序列号4，而SACK会把当前的5，7已经收到的信息在SACK选项里面告知对端，从而提高性能，当使用SACK的时候，NewReno算法可以不使用，因为SACK本身携带的信息就可以使得发送方有足够的信息来知道需要重传哪些包，而不需要重传哪些包。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：5069次
排名：千里之外
原创：28篇
(1)(3)(1)(2)(4)(1)(1)(5)(12)(7)8635人阅读
转自：http://blog.csdn.net/itmacar/article/details/
感谢博主的辛勤成果！
为了防止网络的拥塞现象，TCP提出了一系列的拥塞控制机制。最初由V. Jacobson在1988年的论文中提出的TCP的拥塞控制由“慢启动(Slow start)”和“拥塞避免(Congestion avoidance)”组成，后来TCP Reno版本中又针对性的加入了“快速重传(Fast retransmit)”、“快速恢复(Fast Recovery)”算法，再后来在TCP NewReno中又对“快速恢复”算法进行了改进，近些年又出现了选择性应答(
selective acknowledgement,SACK)算法，还有其他方面的大大小小的改进，成为网络研究的一个热点。
&&&&&& TCP的拥塞控制主要原理依赖于一个拥塞窗口(cwnd)来控制，在之前我们还讨论过TCP还有一个对端通告的接收窗口(rwnd)用于流量控制。窗口值的大小就代表能够发送出去的但还没有收到ACK的最大数据报文段，显然窗口越大那么数据发送的速度也就越快，但是也有越可能使得网络出现拥塞，如果窗口值为1，那么就简化为一个停等协议，每发送一个数据，都要等到对方的确认才能发送第二个数据包，显然数据传输效率低下。TCP的拥塞控制算法就是要在这两者之间权衡，选取最好的cwnd值，从而使得网络吞吐量最大化且不产生拥塞。
&&&&& 由于需要考虑拥塞控制和流量控制两个方面的内容，因此TCP的真正的发送窗口=min(rwnd, cwnd)。但是rwnd是由对端确定的，网络环境对其没有影响，所以在考虑拥塞的时候我们一般不考虑rwnd的值，我们暂时只讨论如何确定cwnd值的大小。关于cwnd的单位，在TCP中是以字节来做单位的，我们假设TCP每次传输都是按照MSS大小来发送数据的，因此你可以认为cwnd按照数据包个数来做单位也可以理解，所以有时我们说cwnd增加1也就是相当于字节数增加1个MSS大小。
&&&&&&慢启动：最初的TCP在连接建立成功后会向网络中发送大量的数据包，这样很容易导致网络中路由器缓存空间耗尽，从而发生拥塞。因此新建立的连接不能够一开始就大量发送数据包，而只能根据网络情况逐步增加每次发送的数据量，以避免上述现象的发生。具体来说，当新建连接时，cwnd初始化为1个最大报文段(MSS)大小，发送端开始按照拥塞窗口大小发送数据，每当有一个报文段被确认，cwnd就增加1个MSS大小。这样cwnd的值就随着网络往返时间(Round
Trip Time,RTT)呈指数级增长，事实上，慢启动的速度一点也不慢，只是它的起点比较低一点而已。我们可以简单计算下：
&& 开始&&&&&&&&&& ---&&&&& cwnd = 1
&& 经过1个RTT后&& ---&&&&& cwnd = 2*1 = 2
&& 经过2个RTT后&& ---&&&&& cwnd = 2*2= 4
&& 经过3个RTT后&& ---&&&&& cwnd = 4*2 = 8
如果带宽为W，那么经过RTT*log2W时间就可以占满带宽。
&&&&&&拥塞避免：从慢启动可以看到，cwnd可以很快的增长上来，从而最大程度利用网络带宽资源，但是cwnd不能一直这样无限增长下去，一定需要某个限制。TCP使用了一个叫慢启动门限(ssthresh)的变量，当cwnd超过该值后，慢启动过程结束，进入拥塞避免阶段。对于大多数TCP实现来说，ssthresh的值是65536(同样以字节计算)。拥塞避免的主要思想是加法增大，也就是cwnd的值不再指数级往上升，开始加法增加。此时当窗口中所有的报文段都被确认时，cwnd的大小加1，cwnd的值就随着RTT开始线性增加，这样就可以避免增长过快导致网络拥塞，慢慢的增加调整到网络的最佳值。
上面讨论的两个机制都是没有检测到拥塞的情况下的行为，那么当发现拥塞了cwnd又该怎样去调整呢？
首先来看TCP是如何确定网络进入了拥塞状态的，TCP认为网络拥塞的主要依据是它重传了一个报文段。上面提到过，TCP对每一个报文段都有一个定时器，称为重传定时器(RTO)，当RTO超时且还没有得到数据确认，那么TCP就会对该报文段进行重传，当发生超时时，那么出现拥塞的可能性就很大，某个报文段可能在网络中某处丢失，并且后续的报文段也没有了消息，在这种情况下，TCP反应比较“强烈”：
1.把ssthresh降低为cwnd值的一半
2.把cwnd重新设置为1
3.重新进入慢启动过程。
从整体上来讲，TCP拥塞控制窗口变化的原则是AIMD原则，即加法增大、乘法减小。可以看出TCP的该原则可以较好地保证流之间的公平性，因为一旦出现丢包，那么立即减半退避，可以给其他新建的流留有足够的空间，从而保证整个的公平性。
其实TCP还有一种情况会进行重传：那就是收到3个相同的ACK。TCP在收到乱序到达包时就会立即发送ACK，TCP利用3个相同的ACK来判定数据包的丢失，此时进行快速重传，快速重传做的事情有：
1.把ssthresh设置为cwnd的一半
2.把cwnd再设置为ssthresh的值(具体实现有些为ssthresh+3)
3.重新进入拥塞避免阶段。
&&&& 后来的“快速恢复”算法是在上述的“快速重传”算法后添加的，当收到3个重复ACK时，TCP最后进入的不是拥塞避免阶段，而是快速恢复阶段。快速重传和快速恢复算法一般同时使用。快速恢复的思想是“数据包守恒”原则，即同一个时刻在网络中的数据包数量是恒定的，只有当“老”数据包离开了网络后，才能向网络中发送一个“新”的数据包，如果发送方收到一个重复的ACK，那么根据TCP的ACK机制就表明有一个数据包离开了网络，于是cwnd加1。如果能够严格按照该原则那么网络中很少会发生拥塞，事实上拥塞控制的目的也就在修正违反该原则的地方。
具体来说快速恢复的主要步骤是：
1.当收到3个重复ACK时，把ssthresh设置为cwnd的一半，把cwnd设置为ssthresh的值加3，然后重传丢失的报文段，加3的原因是因为收到3个重复的ACK，表明有3个“老”的数据包离开了网络。&
2.再收到重复的ACK时，拥塞窗口增加1。
3.当收到新的数据包的ACK时，把cwnd设置为第一步中的ssthresh的值。原因是因为该ACK确认了新的数据，说明从重复ACK时的数据都已收到，该恢复过程已经结束，可以回到恢复之前的状态了，也即再次进入拥塞避免状态。
快速重传算法首次出现在4.3BSD的Tahoe版本，快速恢复首次出现在4.3BSD的Reno版本，也称之为Reno版的TCP拥塞控制算法。
&&&&& 可以看出Reno的快速重传算法是针对一个包的重传情况的，然而在实际中，一个重传超时可能导致许多的数据包的重传，因此当多个数据包从一个数据窗口中丢失时并且触发快速重传和快速恢复算法时，问题就产生了。因此NewReno出现了，它在Reno快速恢复的基础上稍加了修改，可以恢复一个窗口内多个包丢失的情况。具体来讲就是：Reno在收到一个新的数据的ACK时就退出了快速恢复状态了，而NewReno需要收到该窗口内所有数据包的确认后才会退出快速恢复状态，从而更一步提高吞吐量。
SACK就是改变TCP的确认机制，最初的TCP只确认当前已连续收到的数据，SACK则把乱序等信息会全部告诉对方，从而减少数据发送方重传的盲目性。比如说序号1，2，3，5，7的数据收到了，那么普通的ACK只会确认序列号4，而SACK会把当前的5，7已经收到的信息在SACK选项里面告知对端，从而提高性能，当使用SACK的时候，NewReno算法可以不使用，因为SACK本身携带的信息就可以使得发送方有足够的信息来知道需要重传哪些包，而不需要重传哪些包。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：126478次
积分：2258
积分：2258
排名：第13152名
原创：94篇
转载：41篇
评论：14条TCP进入快速恢复时的窗口下降算法 - Linux服务器 - 次元立方网 - 电脑知识与技术互动交流平台
TCP进入快速恢复时的窗口下降算法
夜深人静...
夜深人静...
TCP在发现丢包的时候，会采取一定的措施，至于如何发现丢包不是本文的内容，本文主要描述发现丢包以后TCP采取什么措施。
以为例，降窗发生在进入快速恢复的当时(暂时不考虑RTO以及本地拥塞)，在降窗之前是一个Disorder的状态，指的是系统发现了异常，比如收到了重复ACK或者说收到一个推进的ACK携带了SACK信息，然而还不至于到重传的地步，比如还没有达到乱序度的门限值，在门限值之下，系统会假设这只是一次乱序，马上就会好的，在Disorder状态，TCP的拥塞窗口是僵住的，即既不增加也不减少，此时会有两种结果，一个是在乱序度被超越前系统恢复了正常，那么将会进入拥塞避免状态，窗口执行AI，另一方面如果乱序度被超越，那么就会进入快速恢复状态，窗口执行MD，在这个状态中，拥塞窗口会持续降低，下面的篇幅就是来描述这个降窗过程的。
TCP会进入一个叫做&快速恢复&的状态，恢复什么呢？恢复到正常状态！在快速恢复中，主要要做的任务就是重传&被认为&是丢失的数据包。&被认为&之所以要加上引号是因为一切都是猜测！在这个过程中，TCP会认为网络发生了拥塞，既然发生了拥塞，再发多少数据包也没有用。TCP被设计为一个君子协议，那就是自己发现丢包的时候，自己会主动降低窗口，大家都这么做，以期望网络迅速恢复正常，这也就是为什么像华夏创新的那种算法永远都进不了标准，永远都写不成paper的原因吧。
现在的问题是，如何进行窗口的降低。
就目前看来，主要有4中方式降低窗口：
1.BSD原始方式：这也是《TCP/IP详解》(不是第二版啊)中描述的方式，像心电图一样，在降窗之前会有一个毛刺。目前早就已经弃用，想看究竟的话请看steven的书。
2.RFC3517方式：这是典型的NewReno方式，RFC3517中有详细的描述，比较短也不复杂，10分钟就能看完，就像看历史书一样，理解其基本思想即可，来龙去脉，引启未来。
3. rate halving方式：这是一种非标准的方式，但却是一种创新的方式，它&承若&不再陡降窗口，它将窗口缓慢降到原来的一半，然后在进入正常状态后再缓慢上升。
4.Linux PRR方式：基于rate halving，它不仅仅只是&承若&，而是保证！并且更加灵活了，降窗由ACK来驱动，具体降窗到哪里，取决于ssthresh，而后者是由具体的拥塞算法决定的。
以上就是典型的4中方式，教科书上的学院派方式基本都是1和2，这也是为什么随便问一个学生，他们都能答出1或2一样，而且1和2之间还会有没有休止符的争论。3和4属于内核社区，即便懂Linux内核的家伙们也没几个知道其细节，问起他们细节，他们大多数人的回答还是1或2...这倒也说明不了什么，只是说有些非标准实现不拘一格罢了。启自这种不拘一格，我自己也有一种天真的想法，那就是让快速恢复阶段的窗口走一个弧形，开始于原始窗口，结束于当前带宽允许的窗口。这也就是传说中的5。
本文就不再细说1和2了，毕竟我不是伟大的人民教师，也是个编程人员，没有那么多时间阐释大家都懂的东西，然而我擅长阐述大多数人不懂的东西。掠过1和2之前，说一下它们的缺点：
1).half silence
2).burst failed
千万不要觉得突发是优点或者缺点，如果将它们作为优点，那么当发出大量包时，会造成或加重网络拥塞，当没有这种突发时，又会造成保守的传输！不管怎样，这不是众口难调，而是算法本身的固有缺陷！
在除了1和2之外，我们来一个一个说吧。
Linux rate halving算法
Linux的TCP协议的实现中，采用了一种非标准化的降窗算法，即rate halving算法，顾名思义，它旨在将窗口降低到原有窗口的一半！目标和RFC3517是完全一致的，区别在于执行的过程。
Linux rate halving算法对待拥塞窗口的方式是执行一个缓慢下降的过程，而不像RFC3517那样一下子陡降到一半，然后在整个快速恢复过程中执行窗口线性缓慢上升的过程。恰恰相反，Linux rate halving算法是一个相反的过程，它一开始并不陡降窗口，在快速恢复的最后，它的目标是将窗口缓慢降到原来的一半，进入正常状态后，才从原有窗口的一半开始执行拥塞避免，线性缓慢增加窗口。
然而，实际情况往往不想愿景所希望的那样，我们会慢慢地理清头绪。首先，Linux rate halving的算法如下：
初始状态：
CWND=进入快速恢复前的拥塞窗口大小
在恢复正常前，对于每一个ACK，执行cwnd_down：
cwnd_down()
dec = dec + 1;
dec = decr&1;
CWND = CWND -
CWND = min(CWND, in_flight+1);
为了帮助理解，下面首先给出一个常规理想化的实例，演示算法的执行过程，然后给出一个稍微变态点的例子，演示这个算法的问题：
很完美！一共20个ACK，减掉一半的窗口(从20到10)，20个ACK意味着在进入快速恢复的时刻一窗数据在一个RTT内被确认，但请注意，以上的例子是在理想情况下的降窗过程！仔细看的话就会发现，它严重依赖与in_flight这个变量，即&目前发出的，未被确认，未标记为LOST&的数据包的数量。理想情况下，in_flight的值就是一窗的数据，即一个窗口的大小，但是事实上是那样吗？我们知道，数据包的发送，确认，标记丢失三者之间是解耦合的：
1.你无法保证发送路径或者重传路径一定会发送一个窗口那么多的包
2.你无法保证即便发出了一个窗口的包，update计分板(详见RFC3517的Update例程)的时候不会有大量数据包被标记为LOST
因此，在rate halving算法中，in_flight值可能会陡降，带来的效果就是CWND陡降，然而却没有补偿，比如下面这个稍微变态些的例子：
如果发生了大量的数据包被标记为LOST，情形如上，事实上降窗过程对此事毫不知情，FACK模式下一个携带SACK的包就可能标记很多包为LOST！除此之外，rate halving降窗算法中，以ACK数量而不是ACKed的字节数来作为标尺，这看似是一件好事，但是由于ACKed的字节数会直接体现在in_flight变量中，结果就是，如果一个ACK确认大量的字节，in_flight会变小，最终取min的时候，还是会造成窗口陡降！不过这也倒是迎合了RFC2582的建议：
Deflate the congestion window by the amount of new data acknowledged, then add back one MSS and send a new
segment if permitted by the new value of cwnd. This &partial window deflation& attempts to ensure that, when
Fast Recovery eventually ends, approximately ssthresh amount of data will be outstanding in the network.
但是不同的是什么？不同是NewReno在快速恢复阶段的窗口是从ssthresh逐步以拥塞避免方式增加的，而Linux rate halving算法在快速恢复阶段窗口是只降不升的，这是根本的区别，NewReno在收到patial ACK的时候降窗的理由在Linux rate halving看来并不充分：
Note that in Step 5, the congestion window is deflated when a partial acknowledgement is received.
The congestion window was likely to have been inflated considerably when the partial acknowledgement
was received. In addition, depending on the original pattern of packet losses, the partial acknowledgement
might acknowledge nearly a window of data. In this case, if the congestion window was not deflated, the
data sender might be able to send nearly a window of data back-to-back.
现在我们知道Linux rate halving降窗算法的实际效果了，现在我们来看一下窗口陡降带来的影响以及造成这种影响的根源。窗口陡降的效果就是它会降到ssthresh以下，从而在快速恢复阶段结束后进入慢启动状态。其实如果你仔细看这个算法，会发现它根本就没有检查ssthresh，而只是限定了&halving&这个动作，因此就算窗口不是陡降，算法也无法感知窗口与ssthresh当前的关系。
Linux rate halving的根源在于：
1.如其名称中的half单词，它的目标是将窗口减半，然而首先，并不是所有的拥塞控制算法都是将窗口减半的，这只是早期Reno/NewReno的规范而已；
2.即便是将窗口减半，在执行的过程中，算法并没有好好的履行承诺，而是过分依赖于一个自己无法控制的in_flight变量，且被其控制；
3.再退一步，即便窗口已经降到了一半以下(已经不再用ssthresh约束它了)，Linux rate halving算法并没有任何补偿措施将窗口拉上来；
4.抛开窗口会降到哪里不说，Linux rate halving算法在快速恢复阶段，每次最多只允许1个数据段被发送，即窗口in_flight+1。
鉴于Linux rate halving的不足，google推出了其Linux PRR算法，解决了上面提到的三个问题。
google的Linux PRR降窗算法
我们先看它解决了哪些问题，针对Linux rate halving的缺点，PRR算法：
1.不再仅仅halving，而是完全根据拥塞算法计算出的ssthresh，来将窗口逼近于它；
2.执行的过程不再受当前的in_flight控制，而是根据快速重传以来的发送/接收ACK的总数量来将窗口按照等比例的方式逼近ssthresh；
3.如果窗口降到了ssthresh以下(比如没有数据包可发送或大量包被标记LOST)，算法执行慢启动将其拉升到ssthresh附近；
4快速恢复阶段，最多&还&可以发送(或者说重传)多少数据，不再限定为1，而是取决于&当前收到的ACK/SACK总量，发出数据总量，窗口与ssthresh的关系&。
其中最重要的是上述第2点，它简单的指出了PRR算法是依靠ACK来驱动的，这就形成了一个反馈系统，只可惜PRR只利用了这个反馈系统的一部分，另一部分待我
在下一部分描述我的一个优化时再讨论。紧跟着上面的4点，这个PRR算法的最终效果就是：
1).在快速恢复过程中，拥塞窗口非常平滑地向ssthresh收敛；
2).在快速恢复结束后，拥塞窗口处在ssthresh附近。
为了实现上述的目标，PRR降窗算法必须实时监控以下的变量：
in_flight：它是窗口的一个度量，in_flight的值任何时候都不能大于拥塞窗口的大小。
(s)acked：本次收到ACK进入降窗函数的时候，一共被ACK或者SACK的数据段数量。它度量了本次从网络中清空了哪些数据段，从而影响in_flight。
out：进入快速恢复状态后已经被发送了多少数据包。在transmit例程和retransmit例程中递增。
to_be_out：当前还可以再发多少数据包。
根据数据包守恒原则，能够发送的数据包总量是本次接收到的ACK中确认的数据包的总量，然而处在拥塞状态要执行的并不是这个守恒发送的过程，而是降窗的过程，因此需要在被ACK的数据包数量和可以发送的数据包数量之间打一个折扣，PRR希望达到的目标是：
ssthresh/old_cwnd==发送数据的速率/数据被ACK的速率
ssthresh/old_cwnd==(发送数据的速率*T)/(数据被ACK的速率*T)
ssthresh/old_cwnd==pkts_out/acks_rcv
以此来将目标窗口收敛于ssthresh。刚进入快速恢复的时候的时候，窗口尚未下降，在收敛结束之前，下面的不等式是成立的：
ssthresh/old_cwnd&=pkts_out/acks_rcv
acks_rcv*(ssthresh/old_cwnd)&=pkts_out
考虑到数据包的守恒，设
extra=acks_rcv*(ssthresh/old_cwnd)-pkts_out
这意味着在收敛结束前，我们可以多发送extra这么多的数据包。上述结论的具体推导过程如下：
数据包守恒原则中我们要注意到一个递推的等式，守恒原则要求，被ACK或者SACK多少数据包，说明有这么多数据包离开了网络，方可以发出多少数据包，该等式序列如下：
进入快速恢复时的初始状态：
(s)acked0=0
to_be_out0=0
此后每收到一个ACK(可以携带SACK block)：
收到第1个ACK：
to_be_out1=this_acked=(s)acked1; out1=to_be_out1
收到第2个ACK：
to_be_out2=this_acked=(s)acked2-(s)acked1=(s)acked2-out1; out2=out1+to_be_out2
收到第3个ACK：
to_be_out3=this_acked=(s)acked3-(s)acked2=(s)acked3-(to_be_out2+out1)=(s)acked3-out2; out3=out2+to_be_out3
收到第5个ACK：
to_be_out5=(s)acked5-out4; out5=out4+to_be_out3
收到第6个ACK：
to_be_out6=(s)acked6-out5; out5=out5+to_be_out4
收到第N个ACK：
to_be_out[N]=(s)acked[N]-out[N-1]; out[N]=out[N-1]+to_be_out[N]
通过以上的等式，我们可以得到一个关系，那就是：PRR反馈系统通过to_be_out来补充被(s)acked清空的out！这就好比一个生产者/消费者之间
交易的过程，目前的PRR算法要求这个交易过程不是等价交易，而是一个折扣交易，要在收到的(s)acked上打折扣，这意味着如果发送端接有N个
数据段被ACK了，那么只能算beta*N个被ACK了，其中0&beta&1。于是上面的等式变为了：
to_be_out[N]=beta*(s)acked[N]-out[N-1]
对比一下结论：
extra=acks_rcv*(ssthresh/old_cwnd)-pkts_out
我们知道，这个折扣就是(ssthresh/old_cwnd)！
好了，现在该给出Linux PRR算法了：
初始状态：
CWND=进入快速恢复前的拥塞窗口大小
old_cwnd=CWND
ssthresh=拥塞算法计算的结果，可以是old_cwnd的1/2，4/5，...
在恢复正常前，对于每一个ACK，执行cwnd_down：
cwnd_down_prr(tcp_sock)
tcp_sock.acked = tcp_sock.acked+本次被ack或者sack的数据段总数;
if (tcp_sock.in_flight & tcp_sock.ssthresh) {
cnt = tcp_sock.acked*(tcp_sock.ssthresh/tcp_sock.old_cwnd) - tcp_sock.
cnt = tcp_sock.ssthresh - tcp_sock.in_
tcp_sock.CWND = tcp_sock.in_flight +
和介绍Linux rate halving一样，同样给出一个实例来演示算法执行过程，类似的，第一个例子是标准理想环境下的，第二个是变态些的：
下面我给出一个和Linux rate halving的第二个例子初始状态一致的PRR的例子，我们来看看PRR是怎么补偿窗口的陡降的：
最后我们来一个综合的带有SACK的例子：
算法执行下去的话，没有任何问题，窗口即使不会陡降到ssthresh之下，下一步也会执行类似慢启动的过程提升上来的。这里所谓&类似慢启动&的过程指的就是，按照被ACK的数据的大小来增加窗口，比如ACK了n个，那么窗口就增加n个MSS大小。
从例子中，我们看到，算法执行的每一个步骤，目标拥塞窗口都是根据in_flight，(s)acked，out等实时平滑计算出来的，其降窗的结果充分反应了当前的网络情况，从而解决了Linux rate halving算法中&孤立地&一厢情愿企图&将窗口在一个RTT内降到原有窗口的一半&这么一个连兑现基本的承诺都显得勉强的降窗算法中存在的问题。
一个简单的降窗优化
爆炸！关于拥塞降窗的问题基本都结清了。现在基于PRR算法我有一个简单的优化思路。
我的企图很简单，我希望窗口不必一定下降到ssthresh，而是设置一个截止阀，下降到这个值就不必再继续往下降了，维持住即可，然后从这个窗口开始拥塞避免。事实上不管多么高大上的拥塞控制算法在进入快速恢复之前，计算的所谓ssthresh都TMD是拍脑子拍出来的！以Linux目前的默认拥塞算法cubic为例，进入快速恢复前会将ssthresh重新设置为当前窗口的717/1024，这是个恒定比例，丝毫没有考虑到拥塞的严重程度，或者只是另一个极端，这个丢包只是源自于一个偶尔的网络噪声，这些在cubic的算法层面都没有提及。
PRR算法的好处在于根据当前的TCP计数器(out，acked等)的实时值动态地，平滑地将窗口收敛到ssthresh，这是比rate halving好的方面，相比PRR，rate halving是一个完全封闭的算法，根本没有管当前的TCP计数器值的变化情况。然而PRR也不够完全动态，毕竟ssthresh可以视作一个定值，有时候窗口根本没有必要下降那么多！那么窗口下降到何种程度合适呢？我认为降到&数据被ACK的速率与数据被发送的速率相等&的这一刻即可，这说明这个时候pipe是刚好畅通的，发多少包，收到多少(s)ack！
经过改进的算法如下所示：
cwnd_down_prr_pro(tcp_sock)
tcp_sock.acked = tcp_sock.acked+本次被ack或者sack的数据段总数;
tmp1 = tcp_sock.acked - tcp_sock.prior_
tcp_sock.prior_acked = tcp_sock.
tmp2 = tcp_sock.out - tcp_sock.prior_
tcp_sock.prior_out = tcp_sock.
// 连续3次以上被确认的数量与发送数量之差小于1，说明速率均等，维持窗口，不再下降
if (tmp1 - tmp2绝对值小于等于1) {
tcp_sock.eq++;
tcp_sock.gt = 0;
if (tcp_sock.eq &= 3) {
tcp_sock.ssthresh = tcp_sock.cwnd - 1;
// 连续3次以上确认量大于发出量，增窗！
else if (tmp1 & tmp2) {
tcp_sock.gt++;
tcp_sock.eq = 0;
if (tcp_sock.gt &= 3) {
tcp_sock.ssthresh = tcp_sock.cwnd - 1;
// 否则继续降窗
tcp_sock.eq = 0;
tcp_sock.gt = 0;
tcp_sock.ssthresh = tcp_sock.ssthresh_by_cong_ALG;
if (tcp_sock.in_flight & tcp_sock.ssthresh) {
cnt = tcp_sock.acked*(tcp_sock.ssthresh/tcp_sock.old_cwnd) - tcp_sock.
cnt = tcp_sock.ssthresh - tcp_sock.in_
tcp_sock.CWND = tcp_sock.in_flight +
你会注意到，它牺牲了公平性，也就是说在可能的情况下，不再执行MD，另一方面，这个算法还有一个作用，那就是它竟然可以简单区分是网络噪声引发的偶尔丢包还是拥塞造成的持续丢包。关于公平性，还要说的就是，在别人都在抢你资源的时候，谁对别人友好谁就是2B！
延伸阅读：
Ceph是加州大学SantaCruz分校的SageWeil（DreamHost的...
本教程为 李华明 编著的iOS-Cocos2d游戏开发系列教程：教程涵盖关于i......
专题主要学习DirectX的初级编程入门学习，对Directx11的入门及初学者有......
&面向对象的JavaScript&这一说法多少有些冗余，因为JavaScript 语言本......
Windows7系统专题 无论是升级操作系统、资料备份、加强资料的安全及管......