TCP擁塞控制

TCP擁塞控制是傳輸控制協議（Transmission Control Protocol，縮寫TCP）避免網路擁塞的演算法，是網際網路上主要的一個擁塞控制措施。它使用一套基於線增積減模式的多樣化網路擁塞控制方法（包括慢啟動和擁塞窗口等模式）來控制擁塞。在網際網路上應用中有相當多的具體實現演算法。

## 運作方法

TCP使用多種擁塞控制策略來避免雪崩式擁塞。TCP會為每條連接維護一個「擁塞窗口」來限制可能在端對端間傳輸的未確認分組總數量。這類似TCP流量控制機制中使用的滑動窗口。TCP在一個連接初始化或超時後使用一種「慢啟動」機制來增加擁塞窗口的大小。它的起始值一般為最大分段大小（Maximum segment size，MSS）的兩倍，雖然名為「慢啟動」，初始值也相當低，但其增長極快：當每個分段得到確認時，擁塞窗口會增加一個MSS，使得在每次往返時間（round-trip time，RTT）內擁塞窗口能高效地雙倍增長。

當擁塞窗口超過慢啟動閾值（ssthresh）時，演算法就會進入一個名為「擁塞避免」的階段。在擁塞避免階段，只要未收到重複確認，擁塞窗口則在每次往返時間內線性增加一個MSS大小。

## 擁塞窗口

在TCP中，擁塞窗口（congestion window）是任何時刻內確定能被發送出去的字節數的控制因素之一，是阻止發送方至接收方之間的鏈路變得擁塞的手段。他是由發送方維護，通過估計鏈路的擁塞程度計算出來的，與由接收方維護的接收窗口大小並不衝突。

當一條連接建立後，每個主機獨立維護一個擁塞窗口並設置值為連接所能承受的MSS的最小倍數，之後的變化依靠線增積減機制來控制，這意味如果所有分段到達接收方和確認包準時地回到發送方，擁塞窗口會增加一定數量。該窗口會保持指數增大，直到發生超時或者超過一個稱為「慢啟動閾值（ssthresh）」的限值。如果發送方到達這個閾值時，每收到一個新確認包，擁塞窗口只按照線性速度增加自身值的倒數。

當發生超時的時候，慢啟動閾值降為超時前擁塞窗口的一半大小、擁塞窗口會降為1個MSS，並且重新回到慢啟動階段。

系統管理員可以設置窗口最大限值，或者調整擁塞窗口的增加量，來對TCP調優。

在流量控制中，接收方通過TCP的「窗口」值（Window Size）來告知發送方，由發送方通過對擁塞窗口和接收窗口的大小比較，來確定任何時刻內需要傳輸的數據量。

## 慢啟動

慢啟動（Slow-start）是用於結合其他階段演算法，來避免發送過多數據到網路中而導致網路擁塞，演算法在中定義。

慢啟動初始啟動時設置擁塞窗口值（cwnd）為1、2、4或10個MSS。擁塞窗口在每接收到一個確認包時增加，每個RTT內成倍增加，當然實際上並不完全是指數增長，因為接收方會延遲發送確認，通常是每接收兩個分段則發送一次確認包。發送速率隨著慢啟動的進行而增加，直到遇到出現丟失、達到慢啟動閾值（ssthresh）、或者接收方的接收窗口進行限制。如果發生丟失，則TCP推斷網絡出現了擁塞，會試圖採取措施來降低網路負載。這些是靠具體使用的TCP擁塞演算法來進行測量判斷。當達到慢啟動閾值（ssthresh）時，慢啟動演算法就會轉換為線性增長的階段，演算法控制每個RTT內擁塞窗口只增加1個分段量。雖然稱為「慢啟動」，但實際上比擁塞控制階段的窗口增加更為激進。

對於處理報文丟失這個事件上，不同擁塞控制演算法表現有所不同：

TCP Tahoe：對於TCP Tahoe演算法，當發生丟失時，會進入「快速重傳」機制，慢啟動閾值設為之前擁塞窗口值的一半，擁塞窗口值降為初始值，重新進入慢啟動階段。當擁塞窗口值達到慢啟動閾值時，每RTT內擁塞窗口增加值則為「MSS除以CWND」的值，所以擁塞窗口按線性速度增加。

