Kernel —— Tcp congestion control [V2 - Under revision]

Tcp congestion control 看了5天，总算有点头绪了，其中有三天时间算是白搭了，就因为作者盗用他人过时资料。

我始终想通过，通俗的说明，透彻的理解linux tcp congestion control。
内核中实现congestion control的函数是tcp_fastretrans_alert(),你只需要知道这个函数就够了。
我们一般，听说“拥塞了”，会有怎样的反应呢？想象北京的交通，It's so messy.
那我们会怎么做呢？直观上第一反应就是“逃离这里”。
如果逃不了呢？那你就要好好“享受”了。
所以没错，内核中拥塞处理和交通拥塞是一样的处理方式。
先想办法，逃开。 如果不想再想象怎么疏导。
所以你看tcp_fastretrans_alert() 这个函数，就被分成两部分：
1 想办法从congestion state 中exit。
2 处理各种congestion。
整体上我们知道就干这么两件事，接下来的问题就是怎么干了。
内核很聪明，无非就是细化处理问题。所以内核用了一个machine state来模型，简易化，问题。
状态机在内核的基本解释见ipv4/tcp_input.c
 Linux NewReno/SACK/FACK/ECN state machine.
1 "Open" Normal state, no dubious events, fast path.
2 "Disorder"   In all the respects it is "Open", but requires a bit more attention. It is entered when  we see some SACKs or dupacks. 
It is split of "Open"  mainly to move some processing from fast path to slow one.
3 "CWR" CWND was reduced due to some Congestion Notification event. It can be ECN, ICMP source quench, local device congestion.
4 "Recovery" CWND was reduced, we are fast-retransmitting.
5 "Loss" CWND was reduced due to RTO timeout or SACK reneging.
这里内核定义了含有5个状态的状态机，显然这是内核为了实现方便自己捣鼓出来的。
我们先直观的给出一个形象的解释，非严格逻辑的好坏关系：
Open 最好了，风和日丽的，数据包，唰唰地飞奔着。之后，
Disorder 可突然间有一个包没有得到回应ack，跑没影了。disorder你可以把他当成open。之后
CWR 对面发来通知，慢点太快受不了了。
Recovery 这个状态是内核处于紧张，小心的情况下产生的。当发现三个dack就快速处理掉。
Loss： 玩完了， 最糟糕的情况。
Open Disorder CWR，处于轻量级。
Recovery Loss 属于重量级，却是丢了。
你现在应该知道tcp_fastretrans_alert,所有内容无非就是在上面的状态中，逛来逛去的。
我们不急着去了解tcp_fastretrans_alert的实现细节内容，在此之前我们要了解一个非常变态的概念。
就是undo，undo的核心思想就是纠枉过正，一门心思的往好的state转换。
而tcp_fastretrans_alert实现上就是各种undo，这个也是理解起来最费劲的。
反正我是经常被搞晕。
现在我们开始看tcp_fastretrans_alert的具体实现。
像之前说过的分成两部分，退出和处理。
你看代码会发现所有的状态退出的前提都是una >= high_seq.
high_seq表示发生拥塞时，发送队列没有发送的第一个包。
那么una >= high_seq 说明发生拥塞的那个窗口里面的所有包，都被我们好好的处理掉了，也就是对端都收到了。
这个窗口的拥塞结束了，至于以后还会拥塞那是下一个窗口的事，我们要往好的方面看。既然我们都从一个窗口拥塞当中解脱出来了。
说明情况不是太糟。这就是我们退出拥塞的前提。
我们按着退出和处理两个过程考察这五个状态：
Loss： 当我们进入tcp_fastretrans_alert是loss状态说明我们判断丢包了。
对于从loss状态退出，我们调用tcp_try_undo_recovery; 中国人的象形思维，会把这个函数的recovery不自觉的和CA_RECOVERY这个状态建立联系。
实际上这是不对的，latin语系的人是抽象思维这里的recovery就是恢复的意思和那个状态无关。
tcp_try_undo_recovery我们会看到只有在Reno且una==high_seq才会保持loss状态，否则loss-> open。
关于Reno的una high_seq 的问题解析下。因为他决定我们是Loss 还是Open，不可小区。
在Reno中我们直到至少high seq这个序号被ack了才会loss ->open,是为了避免false fastretransmissions。
这个在rfc2582中讲解了。基本思想是，我们有可能在进入loss状态之初的时候，重传了3个包;当这三个包到达对端时，
实际上呢，原来的包没有丢知识延迟了一下，那么这三个包到了，对端就给我们发送重复 ACK。
在Reno中没有sack/dsack机制，我们是在reno模拟了sack，但那只是模拟，一种猜测而已，不准的，更没有dsack。
试想，我们加入在una == high seq 退出到open了，那么那三个多发了的重复ack会把我们重新带入fast recovery。
可是由sack的支持就不一样了dsack会告诉我们，是小于high seq的包重复了。没事，不会因为fast recovery。
而Reno的dack就不行了。可是当high seq以上都被处理了，那么reno版中的三个重复ack就会因为小于high seq以上的摸个ack序号，而不会引发fast recovery。
这个确实好难想呀。网上也没人说清楚。 
这样我们就从loss 到open了因为发生拥塞的那个问题窗口的所有包都被我们处理掉了，好呀。
tcp_try_undo_recovery返回0,我们现在的状态就是open了。
接下来就是处理open状态。 
如果在tcp_try_undo_recovery，我们may undo不成功则undo marker 和undo retrans 都将保留原值。
我们会在接下来的tcp_try_to_open处理中进入到Disorder.

