轉自：https://mp.weixin.qq.com/s/NIFandX8w-Cynnbl-f2Lwg
一、前言
TCP 通過維護一個擁塞視窗來進行擁塞控制，擁塞控制的原則是，隻要網絡中沒有出現擁塞，擁塞視窗的值就可以再增大一些，以便把更多的資料包發送出去，但隻要網絡出現擁塞，擁塞視窗的值就應該減小一些，以減少注入到網絡中的資料包數。
TCP 擁塞控制算法發展的過程中出現了如下幾種不同的思路：
- 基于丢包的擁塞控制：将丢包視為出現擁塞，采取緩慢探測的方式，逐漸增大擁塞視窗，當出現丢包時，将擁塞視窗減小，如 Reno、Cubic 等。
- 基于時延的擁塞控制：将時延增加視為出現擁塞，延時增加時增大擁塞視窗，延時減小時減小擁塞視窗，如 Vegas、FastTCP 等。
- 基于鍊路容量的擁塞控制：實時測量網絡帶寬和時延，認為網絡上封包總量大于帶寬時延乘積時出現了擁塞，如 BBR。
- 基于學習的擁塞控制：沒有特定的擁塞信号，而是借助評價函數，基于訓練資料，使用機器學習的方法形成一個控制政策，如 Remy。
擁塞控制算法的核心是選擇一個有效的政策來控制擁塞視窗的變化，下面介紹幾種經典的擁塞控制算法。
二、Vegas
Vegas[1] 将時延 RTT 的增加作為網絡出現擁塞的信号，RTT 增加，擁塞視窗減小，RTT 減小，擁塞視窗增加。具體來說，Vegas 通過比較實際吞吐量和期望吞吐量來調節擁塞視窗的大小，
期望吞吐量：Expected = cwnd / BaseRTT，
實際吞吐量：Actual = cwnd / RTT，
diff = (Expected-Actual) * BaseRTT，
BaseRTT 是所有觀測來回響應時間的最小值，一般是建立連接配接後所發的第一個資料包的 RTT，cwnd 是目前的擁塞視窗的大小。Vegas 定義了兩個門檻值 a，b，當 diff > b 時，擁塞視窗減小，當 a <= diff <=b 時，擁塞視窗不變，當 diff < a 時，擁塞視窗增加。
Vegas 算法采用 RTT 的改變來判斷網絡的可用帶寬，能精确地測量網絡的可用帶寬，效率比較好。但是，網絡中 Vegas 與其它算法共存的情況下，基于丢包的擁塞控制算法會嘗試填滿網絡中的緩沖區，導緻 Vegas 計算的 RTT 增大，進而降低擁塞視窗，使得傳輸速度越來越慢，是以 Vegas 未能在 Internet 上普遍采用。
适用場景：
适用于網絡中隻存在 Vegas 一種擁塞控制算法，競争公平的情況。
三、Reno
Reno[2] 将擁塞控制的過程分為四個階段：慢啟動、擁塞避免、快重傳和快恢複，是現有的衆多擁塞控制算法的基礎，下面詳細說明這幾個階段。
慢啟動階段，在沒有出現丢包時每收到一個 ACK 就将擁塞視窗大小加一（機關是 MSS，最大單個封包段長度），每輪次發送視窗增加一倍，呈指數增長，若出現丢包，則将擁塞視窗減半，進入擁塞避免階段；當視窗達到慢啟動門檻值或出現丢包時，進入擁塞避免階段，視窗每輪次加一，呈線性增長；當收到對一個封包的三個重複的 ACK 時，認為這個封包的下一個封包丢失了，進入快重傳階段，立即重傳丢失的封包，而不是等待逾時重傳；快重傳完成後進入快恢複階段，将慢啟動門檻值修改為目前擁塞視窗值的一半，同時擁塞視窗值等于慢啟動門檻值，然後進入擁塞避免階段，重複上訴過程。Reno 擁塞控制過程如圖 1 所示。
圖1、TCP Reno擁塞控制過程
Reno 算法将收到 ACK 這一信号作為擁塞視窗增長的依據，在早期低帶寬、低延遲時間的網絡中能夠很好的發揮作用，但是随着網絡帶寬和延時的增加，Reno 的缺點就漸漸展現出來了，發送端從發送封包到收到 ACK 經曆一個 RTT，在高帶寬延時（High Bandwidth-Delay Product，BDP）網絡中，RTT 很大，導緻擁塞視窗增長很慢，傳輸速度需要經過很長時間才能達到最大帶寬，導緻帶寬使用率降低。
适用場景：
适用于低延時、低帶寬的網絡。
四、Cubic
Cubic[3] 是 Linux 核心 2.6 之後的預設 TCP 擁塞控制算法，使用一個立方函數（cubic function）
作為擁塞視窗的增長函數，其中，C 是調節因子，t 是從上一次縮小擁塞視窗經過的時間，Wmax 是上一次發生擁塞時的視窗大小，
β是乘法減小因子。從函數中可以看出擁塞視窗的增長不再與 RTT 有關，而僅僅取決上次發生擁塞時的最大視窗和距離上次發生擁塞的時間間隔值。
Cubic 擁塞視窗增長曲線如下，凸曲線部分為穩定增長階段，凹曲線部分為最大帶寬探測階段。如圖 2 所示，在剛開始時，擁塞視窗增長很快，在接近 Wmax 口時，增長速度變的平緩，避免流量突增而導緻丢包；在 Wmax 附近，擁塞視窗不再增加；之後開始緩慢地探測網絡最大吞吐量，保證穩定性（在 Wmax 附近容易出現擁塞），在遠離 Wmax 後，增大視窗增長的速度，保證了帶寬的使用率。
圖 2、TCP Cubic 擁塞視窗增長函數
當出現丢包時，将擁塞視窗進行乘法減小，再繼續開始上述增長過程。此方式可以使得擁塞視窗一直維持在 Wmax 附近，進而保證了帶寬的使用率。Cubic 的擁塞控制過程如圖 3 所示：
圖 3、TCP Cubic 擁塞控制過程
Cubic 算法的優點在于隻要沒有出現丢包，就不會主動降低自己的發送速度，可以最大程度的利用網絡剩餘帶寬，提高吞吐量，在高帶寬、低丢包率的網絡中可以發揮較好的性能。
但是，Cubic 同之前的擁塞控制算法一樣，無法區分擁塞丢包和傳輸錯誤丢包，隻要發現丢包，就會減小擁塞視窗，降低發送速率，而事實上傳輸錯誤丢包時網絡不一定發生了擁塞，但是傳輸錯誤丢包的機率很低，是以對 Cubic 算法的性能影響不是很大。
Cubic 算法的另一個不足之處是過于激進，在沒有出現丢包時會不停地增加擁塞視窗的大小，向網絡注入流量，将網絡裝置的緩沖區填滿，出現 Bufferbloat（緩沖區膨脹）。由于緩沖區長期趨于飽和狀态，新進入網絡的的資料包會在緩沖區裡排隊，增加無謂的排隊時延，緩沖區越大，時延就越高。另外 Cubic 算法在高帶寬使用率的同時依然在增加擁塞視窗，間接增加了丢包率，造成網絡抖動加劇。
适用場景：
适用于高帶寬、低丢包率網絡，能夠有效利用帶寬。
五、BBR
BBR[4] 是谷歌在 2016 年提出的一種新的擁塞控制算法，已經在 Youtube 伺服器和谷歌跨資料中心廣域網上部署，據 Youtube 官方資料稱，部署 BBR 後，在全球範圍内通路 Youtube 的延遲降低了 53%，在時延較高的開發中國家，延遲降低了 80%。目前 BBR 已經內建到 Linux 4.9 以上版本的核心中。
BBR 算法不将出現丢包或時延增加作為擁塞的信号，而是認為當網絡上的資料包總量大于瓶頸鍊路帶寬和時延的乘積時才出現了擁塞，是以 BBR 也稱為基于擁塞的擁塞控制算法（Congestion-Based Congestion Control）。BBR 算法周期性地探測網絡的容量，交替測量一段時間内的帶寬極大值和時延極小值，将其乘積作為作為擁塞視窗大小（交替測量的原因是極大帶寬和極小時延不可能同時得到，帶寬極大時網絡被填滿造成排隊，時延必然極大，時延極小時需要資料包不被排隊直接轉發，帶寬必然極小），使得擁塞視窗始的值始終與網絡的容量保持一緻。
由于 BBR 的擁塞視窗是精确測量出來的，不會無限的增加擁塞視窗，也就不會将網絡裝置的緩沖區填滿，避免了出現 Bufferbloat 問題，使得時延大大降低。如圖 4 所示，網絡緩沖區被填滿時時延為 250ms，Cubic 算法會繼續增加擁塞視窗，使得時延持續增加到 500ms 并出現丢包，整個過程 Cubic 一直處于高時延狀态，而 BBR 由于不會填滿網絡緩沖區，時延一直處于較低狀态。
圖 4、Cubic 和 BBR RTT 對比
由于 BBR 算法不将丢包作為擁塞信号，是以在丢包率較高的網絡中，BBR 依然有極高的吞吐量，如圖 5 所示，在 1% 丢包率的網絡環境下，Cubic 的吞吐量已經降低 90% 以上，而 BBR 的吞吐量幾乎沒有受到影響，當丢包率大于 15% 時，BBR 的吞吐量才大幅下降。
圖 5、Cubic 和 BBR 傳輸速率與丢包率關系對比
BBR 算法是回報驅動的，有自主調節機制，不受 TCP 擁塞控制狀态機的控制，通過測量網絡容量來調整擁塞視窗，發送速率由自己掌控，而傳統的擁塞控制算法隻負責計算擁塞視窗，而不管發送速率（pacing rate），怎麼發由 TCP 自己決定，這樣會在瓶頸帶寬附近因發送速率的激增導緻資料包排隊或出現丢包。
經過測試，在高延時、高丢包率的環境下，BBR 相對于 Cubic 算法在傳輸速度上有較大的提升，具體的測試結果表 1 所示：
BBR 算法的不足之處在于裝置隊列緩存較大時，BBR 可能會競争不過 Cubic 等比較激進算法，原因是 BBR 不主動去占據隊列緩存，如果 Cubic 的流量長期占據隊列緩存，會使得 BBR 在多個周期内測量的極小 RTT 增大，進而使 BBR 的帶寬減小。
适用場景：
适用于高帶寬、高時延、有一定丢包率的長肥網絡，可以有效降低傳輸時延，并保證較高的吞吐量。
六、Remy
Remy[5] 也稱為計算機生成的擁塞控制算法（computer-generated congestion-control algorithm），采用機器學習的方式生成擁塞控制算法模型。通過輸入各種參數模型（如瓶頸鍊路速率、時延、瓶頸鍊路上的發送者數量等），使用一個目标函數定量判斷算法的優劣程度，在生成算法的過程中，針對不同的網絡狀态采用不同的方式調整擁塞視窗，反複修改調節方式，直到目标函數最優，最終會生成一個網絡狀态到調節方式的映射表，在真實的網絡中，根據特定的網絡環境從映射表直接選取擁塞視窗的調節方式。
Remy 試圖屏蔽底層網絡環境的差異，采用一個通用的擁塞控制算法模型來處理不同的網絡環境。這種方式比較依賴輸入的訓練集（曆史網絡模型），如果訓練集能夠全面覆寫所有可能出現的網絡環境及擁塞調節算法，Remy 算法在應用到真實的網絡環境中時能夠表現的很好，但是如果真實網絡與訓練網絡差異較大，Remy 算法的性能會比較差。
适用場景：
網絡環境為複雜的異構網絡，希望計算機能夠針對不同網絡場景自動選擇合适的擁塞控制方式，要求現有的網絡模型能夠覆寫所有可能出現情況。
七、總結
每一種擁塞控制算法都是在一定的網絡環境下誕生的，适合特定的場景，沒有一種一勞永逸的算法。網絡環境越來越複雜，擁塞控制算法也在不斷地演進。本文不是要去選擇一個最好的算法，隻是簡單介紹了幾種典型算法的設計思路、優缺點以及适用場景，希望能給大家帶來一些啟發。
參考論文：
[1] S.O. L. Brakmo and L. Peterson. TCP Vegas: New techniques for congestiondetection and avoidance. In SIGCOMM, 1994. Proceedings. 1994 InternationalConference on. ACM, 1994.
[2] V.Jacobson, “Congestion avoidance and control,” in ACM SIGCOMM ComputerCommunication Review, vol. 18. ACM, 1988, pp. 314–329.
[3] L. X. I. R. Sangtae Ha. Cubic: A new TCP -friendlyhigh-speed TCP variant. In SIGOPS-OSR, July 2008. ACM, 2008.
[4] C.S. G. S. H. Y. Neal Cardwell, Yuchung Cheng and V. Jacobson. BBR:congestion-based congestion control. ACM Queue, 14(5):20{53, 2016.
[5] K.Winstein and H. Balakrishnan. TCP Ex Machina: Computer-generated Congestion Control.In Proceedings of the ACM SIGCOMM 2013 Conference, 2013.