tcp擁塞避免與控制

說到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中已經證明了收斂性。