如果我们进入tcp_fastretrans_alert是CWR状态呢？
我们为什么要保证high seq 被ack了，才退出到open呢。这是为了保证我们发送的包含CWR bit包到了接受端。对端不再给我们发送ece了。
稍作调整，我们又到了处理open的时候。

如果我们进入tcp_fastretrans_alert是Disorder状态。
如果我们是由于 loss open disorder 路径计入disorder状态，我们在退出前提是una >=high seq。
也就是说发生拥塞的那个窗口的包已经都被对端收到了，此时受到的dack，都是重复的无用的。
我们调用tcp_try_undo_dsack这个函数。如果我们受到了所用重发的包的ack，那么undo retrans就是0了。
我们就可以到open去了，因为不会再由dack了。对于reno也可以直接到因为reno不识别dack。
or 干脆una > high seq , 一了百了了。
总之我们到了Open。接下来又到了处理open的阶段了。

如果我们进入tcp_fastretrans_alert是Recovery状态。
此时拥塞窗口数据都得到了处理，要sack没什么用了，而reno自己模拟那个也得处理为0.
接下就是，我们或者open了，或者还是recovery。
如果recovery的话，到这里就直接返回了。 所以一条路走到黑的就是Open 了。
上面就是关于在拥塞状态下，内核的夺命狂奔，出逃。

接下来是如何处理各个状态
==============

首先是处理Recovery。
分为两种情况，ack了新的数据，还是老的数据。
如果这个ack，没有ack，prior una之后的数据，处理下reno的模拟sack就好了。
如果这个ack，ack了一点parital的新数据，也要处理reno的模拟的sack同时，
调用tcp_try_undo_partial, 这个函数不是为了达到open，而是尽力返回到进入recovery那个cwnd。
这个函数的返回值，表示这ack是否ack了部分重传队列的包。这个要好好理解下。
关联到后面update scorboard函数。部分重传队列已经被ack了当然要更新下scoreboard。
之后就是tcp_cwnd_down,每个受到一个ack减小一个cwnd。
重传数据包。

处理Loss状态
tcp_try_undo_loss 能undo 到open return
不能undo调整下cwnd，继续重发丢包。之后return。

default：
这里处理其他三个状态。
现实处理下reno的sack问题。

如果是disorder 调用tcp_try_undo_dsack,处理由于loss 到 open 再到disorder产生的dsack。
接下来tcp_time_to_recover表示是否进入RECOVERY状态。
否的话tcp_try_to_open 进入cwr or disorder， return。
是的话 进入Recovery
之后，调整cwnd，重传结束

--fin
我们先了解下TCP的拥塞控制解释。。
再说！