TCP Reno：TCP Reno演算法實現了一個名為「快速恢復」的機制，慢啟動閾值設為之前擁塞窗口值的一半，和作為新的擁塞窗口值，並跳過慢啟動階段，直接進入擁塞控制階段。

慢啟動假設分段的未確認是由於網路擁塞造成的，雖然大部分網路的確如此，但也有其他原因，例如一些鏈路質量差的網路，會導致分段包丟失。在一些網路環境，例如無線網絡，慢啟動效率並不好。

慢啟動對於一些短暫的連接性能並不好，一些較舊的網頁瀏覽器會建立大量連續的短暫連結，通過快速開啟和關閉連結來請求獲得文件，這使得大多數連結處於慢啟動模式，導致網頁響應時間差。所以現在新的網頁瀏覽器，會通過向特殊的伺服器，開啟一條連結來請求獲得全部的文件，而避免頻繁新建大量短暫連結。不過這樣對一些非請求網站所提供的服務，例如廣告跟蹤腳本、社交分享功能腳本、網路分析腳本等，並不適用。

## 和式增加，積式減少

和性增長/乘性降低（additive-increase/multiplicative-decrease，AIMD，這裡簡稱「線增積減」）是一種反饋控制演算法，其包含了對擁塞窗口線性增加，和當發生擁塞時對窗口積式減少。多個使用AIMD控制的TCP流最終會收斂到對線路的等量競爭使用。

## 快速重傳

快速重傳（Fast retransmit）是對TCP發送方降低等待重發丟失分段用時的一種改進。TCP發送方每發送一個分段都會啟動一個超時計時器，如果沒能在特定時間內接收到相應分段的確認，發送方就假設這個分段在網路上丟失了，需要重發。這也是 TCP 用來估計 RTT 的測量方法。

重複確認（duplicate cumulative acknowledgements，DupAcks）就是這個階段的基礎，其基於以下過程：如果接收方接收到一個數據分段，就會將該分段的序列號加上數據字節長的值，作為分段確認的確認號，發送回發送方，表示期望發送方發送下一個序列號的分段。但是如果接收方提前收到更下一個序列號的分段——或者說接收到無序到達的分段，即之前期望確認號對應的分段出現接收丟失——接收方需要立即使用之前的確認號發送分段確認。此時如果發送方收到接收方相同確認號的分段確認超過1次，並且該對應序列號的分段超時計時器仍沒超時的話，則這就是出現重複確認，需要進入快速重傳。

快速重傳就是基於以下機制：如果假設重複閾值為3，當發送方收到4次相同確認號的分段確認（第1次收到確認期望序列號，加3次重複的期望序列號確認）時，則可以認為繼續發送更高序列號的分段將會被接受方丟棄，而且會無法有序送達。發送方應該忽略超時計時器的等待重發，立即重發重複分段確認中確認號對應序列號的分段。

## 具體實現演算法

「TCP+演算法名稱」這一TCP演算法命名方式最早出在凱文·福爾（Kevin Fall）和莎莉·弗洛伊德（Sally Floyd）在1996年發布的一篇論文中。

### TCP Tahoe 和 Reno

這兩個演算法是根據其第一次加入到4.3BSD的時間回溯命名的，兩個名字對應自其第一次出現時BSD的代號，而代號分別取自太浩湖（Lake Tahoe）和其附近的城市雷諾市。「Tahoe」演算法實現在4.3BSD-Tahoe中第一次加入，之後在4.3BSD網路發布第一版實現了脫AT&T授權版本，使其能更容易被廣泛再發布與實現。改進版「Reno」在4.3BSD-Reno中實現，並之後通過「4.3BSD網路發布第二版」和4.4BSD-Lite發布。

兩者演算法大致一致，對於丟包事件判斷都是以重傳超時（retransmission timeout，RTO）和重複確認為條件，但是對於重複確認的處理，兩者有所不同：

