Chinaunix首页 | 论坛 | 博客
  • 博客访问: 354426
  • 博文数量: 48
  • 博客积分: 764
  • 博客等级: 上士
  • 技术积分: 1133
  • 用 户 组: 普通用户
  • 注册时间: 2011-01-17 13:29
文章分类

全部博文(48)

文章存档

2014年(5)

2013年(34)

2012年(9)

分类: LINUX

2013-04-08 13:17:47


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的拥塞控制解释。
再说!
阅读(5412) | 评论(2) | 转发(0) |
给主人留下些什么吧!~~

firocu2013-04-26 14:41:39

henrystark:文章写得不错,总体思路走得很顺。但是最后一段有点让人摸不着头脑。
TCP使用了滑动窗口和重传的概念(跟链路层很像)
可是貌似和这篇文章讲的没有太大关系。

关于窗口减半:减半是不错,只是现有实现里有些微妙的地方。
大概是每到两个ack,窗口减1,是逐渐降低的过程。
不记得是哪篇RFC了。

关于最后一段,以前在csdn回答问题时,偶然看到《计算机网络——自顶而下方法》3.4节。
讲了GBN和SR两种不同类型的协议设计,有兴趣可以看下。

p.s.我也在研究TCP,侧重方向貌似和你不同,感兴趣可以交流下。

哈哈,好呀,独乐乐不如众乐乐。我的邮箱firogm@gmail.com。


我的目标是大致把linux整个协议栈走一遍。
另外,这篇文章,还没写完,我的习作习惯不好,加上便于记录,草稿也会发上来。

回复 | 举报

henrystark2013-04-20 11:39:08

文章写得不错,总体思路走得很顺。但是最后一段有点让人摸不着头脑。
TCP使用了滑动窗口和重传的概念(跟链路层很像)
可是貌似和这篇文章讲的没有太大关系。

关于窗口减半:减半是不错,只是现有实现里有些微妙的地方。
大概是每到两个ack,窗口减1,是逐渐降低的过程。
不记得是哪篇RFC了。

关于最后一段,以前在csdn回答问题时,偶然看到《计算机网络——自顶而下方法》3.4节。
讲了GBN和SR两种不同类型的协议设计,有兴趣可以看下。

p.s.我也在研究TCP,侧重方向貌似和你不同,感兴趣可以交流下。