作者：henrystark henrystark@126.com
Blog: http://henrystark.blog.chinaunix.net/
日期：20140524
本文遵循CC协议：署名-非商业性使用-禁止演绎 2.5（https://creativecommons.org/licenses/by-nc-nd/2.5/cn/）。可以自由拷贝，转载。但转载请保持文档的完整性，注明原作者及原链接。如有错讹，烦请指出。
TCP fast recovery、partial ACK和Newreno
0.写作目的
本篇blog旨在纠正TCP fast recovery的理解、讲述TCP Newreno对于reno的改进。研究TCP要理论和代码并重，仔细读书，细节是魔鬼，按照理论设定，阅读代码才比较轻松。从细节入手，完全吃透，往往能收到意想不到的效果。
1.引言
TCP Newreno的改进主要在于对fast retransmit情况，partial ACK的处理。由于fast retransmit和fast recovery联系紧密。有感于国内不少做研究的，对fast recovery状态的描述和绘图多有错讹，因此这篇blog先讲述fast retransmit和fast recovery，再叙述TCP Newreno的partial ACK处理。
2.fast retransmit和fast recovery
这两个状态必须分别看待，才能完全弄懂TCP的减窗方式。fast restransmit实际上是一个暂态，是指收到三次dup ACK之后的动作。从收到第一个重复ACK起，到收到第三个重复ACK止，窗口不做调整，这一段的窗口行为对应到源码就是TCP拥塞状态机的DISORDER状态。收到第三个dup ACK，就进入RECOVERY状态。RECOVERY状态包含了fast retrans和fast recovery。进入RECOVERY状态的同时，就重传数据包，之后启动fast recovery机制。值得注意的一点是：fast recovery阶段的增窗速度很快，进入此阶段后，每收到一个dup ACK，cwnd就加1，因为网络空出来一个包的空间。fast recovery状态终止于new ACK，即收到新的ACK之后，此状态就终止。
文字干枯无聊，这里还是用图说明比较好，篇幅所限，这里以传统Newreno AIMD TCP为准作图。国内外很多研究或教材有误人子弟的嫌疑，我们经常看到的cwnd变化图是这样的：
图1 常见cwnd变化图
实际上，遵循RFC的cwnd变化图应该是这样的：
图2 RFC cwnd变化图
图1之所以如此，是在图2基础上做算法改进的结果，详情见【引 1】。
结合上图再来看TCP拥塞控制状态机就有恍然大悟的感觉了。拥塞状态机有不少细节处理，但骨架依然围绕图2。Disorder状态，cwnd不做调整。Recovery状态本该包含“3次dup ACK之后立即降窗”和“fast recovery迅速增窗”两个阶段。但现有Linux源码中，一进入Recovery状态就调用tcp_cwnd_down，每两个ACK，窗口减一。也就是在Recovery状态中，窗口只减不增。看了一会儿源码没有看到Recovery状态有增窗的语句，不敢确定【存疑】。不过此处问题不大。
重传包的队列处理、窗口处理，以及降窗引起窗口右侧收缩等细节稍后再另一篇blog讨论。
3.partial ACK和Newreno
这个名字听起来奇怪，其实概念并不复杂。连续丢包情况下，只收到了部分丢失包的ACK，那么这ACK就称为partial ACK。举例来说，如果4 5 6号包丢了，现在只重传4，只收到了4的ACK，后面的5 6没有确认，这就是partial ACK。Newreno的贡献就在于针对partial ACK的改进。reno的机制并没有考虑连续丢包的问题，如果每个丢失的包都要等待3个ACK来恢复，TCP的行为就相当蠢笨了。Newreno规定，有partial ACK时，后面未确认的数据段，也立即重传，这对于TCP的性能提升是显而易见的【引 2】。
然而Newreno的机制与SACK相比，仍逊色一筹，毕竟对于partial ACK的改进只能应对一部分情况，重传仍然是一次一次进行的，而使用SACK之后，可以在一个RTT内进行多个区间段、数据包的重传。
本文重点在讨论fast recovery阶段的处理。TCP多个变种的主要区别在于slow start增窗方式、丢包阈值调节、拥塞避免增窗方式。fast recovery和retrans却公用tcp_input.c，流程基本一致。后续文章也将讨论bic cubic的hystart等。
【引用】
【1】freeBSD tcp fast recovery改进, http://www.awadallah.com/tcp/。
【2】 The NewReno Modification to TCP's Fast Recovery Algorithm， http://tools.ietf.org/html/rfc6582。