TCP——为什么是AIMD？

作者：henrystark
Blog: http://henrystark.blog.chinaunix.net/
日期：20141012
本文遵循CC协议：署名-非商业性使用-禁止演绎 2.5（）。可以自由拷贝，转载。但转载请保持文档的完整性，注明原作者及原链接。如有错讹，烦请指出。
（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中已经证明了收敛性。