- Tahoe：如果收到三次重複確認——即第四次收到相同確認號的分段確認，並且分段對應包無負載分段和無改變接收窗口——的話，Tahoe演算法則進入快速重傳，將慢啟動閾值改為當前擁塞窗口的一半，將擁塞窗口降為1個MSS，並重新進入慢啟動階段。Kurose & Ross 2008, p. 284.
- Reno：如果收到三次重複確認，Reno演算法則進入快速重傳，只將擁塞窗口減半來跳過慢啟動階段，將慢啟動閾值設為當前新的擁塞窗口值，進入一個稱為「快速恢復」的新設計階段。

對於RTO，兩個演算法都是將擁塞窗口降為1個MSS，然後進入慢啟動階段。

#### 快速恢復

快速恢復（Fast recovery）是Reno演算法新引入的一個階段，在將丟失的分段重傳後，啟動一個超時定時器，並等待該丟失分段包的分段確認後，再進入擁塞控制階段。如果仍然超時，則回到慢啟動階段。

### TCP Vegas

至1990年代中期，TCP量度延遲和RTT都是以傳輸緩存中最後一個被傳送的分段包為準。亞利桑那大學的研究人員拉里·彼得森和勞倫斯·布拉科夫提出了新的TCP擁塞演算法「TCP Vegas」，其實通過度量傳輸緩存中每個傳送分段包來代替只量度一個分段包，根據每次度量的平均值來增加擁塞窗口。該演算法取名自內華達州最大的城市拉斯維加斯。不過由於一些資源公平性原因，該演算法並沒有在彼得森的實驗室之外廣泛部署。一些研究認為該演算法和其他擁塞演算法混合使用，可能會導致性能競爭不及其他演算法。在各種TCP擁塞演算法的比較研究中，Vegas被認為是最平滑的控制演算法，其次為CUBIC。

DD-WRT在v24 SP2開始將該演算法作為其默認的TCP擁塞控制演算法。

### TCP New Reno

TCP New Reno是對TCP Reno中快速恢復階段的重傳進行改善的一種改進演算法，其定義於，覆蓋了原有在和的舊定義。

在Reno的快速恢復中，一旦出現3次重複確認，TCP發送方會重發重複確認對應序列號的分段並設置定時器等待該重發分段包的分段確認包，當該分段確認包收到後，就立即退出快速恢復階段，進入擁塞控制階段，但如果某個導致重複確認的分段包到遇到重複確認期間所發送的分段包存在多個丟失的話，則這些丟失只能等待超時重發，並且導致擁塞窗口多次進入擁塞控制階段而多次下降。而New Reno的快速恢復中，一旦出現3次重複確認，TCP發送方先記下3次重複確認時已發送但未確認的分段的最大序列號，然後重發重複確認對應序列號的分段包。如果只有該重複確認的分段丟失，則接收方接收該重發分段包後，會立即返回最大序列號的分段確認包，從而完成重發；但如果重複確認期間的發送包有多個丟失，接收方在接收該重發分段後，會返回非最大序列號的分段確認包，從而發送方繼續保持重發這些丟失的分段，直到最大序列號的分段確認包的返回，才退出快速恢復階段。

New Reno在低錯誤率時運行效率和「選擇確認」（Selective ACKnowledgement，SACK）相當，在高錯誤率仍優於Reno。

### TCP Hybla

TCP Hybla旨在消除由於高延遲地面線路或者衛星無線鏈路下導致的RTT過長而對TCP連結的影響。它通過對擁塞窗口動態分析來修改，來減少對RTT的性能依賴。

### TCP BIC 和 CUBIC

TCP BIC（Binary Increase Congestion control）旨在優化高速高延遲網路（即根據所定義的「長肥網路」（long fat network，LFN））的擁塞控制，其擁塞窗口演算法使用二分搜索算法嘗試找到能長時間保持擁塞窗口最大值的值。Linux內核在2.6.8至2.6.18使用該演算法作為默認TCP擁塞演算法。

CUBIC則是比BIC更溫和和系統化的分支版本，其使用三次函數代替二分演算法作為其擁塞窗口演算法，並且使用函數拐點作為擁塞窗口的設置值。Linux內核在2.6.19後使用該演算法作為默認TCP擁塞演算法。

