LinuxTCP拥塞控制-Congestion Control In LinuxTCP-拥塞状态机（二）

作者：henrystark [e-mail] 
Blog: http://henrystark.blog.chinaunix.net/
日期：20131004
本文可以自由拷贝，转载。但转载请保持文档的完整性，注明原作者及原链接。 如有错讹，烦请指出。

3.Linux实现

尽管Linux遵循了TCP拥塞控制原则，但是在实现中却采用了不同的方法。LinuxTCP发送端把outstanding的数据包和当前拥塞窗口进行比较，以确定如何发送数据【注 1】，而并非把拥塞窗口和SND.NXT、SND.UNA比较【注 2】。Linux是以满填充的包数目为单元计数的，而TCP标准建议按照字节数计算。这导致发送数据过程上的差异：如果使用字节计数窗口，TCP将允许拥塞窗口中的完整段被切分成几个小数据段发送【注 3】。而Linux只允许一个段对应一个包。所以，LinuxTCP对于小包的处理较为保守。
LinuxTCP发送端对于NewReno和SACK使用相同的策略来判定outstanding包数目【注 4】。当发送端能使用SACK时，就能使用FACK算法或者近似于IETF的方法来计算SACK数据块中的空洞。后者把所有未确认数据段视为outstanding。以下公式是所有recovery方法的基础：

left_out <- sacked_out + lost_out  
in_flight <- packets_out - left_out + retrans_out  

这些公式用来决定网络中outstanding的数据包。packets_out是正常传输的数据包数目，sacked_out是被SACK数据块确定的包数目，lost_out是对于丢失包数目的估计。retrans_out是重传的包数目。lost_out取决于选定的recovery算法。例如，当使用FACK时，所有在最高标号和确认标号之间的数据包都认为是lost_out。【注 5】
如果没有SACK信息，LinuxTCP发送端每收到一个重复ACK，就将sacked_out加1，这和TCP标准保持了一致性，而由此导致的行为也类似于NewReno算法【注 6】。Linux选择的设计原则并不要求窗口的任意调整，但是cwnd自始至终标志了fast recovery过程有多少包允许发送【注 7】。
用于跟踪outstanding, acked, lost, retransed数据包的计数器要求额外的数据结构支持。Linux发送端使用“计分板”维持每个outstanding的段的状态。报文段可能被标记为outstanding、acked、retransed或者lost。这几个标志位可能同时存在，例如，一个报文段可以被标记为lost和retransed。Linux发送端利用这些信息可以知道有哪些报文段需要重传、当新ACK到达时如何调整计数以确定in_flight等。“计分板” 在判断包是否错误标记为丢失方面扮演了一个重要角色，例如，可能只是发生了重排。
计分板和计数器在计算in_flight时，应该保持一致性。如何标志outstanding、acked和retransed数据段是显而易见的，但是如何标志lost则取决于recovery算法。使用NewReno的恢复算法会将第一个未确认数据包标记为lost。实际上，这和IETF的拥塞控制标准保持了一致。当ACK没有确认所有outstanding数据段时，第一个未确认段被标记为lost。这将会导致下一个未确认数据段的重传【注 8】，NewReno算法也是这样规定的。
Linux发送端在ACK到达时使用拥塞状态机来确定行为：

Open.这是正常发送状态，ACK按照快速路径处理。当有ACK到达时，发送端增加窗口，增加量取决于发送端处于慢启动还是拥塞避免。    
Disorder，当发送端探测到DACK或者SACK时，转变为乱序状态。该过程不会调整拥塞窗口，但是一个到达的包触发一个新数据段传输【注 9】。这时，TCP发送端遵循包守恒原则【引 1】，该原则指定旧数据包离开网络时才会触发新数据包发送。这种行为也类似于"限制传输"原则【引 2】，该原则建议在拥塞窗口较小或者大量段丢失时，使用更高效的传输方法，即快速重传。  
CWR.这个状态由ECN（显式拥塞通知）或者ICMP路径探测信息引起【注 10】，该状态可以被Recovery或者Loss状态中断。  
Recovery.当有足够多的连续DACK到来，发送端将重传第一个未确认数据段并进入Recovery状态。默认情况下，进入Recovery的条件是三个重复ACK【注 11】。在此状态中，每收到两个ACK，拥塞窗口减1，和CWR状态比较相似。当cwnd为一半时，不再减。在此状态中，cwnd不会增加，发送端可能重传被标记为lost的数据包，也可能按照包守恒原则发送数据包。当数据包得到确认，发送端就会回到open状态。RTO也会打断Recovery状态。
Loss。当RTO发生时，发送端进入loss状态。所有outstanding数据段被标记为lost。cwnd变为1。loss状态和Recovery状态的区别是Loss状态变为1以后，继续增长，而Recovery状态的cwnd只降低不增长。另外，loss状态不能被任何其他状态打断，在loss状态中，快速重传是没办法触发的。

