TCP拥塞控制图解(不包括RTO，因为它太简单了)
分享一下我老师大神的人工智能教程！零基础，通俗易懂！http://blog.****.net/jiangjunshow
也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！
最新的勘误已经发表，请先对照最新的勘误，如有疑问，随时联络，谢谢。
勘误链接： 《TCP拥塞控制图解(不包括RTO，因为它太简单了) 【勘误1】》五一假期放假，我感到莫名地轻松，因为这是一个三天无比快乐的工作时间，今天一天在家，修正了上周末的图表，终于完成了初稿。千万不要吵醒熟睡中的老婆，一旦吵醒了就什么都完了，那就必须通宵了，可是明天还要去西冲，到头来垂头丧气，还是完蛋！不管怎么说，今天总的东西希望对别的人有用(如果你觉得对你没有用的话)
1.网上有很多讲TCP拥塞控制的文章，但是几乎没有一篇能够讲清楚的，关于很多细节充其量只是描述一下代码，想必作者也没有真懂。唯一觉得比较好的两位博主：
a).****的http://blog.****.net/zhangskdb).chinaunix的http://blog.chinaunix.net/uid/28387257
其它的基本没什么可以看的了，代码解释谁都会，if解释成如果这些就是网络的垃圾，幸运的是，如今我也加入了他们，希望能成为NO.3，为大家抛砖引玉，只有大家站在同一个层面，才会有公平的PK。
2.在分析TCP拥塞控制的时候，不要动不动就摆出“拥塞状态机”，事实上这是Linux的独家奉献，如果看BSD或者其它的实现，很多根本就没有拥塞状态机的概念，只要完全按照RFC的要求或者建议去实现【有时候，也不必完全按照RFC】，你的TCP一样可以完美。
3.对于实现而言，Linux的TCP协议栈是一个很烂的实现，然而这是有理由的，Linux相比BSD或者lwIP的实现，消除了几乎所有的代码冗余，它希望在一套代码中，在一个很短的函数中，完成所有的一切，这就难免了各种if，&，||等
先上图为好。
可是，如果你用2.6.32的内核的话，就是以上这些了，然而如果你升级到4.4，你会看到不一样的结果！
tcp_may_raise_cwnd在tcp_fastretrans_alert之后，因为在alert中可以更新reordering
在处理的时候可以在partial ACK之后的una后面没有retrans，且确认数据包的ACK不是由于重传（是由于原始数据包）导致的时候（时间戳或者DSACK判断），可以进入Disorder状态，
且，如果partial ACK的后面连sack也没有，那么可以直接进入Open。这些都在图中画出了，详见Where to go。
4.刚才还没有完，我想来一点代码分析，基于Linux 2.6.32以及Linux 4.3
以下代码来自2.6.32
static int tcp_try_undo_partial(struct sock *sk, int acked){ struct tcp_sock *tp = tcp_sk(sk); /* Partial ACK arrived. Force Hoe's retransmit. */ int failed = tcp_is_reno(tp) || (tcp_fackets_out(tp) > tp->reordering); // 确认ACK是由最初的传输产生的还是由重传产生的 if (tcp_may_undo(tp)) { /* Plain luck! Hole if filled with delayed * packet, rather than with a retransmit. */ if (tp->retrans_out == 0) tp->retrans_stamp = 0; // 如果可能的话，更新乱序度，可悲的是，Linux2.6.32没有对其做出积极的反应， // 而仅仅是一些消极的反应:只有重复(或者sack)大于reordering才会标记LOST!!! tcp_update_reordering(sk, tcp_fackets_out(tp) + acked, 1); DBGUNDO(sk, "Hoe"); tcp_undo_cwr(sk, 0);//仅仅意味着可以多发一些数据，并不改变在快速恢复过程中由ssthresh指示的窗口收敛值 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPPARTIALUNDO); /* So... Do not make Hoe's retransmit yet. * If the first packet was delayed, the rest * ones are most probably delayed as well. */ // 这个启发在于，如果真的发生了undo，意味着网络中很可能真的发生了延迟或者乱序，而不是真正的丢包，因此不标记LOST，而是继续发送新数据或者前向重传 failed = 0; } return failed;} static void tcp_fastretrans_alert(struct sock *sk, int pkts_acked, int flag){ struct inet_connection_sock *icsk = inet_csk(sk); struct tcp_sock *tp = tcp_sk(sk); // (FLAG_DATA-接收端主动数据传输|FLAG_WIN_UPDATE-主动窗口更新|FLAG_ACKED-数据被ACK) // 对于主动发送的携带ACK的数据包，即便ACK重复了，也不算是重复ACK int is_dupack = !(flag & (FLAG_SND_UNA_ADVANCED | FLAG_NOT_DUP)); int do_lost = is_dupack || ((flag & FLAG_DATA_SACKED) && (tcp_fackets_out(tp) > tp->reordering)); int fast_rexmit = 0, mib_idx; ... /* B. In all the states check for reneging SACKs. */ // 详见图中的SACK reneging主动检测 if (tcp_check_sack_reneging(sk, flag)) return; /* C. Process data loss notification, provided it is valid. */ // 详见图中的LOST主动检测 if (tcp_is_fack(tp) && (flag & FLAG_DATA_LOST) && before(tp->snd_una, tp->high_seq) && icsk->icsk_ca_state != TCP_CA_Open && tp->fackets_out > tp->reordering) { tcp_mark_head_lost(sk, tp->fackets_out - tp->reordering); NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPLOSS); } ... if (icsk->icsk_ca_state == TCP_CA_Open) { WARN_ON(tp->retrans_out != 0); tp->retrans_stamp = 0; // 判断当前的ACK是否覆盖了cover } else if (!before(tp->snd_una, tp->high_seq)) { ... case TCP_CA_Disorder: // 如果可以可以undo dasck，代表了之前的重传都是误判。 tcp_try_undo_dsack(sk); if (!tp->undo_marker || /* For SACK case do not Open to allow to undo * catching for all duplicate ACKs. 没有必要如此严格 */ // reno无法识别DSACK，因此就不必去检查它了 tcp_is_reno(tp) || tp->snd_una != tp->high_seq) { tp->undo_marker = 0; tcp_set_ca_state(sk, TCP_CA_Open); } break; case TCP_CA_Recovery: if (tcp_is_reno(tp)) tcp_reset_reno_sack(tp); // 如果是reno模式，那么为了防止不必要(此处应该用"地" )地再次进入"快速重传"状态 // 必须要ACK超越cover!详见When to exit recovery if (tcp_try_undo_recovery(sk)) return; tcp_complete_cwr(sk); break; } } /* F. Process state. */ switch (icsk->icsk_ca_state) { case TCP_CA_Recovery: if (!(flag & FLAG_SND_UNA_ADVANCED)) { // 这是在模拟reno的sack呢 if (tcp_is_reno(tp) && is_dupack) tcp_add_reno_sack(sk); } else // 高版本的内核对此处理完全不一样，请参见图中Where to go do_lost = tcp_try_undo_partial(sk, pkts_acked); break; case TCP_CA_Loss: ... default: if (tcp_is_reno(tp)) { if (flag & FLAG_SND_UNA_ADVANCED) tcp_reset_reno_sack(tp); if (is_dupack) tcp_add_reno_sack(sk); } if (icsk->icsk_ca_state == TCP_CA_Disorder) tcp_try_undo_dsack(sk); if (!tcp_time_to_recover(sk)) { // 仅仅在Open，CWR，Disorder状态下才会被调用 tcp_try_to_open(sk, flag); return; } /* MTU probe failure: don't reduce cwnd */ if (icsk->icsk_ca_state < TCP_CA_CWR && icsk->icsk_mtup.probe_size && tp->snd_una == tp->mtu_probe.probe_seq_start) { tcp_mtup_probe_failed(sk); /* Restores the reduction we did in tcp_mtup_probe() */ tp->snd_cwnd++; tcp_simple_retransmit(sk); return; } /* Otherwise enter Recovery state */ if (tcp_is_reno(tp)) mib_idx = LINUX_MIB_TCPRENORECOVERY; else mib_idx = LINUX_MIB_TCPSACKRECOVERY; NET_INC_STATS_BH(sock_net(sk), mib_idx); tp->high_seq = tp->snd_nxt; tp->prior_ssthresh = 0; tp->undo_marker = tp->snd_una; tp->undo_retrans = tp->retrans_out; if (icsk->icsk_ca_state < TCP_CA_CWR) { if (!(flag & FLAG_ECE)) tp->prior_ssthresh = tcp_current_ssthresh(sk); tp->snd_ssthresh = icsk->icsk_ca_ops->ssthresh(sk); TCP_ECN_queue_cwr(tp); } tp->bytes_acked = 0; tp->snd_cwnd_cnt = 0; tcp_set_ca_state(sk, TCP_CA_Recovery); fast_rexmit = 1; } if (do_lost || (tcp_is_fack(tp) && tcp_head_timedout(sk))) tcp_update_scoreboard(sk, fast_rexmit); // 请注意，这是个可以修改的逻辑，在Linux 3.x中，其已经成了prr，然而2.6.32，并不。 tcp_cwnd_down(sk, flag); // 按照优先级来传输，参见图中How(to retransmit) tcp_xmit_retransmit_queue(sk);}我们看tcp_ack的逻辑： if (tcp_ack_is_dubious(sk, flag)) { /* Advance CWND, if state allows this. */ if ((flag & FLAG_DATA_ACKED) && !frto_cwnd && tcp_may_raise_cwnd(sk, flag)) tcp_cong_avoid(sk, ack, prior_in_flight); tcp_fastretrans_alert(sk, prior_packets - tp->packets_out, flag); } else { if ((flag & FLAG_DATA_ACKED) && !frto_cwnd) tcp_cong_avoid(sk, ack, prior_in_flight); }然后，我们看一下4.3的逻辑：
static bool tcp_try_undo_partial(struct sock *sk, const int acked, const int prior_unsacked, int flag){ struct tcp_sock *tp = tcp_sk(sk); if (tp->undo_marker && tcp_packet_delayed(tp)) { /* Plain luck! Hole if filled with delayed * packet, rather than with a retransmit. */ tcp_update_reordering(sk, tcp_fackets_out(tp) + acked, 1); /* We are getting evidence that the reordering degree is higher * than we realized. If there are no retransmits out then we * can undo. Otherwise we clock out new packets but do not * mark more packets lost or retransmit more. */ // 仅仅在第一次的时候，undo make明确为UNA的位置，然而收到第一个patial ACK的时候 // 会判断是否有数据包在重传中，如果有，就不忙着再标记LOST段了，而是什么都不做，将 // 窗口留给新数据 if (tp->retrans_out) { tcp_cwnd_reduction(sk, prior_unsacked, 0, flag); return true; } if (!tcp_any_retrans_done(sk)) tp->retrans_stamp = 0; DBGUNDO(sk, "partial recovery"); // 从此以后，undo make为0，就完全按照sack和reordering的差值来标记LOST了 tcp_undo_cwnd_reduction(sk, true); NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPPARTIALUNDO); tcp_try_keep_open(sk); return true; } return false;}在tcp_ack中： if (tcp_ack_is_dubious(sk, flag)) { // 这里不再针对dubious情形的ack也进行tcp_may_raise_cwnd的判断， // 从而在允许的情况下依然增加拥塞窗口。 is_dupack = !(flag & (FLAG_SND_UNA_ADVANCED | FLAG_NOT_DUP)); tcp_fastretrans_alert(sk, acked, prior_unsacked, is_dupack, flag); } if (tp->tlp_high_seq) tcp_process_tlp_ack(sk, ack, flag); /* Advance cwnd if state allows */ // 在这里进行tcp_may_raise_cwnd判断，保证在高乱序的情况下依然可以增加拥塞窗口 // 1.alert中可能会进行update reordering // 2.alert中会在partial ACK之后进入Disorder/Open状态 if (tcp_may_raise_cwnd(sk, flag)) tcp_cong_avoid(sk, ack, acked);而且在tcp_may_raise_cwnd中，会对reordering变大的情况做出补偿，因为此时，基本已经可以判定，并不是丢包，而是乱序导致了SACK！
最后，这并不是本系列文章的终结，我本想总结一下TCP拥塞控制的各种计数器，但是觉得那无非又是一番字词句段篇章，毫无意义，如果读懂了RFC，一切都好办了。
Linux TCP实现实在太烂了，但是我不觉得它比OpenSSL更烂，也不比Openv*n更烂，不是吗？我吐槽过OpenSSL和Openv*n，然而最终我放弃了OpenSSL，因为我知道It is beyond my ability！如今我不再吐槽了，因为无力做没有意义的事情了。
在此，我纠正一下措辞，马上着手另外一件事去了，不管怎么说，在一件事没有彻底(起码要60%+吧)搞明白之前，最好不要去搞别的，这会产生夹生饭。然而在我们的传统中，这好像毫无必要！因为我们的四大发明(这个关于四大发明的话题我会另外写一篇文章的，敬请期待)没有一个是知道了起码60%的原理后搞出来，这倒不是要反衬西方的实践都是在理解原理的前提下做出的，比如珍妮纺纱机，比如希腊火之类的，我要说的是，我们这里拥有一种魔法，正如中学时的化学老师所说的那样，我们的先人不知道什么是“酸”，但是却可以造出醋！于是我们都深深的受到了影响，于是就出现了大量的未知酸，先有醋的东西。大量的抄袭，大量的盗版，大量的毫无创意的模仿，但始终没有原创，因为大多数人一直都在追求的是一种所谓的捷径，而不是对知识的持续努力的积累，古人说过一句比较好的话，大意就是背诵了唐诗三百首，文章自然就流露出来了(不会写，也会偷)，虽然也是教人模仿，但是起码那需要硬努力，要么你花点时间研究一下平仄的规律，要么你就背诵大量的现成的诗去自己总结规律，难道还有别的路吗？？如果一开始上来就动笔，拿出来的可能会是一首诗，然而绝大多数是打油诗。
如果只做服务器而不是转发，针对路由子系统的工作就显得没有意义了...
附：Linux 2.6.32和3.x在undo时的窗口处理
我们比较关注TCP在快速恢复结束后窗口会怎样，它是不是被设置成降窗开始时的ssthresh呢？我们先看2.6.32的代码
case TCP_CA_Recovery: if (tcp_is_reno(tp)) tcp_reset_reno_sack(tp); // 如果是reno模式，那么为了防止不必要(此处应该用"地" )地再次进入"快速重传"状态 // 必须要ACK超越cover!详见When to exit recovery if (tcp_try_undo_recovery(sk)) return; // 上面的undo中可能存在may undo为真的情况，意味着所有的重传均是误判，因此窗口 // 会恢复到之前的大小，然而一切都被下面的complete函数拉回来了，它无条件取当前 // 窗口和ssthresh的最小值作为新窗口 tcp_complete_cwr(sk); break;然后再看下3.10的代码：
case TCP_CA_Recovery: if (tcp_is_reno(tp)) tcp_reset_reno_sack(tp); if (tcp_try_undo_recovery(sk)) return; // 我把下列函数中的一个注释提到这里: // "/* Reset cwnd to ssthresh in CWR or Recovery (unless it's undone) */" // 这意味着什么?这意味着如果在undo_recovery中undo_marker变成0了，也就是说 // may_undo返回了真，那么就不必将窗口reset到ssthresh了，因为undo操作已经将 // 窗口恢复到之前的值了。 // 这是十分合理的，然而是有条件的，条件就是之前的重传都是误判，均被DSACK了， // 这个条件并不苛刻，既然是误判，当然可以恢复拥塞之前的值了，然而，我们能否 // 激进一点呢? :-( tcp_end_cwnd_reduction(sk); break;其实，围绕这快速恢复结束后窗口应该在哪里这个问题，可以连续扯上一整天，但是我觉得这就好像两个势均力敌的人在扳手腕一样，状态是胶着的。