速讀原著-TCP/IP(擁塞避免演算法)
- 2020 年 3 月 12 日
- 筆記
第21章 TCP的超時與重傳
21.6 擁塞避免演算法
在第2 0 . 6節介紹的慢啟動演算法是在一個連接上發起數據流的方法，但有時我們會達到中間路由器的極限，此時分組將被丟棄。擁塞避免演算法是一種處理丟失分組的方法。該方法的具體描述見 [Jacobson 1988]。
該演算法假定由於分組受到損壞引起的丟失是非常少的（遠小於 1 %），因此分組丟失就意味著在源主機和目的主機之間的某處網路上發生了擁塞。有兩種分組丟失的指示：發生超時和接收到重複的確認（我們在 2 1 . 5節看到這種現象。如果使用超時作為擁塞指示，則需要使用一個好的RT T演算法，正如在2 1 . 3節中描述的那樣）。
擁塞避免演算法和慢啟動演算法是兩個目的不同、獨立的演算法。但是當擁塞發生時，我們希望降低分組進入網路的傳輸速率，於是可以調用慢啟動來作到這一點。在實際中這兩個演算法通常在一起實現。
擁塞避免演算法和慢啟動演算法需要對每個連接維持兩個變數：一個擁塞窗口 c w n d和一個慢啟動門限s s t h re s h。這樣得到的演算法的工作過程如下：
- 對一個給定的連接，初始化 c w n d為1個報文段，s s t h re s h為6 5 5 3 5個位元組。
- TCP輸出常式的輸出不能超過 c w n d和接收方通告窗口的大小。擁塞避免是發送方使用的流量控制，而通告窗口則是接收方進行的流量控制。前者是發送方感受到的網路擁塞的估計，而後者則與接收方在該連接上的可用快取大小有關。
- 當擁塞發生時（超時或收到重複確認），s s t h re s h被設置為當前窗口大小的一半（ c w n d和接收方通告窗口大小的最小值，但最少為 2個報文段）。此外，如果是超時引起了擁塞，則c w n d被設置為1個報文段（這就是慢啟動）。
- 當新的數據被對方確認時，就增加 c w n d，但增加的方法依賴於我們是否正在進行慢啟動或擁塞避免。如果 c w n d小於或等於s s t h re s h，則正在進行慢啟動，否則正在進行擁塞避免。慢啟動一直持續到我們回到當擁塞發生時所處位置的半時候才停止（因為我們記錄了在步驟 2中給我們製造麻煩的窗口大小的一半），然後轉為執行擁塞避免。
慢啟動演算法初始設置 c w n d為1個報文段，此後每收到一個確認就加 1。正如2 0 . 6節描述的那樣，這會使窗口按指數方式增長：發送 1個報文段，然後是2個，接著是4個……。
擁塞避免演算法要求每次收到一個確認時將 c w n d增加1 /c w n d。與慢啟動的指數增加比起來，這是一種加性增長(additive increase)。我們希望在一個往返時間內最多為 c w n d增加1個報文段（不管在這個 RT T中收到了多少個 A C K），然而慢啟動將根據這個往返時間中所收到的確認的個數增加c w n d。
所有的4 . 3 B S D版本和4 . 4 B S D都在擁塞避免中將增加值不正確地設置為 1個報文段的一小部分（即一個報文段的大小除以 8），這是錯誤的，並在以後的版本中不再使用[Floyd 1994]。但是，為了和（不正確的）實現的結果對應，我們在將來的計算中給出了這個細節。
在[Leffler et al. 1989]中介紹的4.3BSD Tahoe版本僅在對方處於一個不同的網路上時才進行慢啟動。而4.3BSD Reno版本改變了這種做法，因此，慢啟動總是被執行。圖2 1 – 8是慢啟動和擁塞避免的一個可視化描述。我們以段為單位來顯示 c w n d和s s t h re s h，但它們實際上都是以位元組為單位進行維護的。
在該圖中，假定當 c w n d為3 2個報文段時就會發生擁塞。於是設置 s s t h re s h為1 6個報文段，而c w n d為1個報文段。在時刻 0發送了一個報文段，並假定在時刻 1接收到它的 A C K，此時c w n d增加為2。接著發送了2個報文段，並假定在時刻 2接收到它們的A C K，於是c w n d增加為4（對每個A C K增加1次）。這種指數增加演算法一直進行到在時刻 3和4之間收到8個A C K後c w n d等 於s s t h re s h時才停止，從該時刻起， c w n d以線性方式增加，在每個往返時間內最多增加 1個報文段。
正如我們在這個圖中看到的那樣，術語「慢啟動」並不完全正確。它只是採用了比引起擁塞更慢些的分組傳輸速率，但在慢啟動期間進入網路的分組數增加的速率仍然是在增加的。只有在達到s s t h re s h擁塞避免演算法起作用時，這種增加的速率才會慢下來。