LinuxTCP在上述状态中避免通过显式调用的方式来发送数据包，例如，在快速重传中就是这样【注 12】。现有的拥塞控制状态决定如何调整拥塞窗口和包丢失。当TCP发送端在某种状态下处理了一个ack后，如果in_flight小于cwnd，则发送数据包。发送端可能传输丢失、未及重传的包，或者新数据包。
某些情形下，outstanding的数据包数目会突然减少几个数据段。例如，一个ACK可能会确认多个段。这些情形会造成数据包的突发投递。Linux为了防止这种情况，规定一个ACK最多能引起三个数据包的传送。防止突发的措施可能会让cwnd降低至ssthresh之下，所以发送端有可能在收到累积ACK之后进入慢启动阶段。
当一个TCP连接建立之后，有许多变量需要初始化。但是，为了在连接初期提高通信效率，Linux发送端会缓存ssthresh、RTO等值，当指向同样IP的连接建立之后，可以使用这些变量。如果发送端和接收端的网络状况发生了变化，这些变量过时了。

注：
【1】例如将当前窗口的边界和已经发送的数据包标号、已经确认的数据包标号进行比较等。
【2】Linux实现中，SND.UNA是滑动窗口的左边界，SND.UNA+snd_wnd是滑动窗口的右边界。实际上，大体和TCP规定的滑动窗口标准是一致的。发送数据时，无论哪种实现，总要和SND.UNA、SND_UNA+snd_wnd这些值进行比较，只是在Linux中，这些值由cwnd代表。关于这一点，后续博文会详细讨论。
【3】这里说的意思可能是指非MSS的整数倍窗口，窗口如果不足一个MSS，还是可以发送。
【4】Linux中，所有TCP主要逻辑的实现都在tcp_input.c中，每个协议能重载的函数是有限的，比如阈值调节函数等。outstanding以为已经投递的数据包，可以理解为in_flight。
【5】FACK的算法过于激进，这些包可能并未丢失。
【6】NewReno是不支持SACK的，SACK出现在newreno之后，为了保持和newreno的兼容性，Linux可以用SACK来模拟newreno的行为，现有的主流协议都基于SACK，它已经作为一种基础存在。
【7】这一句不大理解，cwnd的任意调整可能是指非MSS整数倍。cwnd当然直接决定发送的段数，在任何状态中都是一样。
【8】多次重复ACK就会引起重传，这里的意思很奇怪，重传也是按顺序来的，不可能由重复ACK引起“下一个”数据段的重传。
【9】实际上，在disorder状态试探退出时，对cwnd做了调整，详见tcp_moderate_cwnd()这个函数，这个调整是为了防止一退出disorder，窗口就增长过高。当状态还处于disorder中时，多种参考文献均认定cwnd不做调整。 【10】CWR状态比较特殊，现有的交换机基本没有实现ECN机制，所以一般网络下，TCP发送端永远不会进入这个状态。 【11】disorder和recovery状态的进入规则都是重复ACK，但是重复数目不同，当有更多重复ack时，状态从disorder转换为recovery。关于disorder状态，在后续博文中会试图讲解，我也纠结了很久。 【12】这句话不理解什么意思，大概是指TCP发送数据的唯一方式是由ack和cwnd驱动，除此之外，别无他法。

引用： 【1】Jac88
【2】IETF [ABF01] 请有意者自行查阅。
第二部分到此结束。
如有错讹，欢迎指出，但是不要喷。我也是初学者。本文仅代表我个人的理解。