• 博客访问: 358817
  • 博文数量: 39
  • 博客积分: 125
  • 博客等级: 民兵
  • 技术积分: 1833
  • 用 户 组: 普通用户
  • 注册时间: 2013-01-03 11:29
个人简介

skills:Linux TCP,C; 欢迎邮件和Q群交流.

文章分类

全部博文(39)

文章存档

2014年(9)

2013年(30)

微信关注

IT168企业级官微



微信号:IT168qiye



系统架构师大会



微信号:SACC2013

订阅
热词专题
TCP——为什么是AIMD? 2014-10-12 15:58:46

分类: LINUX

作者:henrystark henrystark@126.com
Blog: http://henrystark.blog.chinaunix.net/
日期:20141012
本文遵循CC协议:署名-非商业性使用-禁止演绎 2.5(https://creativecommons.org/licenses/by-nc-nd/2.5/cn/)。可以自由拷贝,转载。但转载请保持文档的完整性,注明原作者及原链接。如有错讹,烦请指出。
(I like thinker or creater, not follower. If you are a good follower and get the key point by learning others, don't say you own it.)



TCP——为什么是AIMD

说到TCP原理,一般的人谈传输效率,也就是吞吐率,了解的人谈公平性,以及收敛性。本篇博文讲一下TCP为什么使用AIMD策略,为什么是收敛的?


1.公平性和收敛性


才接触网络协议的人可能会问:为什么要收敛和公平?TCP不是传输可靠、够快就行了吗?
远远不够,因为TCP是端到端的,窗口增减也是试探性的“自适应”方式,网络是黑盒,这就有很多问题。你自己一个人发包发得快,侵略性强,没有太大问题。但是如果其他人也跟你一样没有节制的发包呢?这就会造成网络负载过重,以至于崩溃。公平性和收敛性的出发点就在这里。让每一个TCP发送端尽可能地均分带宽,同时减少丢包,减轻网络设备的压力。这其实是很难的trade off。TCP窗口总是锯齿状地周期抖动,增长-减小,不断循环,这种探测带宽的行为一定会造成丢包,只是或多或少的差别而已。


举个例子:你现在看动漫《fate/stay night ubw》,已经开始了一段时间,视频缓冲速度很快。这时候你旁边的同学看你这么入神,发现很好看,于是加入队伍,也点开视频。这时候网络该怎么分呢?又通过什么样的机制分呢?最好的结果当然是均分带宽,你自己分一半,同学也分一半,这时候你的视频缓冲就慢下来了【注 1】。公平分配说起来容易,做起来难。怎么保证完全均分?这就要靠丢包和延时变动来反映网络状况。你的同学加入了,新建的TCP连接会尝试慢启动,慢启动其实不慢,窗口指数增长,缓冲速度快速增加,也就是说,他开始抢你的带宽了。抢到一定时刻,一定会引起丢包,或者延时的急剧增长。这时候,基于丢包或者延时变动的TCP减窗机制起作用了,你们两个都开始减窗。你减一点,我减一点。这时候你会想:不对啊,我先开始的,速度早就涨上去了,我们两个都减,他永远赶不上我。那么,开始谈第二个问题。


2.AIMD为什么收敛


上面说到减窗,现在普遍的减窗策略是“乘性减窗”,英文对应“MD”。比如你们固有的带宽是8M,一开始你自己全占了,然后同学开始抢,慢启动发包很快,于是,交换机缓存扛不住了,丢包了。这时候你的吞吐率是7M,同学的速率是1M。你们两个的TCP察觉到丢包后,把速率各减去一半,你有3.5M,他有0.5M。网络不拥塞了,没有丢包,那就继续增窗。该增多少呢?你的带宽明显占优势,同学有没有可能获得比你更高的速率呢?怎么样增才能达到均分带宽的目的?现在普遍的增窗策略是“加性增窗”,英文对应“AI”。也就是每条TCP连接在一个RTT内的增量是常数,假设这个加性因子为200K。那接下来的速率增长就是:你有3.5+0.2=3.7,同学有0.5+0.2=0.7.

看到这里,或许有的人就恍然大悟了:这样增窗,结果是大家的速率都收敛。也许还有人不明白,那就把速率随时间变化的情况列出出来:

     3.5     0.5
    3.7     0.7
    3.9     0.9
    4.1     1.1
    ……………………………
    5.5     2.5
    2.75    1.25    MD
    ……………………………
    4.75    3.25
    2.375   1.625   MD
    ……………………………
    4.375   3.625
    2.1875  1.8125  MD
    ……………………………
    4.1875  3.8125  MD
    …………………………… 


从以上速率变化,可以看出,两条TCP连接的速率在逐渐趋近,这就是AIMD策略的效果:收敛,到最后公平。也许有的人意犹未尽,那就从公式角度再算一次看看。假设flow1的初始窗口为c1,flow2的初始窗口为c2。MD减窗过程中,乘性因子为beta=0.5,也就是遇到丢包,窗口减一半。AI增窗过程中,加性因子为a。于是有:

     c1' = ((c1*0.5 + m*0.2)*0.5 + m*0.2)*0.5 + m*0.2 …………
    这里m是变化的,表示增窗的次数,直到遇到丢包。但是由于带宽有限,于是m可以视为常数。
    c1'可以用等比数列求和公式给出,这里就不详细计算了。结论可以直接告诉大家:
    c1'收敛到跟m和beta有关,跟c1无关的常数。
    c2'也类似。
    收敛性的证明比较复杂,我也懒得在博文里讲这么学术化的事情。参见【注 2】。 


看到这里,你也就明白,TCP如何均分带宽,你同学又为什么能从你手里抢到带宽了。至于减窗是不是过于剧烈,beta能不能设置得更好,变成动态的,增窗因子能不能设置更好,变成动态的。以及能不能抛弃AIMD,使用MIMD,在什么网络中能这样做。这些问题就不是本文的讨论范围了,也许以后会讲。

注:
【1】视频传输中,实时性视频用UDP,非实时性视频用TCP,这里用人气动漫举例,是比较恰当的,动漫不像篮球比赛,没有太强的实时性。好奇的同学可以查阅“牛奶葡萄酒”原则。
【2】Jacobson在他著名的论文,SIGCOMM 88中已经证明了收敛性。

阅读(6030) | 评论(0) | 转发(2) |
0

上一篇:QUIC和TCP

下一篇:没有了

给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册