### TCP Westwood和Westwood+

TCP Westwood改良自New Reno，不同於以往其他擁塞控制演算法使用丟失來測量，其通過對確認包測量來確定一個「合適的發送速度」，並以此調整擁塞窗口和慢啟動閾值。其改良了慢啟動階段演算法為「敏捷探測（Agile Probing）」，和設計了一種持續探測擁塞窗口的方法來控制進入「敏捷探測」，使連結儘可能地使用更多的帶寬。Westwood+使用更長的帶寬估計間隔和優化的濾波器來修正Westwood對ACK壓縮場景對帶寬估計過高的問題。通過以上改良，TCP Westwood系列演算法在有線網路和無線網絡的擁塞控制上取得平衡，尤其研究中針對於無線通信網路上。

### Compound TCP

複合TCP（Compound TCP）是微軟自己實現的TCP擁塞控制演算法，通過同時維護兩個擁塞窗口，來實現在長肥網路有較好的性能而又不損失公平性。該演算法在Windows Vista和Windows Server 2008開始廣泛部署，並通過補丁的方式回溯支持到Windows XP和Windows Server 2003。在Linux上也有一個舊版本的移植實現。

### TCP PRR

TCP PRR（TCP Proportional Rate Reduction）是旨在恢復期間提高發送數據的準確性。該演算法確保恢復後的擁塞窗口大小儘可能接近慢啟動閾值。在Google進行的測試中，能將平均延遲降低3~10%，恢復的超時減少5%。PRR演算法之後作為Linux內核3.2版本的默認擁塞演算法。

### TCP BBR

TCP BBR（Bottleneck Bandwidth and Round-trip propagation time）是由Google設計，於2016年發布的擁塞演算法。以往大部分擁塞演算法是基於丟包來作為降低傳輸速率的信號，而BBR則基於模型主動探測。該演算法使用網路最近出站數據分組當時的最大帶寬和往返時間來建立網路的顯式模型。數據包傳輸的每個累積或選擇性確認用於生成記錄在數據包傳輸過程和確認返回期間的時間內所傳送數據量的採樣率。該演算法認為隨著網路接口控制器逐漸進入千兆速度時，與緩衝膨脹相關的延遲相比丟包更應該被認為是識別擁塞的主要決定因素，所以基於延遲模型的擁塞控制演算法（如BBR）會有更高的吞吐量和更低的延遲，可以用BBR來替代其他流行的擁塞演算法，例如CUBIC。Google在YouTube上應用該演算法，將全球平均的YouTube網路吞吐量提高了4%，在一些國家超過了14%。

BBR之後移植入Linux內核4.9版本，並且對於QUIC可用。

BBR效率很高，速度也很快，但是它與非BBR的流的公平性有爭議。雖然谷歌的展示顯示 BBR 與 CUBIC 共存良好，但像傑夫·休斯頓和霍克、布利斯和齊特巴特等研究者發現它對其他流不公平，並且不可擴展。霍克等人還發現，在Linux 4.9的BBR實現中「存在一些嚴重的固有問題，如排隊延遲增加、不公平和大量數據包丟失」。

索海爾·阿巴斯洛等人（C2TCP的作者）指出，BBR在動態環境中表現不佳，比如蜂窩網絡。他們還表明BBR存在不公平問題。例如，當一個CUBIC流（在Linux、Android和MacOS中是默認的TCP實現）與網路中的BBR流共存時，BBR流可以支配 CUBIC 流並從中獲得整個鏈路帶寬。

TCP BBR 擁塞控制演算法是由 Google 開發並開源的，已經集成到了 Linux 內核中。只需簡單啟用即可對當前網路進行優化。

## 外部連結

- 一些關於擁塞控制的論文
- TCP Vegas的介紹主頁
- TCP Congestion Handling and Congestion Avoidance Algorithms – The TCP/IP Guide
- TCP擁塞控制的四大金剛--慢啟動，擁塞避免，快速重傳和快速恢復
- TCP擁塞控制：Tahoe、Reno、NewReno與SACK演算法概述與比較