TCP――為什么是AIMD？

TCP——為什么是AIMD

說(shuō)到TCP原理，一般的人談傳輸效率，也就是吞吐率，了解的人談公平性，以及收斂性。本篇博文講一下TCP為什么使用AIMD策略，為什么是收斂的?

1.公平性和收斂性

才接觸網(wǎng)絡(luò)協(xié)議的人可能會(huì)問(wèn)：為什么要收斂和公平?TCP不是傳輸可靠、夠快就行了嗎?

遠(yuǎn)遠(yuǎn)不夠，因?yàn)門CP是端到端的，窗口增減也是試探性的“自適應(yīng)”方式，網(wǎng)絡(luò)是黑盒，這就有很多問(wèn)題。你自己一個(gè)人發(fā)包發(fā)得快，侵略性強(qiáng)，沒(méi)有太大問(wèn)題。但是如果其他人也跟你一樣沒(méi)有節(jié)制的發(fā)包呢?這就會(huì)造成網(wǎng)絡(luò)負(fù)載過(guò)重，以至于崩潰。公平性和收斂性的出發(fā)點(diǎn)就在這里。讓每一個(gè)TCP發(fā)送端盡可能地均分帶寬，同時(shí)減少丟包，減輕網(wǎng)絡(luò)設(shè)備的壓力。這其實(shí)是很難的trade off。TCP窗口總是鋸齒狀地周期抖動(dòng)，增長(zhǎng)-減小，不斷循環(huán)，這種探測(cè)帶寬的行為一定會(huì)造成丟包，只是或多或少的差別而已。

舉個(gè)例子：你現(xiàn)在看動(dòng)漫《fate/stay night ubw》，已經(jīng)開始了一段時(shí)間，視頻緩沖速度很快。這時(shí)候你旁邊的同學(xué)看你這么入神，發(fā)現(xiàn)很好看，于是加入隊(duì)伍，也點(diǎn)開視頻。這時(shí)候網(wǎng)絡(luò)該怎么分呢?又通過(guò)什么樣的機(jī)制分呢?最好的結(jié)果當(dāng)然是均分帶寬，你自己分一半，同學(xué)也分一半，這時(shí)候你的視頻緩沖就慢下來(lái)了【注 1】。公平分配說(shuō)起來(lái)容易，做起來(lái)難。怎么保證完全均分?這就要靠丟包和延時(shí)變動(dòng)來(lái)反映網(wǎng)絡(luò)狀況。你的同學(xué)加入了，新建的TCP連接會(huì)嘗試慢啟動(dòng)，慢啟動(dòng)其實(shí)不慢，窗口指數(shù)增長(zhǎng)，緩沖速度快速增加，也就是說(shuō)，他開始搶你的帶寬了。搶到一定時(shí)刻，一定會(huì)引起丟包，或者延時(shí)的急劇增長(zhǎng)。這時(shí)候，基于丟包或者延時(shí)變動(dòng)的TCP減窗機(jī)制起作用了，你們兩個(gè)都開始減窗。你減一點(diǎn)，我減一點(diǎn)。這時(shí)候你會(huì)想：不對(duì)啊，我先開始的，速度早就漲上去了，我們兩個(gè)都減，他永遠(yuǎn)趕不上我。那么，開始談第二個(gè)問(wèn)題。

2.AIMD為什么收斂

上面說(shuō)到減窗，現(xiàn)在普遍的減窗策略是“乘性減窗”，英文對(duì)應(yīng)“MD”。比如你們固有的帶寬是8M，一開始你自己全占了，然后同學(xué)開始搶，慢啟動(dòng)發(fā)包很快，于是，交換機(jī)緩存扛不住了，丟包了。這時(shí)候你的吞吐率是7M，同學(xué)的速率是1M。你們兩個(gè)的TCP察覺(jué)到丟包后，把速率各減去一半，你有3.5M，他有0.5M。網(wǎng)絡(luò)不擁塞了，沒(méi)有丟包，那就繼續(xù)增窗。該增多少呢?你的帶寬明顯占優(yōu)勢(shì)，同學(xué)有沒(méi)有可能獲得比你更高的速率呢?怎么樣增才能達(dá)到均分帶寬的目的?現(xiàn)在普遍的增窗策略是“加性增窗”，英文對(duì)應(yīng)“AI”。也就是每條TCP連接在一個(gè)RTT內(nèi)的增量是常數(shù)，假設(shè)這個(gè)加性因子為200K。那接下來(lái)的速率增長(zhǎng)就是：你有3.5+0.2=3.7，同學(xué)有0.5+0.2=0.7.

看到這里，或許有的人就恍然大悟了：這樣增窗，結(jié)果是大家的速率都收斂。也許還有人不明白，那就把速率隨時(shí)間變化的情況列出出來(lái)：

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策略的效果：收斂，到最后公平。也許有的人意猶未盡，那就從公式角度再算一次看看。假設(shè)flow1的初始窗口為c1，flow2的初始窗口為c2。MD減窗過(guò)程中，乘性因子為beta=0.5，也就是遇到丟包，窗口減一半。AI增窗過(guò)程中，加性因子為a。于是有：

c1' = ((c1*0.5 + m*0.2)*0.5 + m*0.2)*0.5 + m*0.2 …………

這里m是變化的，表示增窗的次數(shù)，直到遇到丟包。但是由于帶寬有限，于是m可以視為常數(shù)。

c1'可以用等比數(shù)列求和公式給出，這里就不詳細(xì)計(jì)算了。結(jié)論可以直接告訴大家：

c1'收斂到跟m和beta有關(guān)，跟c1無(wú)關(guān)的常數(shù)。

c2'也類似。

收斂性的證明比較復(fù)雜，我也懶得在博文里講這么學(xué)術(shù)化的事情。參見(jiàn)【注 2】。

看到這里，你也就明白，TCP如何均分帶寬，你同學(xué)又為什么能從你手里搶到帶寬了。至于減窗是不是過(guò)于劇烈，beta能不能設(shè)置得更好，變成動(dòng)態(tài)的，增窗因子能不能設(shè)置更好，變成動(dòng)態(tài)的。以及能不能拋棄AIMD，使用MIMD，在什么網(wǎng)絡(luò)中能這樣做。這些問(wèn)題就不是本文的討論范圍了，也許以后會(huì)講。