TCP通過(guò)維護(hù)一個(gè)擁塞窗口來(lái)進(jìn)行擁塞控制，擁塞控制的原則是，只要網(wǎng)絡(luò)中沒(méi)有出現(xiàn)擁塞，擁塞窗口的值就可以再增大一些，以便把更多的數(shù)據(jù)包發(fā)送出去，但只要網(wǎng)絡(luò)出現(xiàn)擁塞，擁塞窗口的值就應(yīng)該減小一些，以減少注入到網(wǎng)絡(luò)中的數(shù)據(jù)包數(shù)。
TCP擁塞控制算法發(fā)展的過(guò)程中出現(xiàn)了如下幾種不同的思路：
- 基于丟包的擁塞控制：將丟包視為出現(xiàn)擁塞，采取緩慢探測(cè)的方式，逐漸增大擁塞窗口，當(dāng)出現(xiàn)丟包時(shí)，將擁塞窗口減小，如Reno、Cubic等。
- 基于時(shí)延的擁塞控制：將時(shí)延增加視為出現(xiàn)擁塞，延時(shí)增加時(shí)增大擁塞窗口，延時(shí)減小時(shí)減小擁塞窗口，如Vegas、FastTCP等。
- 基于鏈路容量的擁塞控制：實(shí)時(shí)測(cè)量網(wǎng)絡(luò)帶寬和時(shí)延，認(rèn)為網(wǎng)絡(luò)上報(bào)文總量大于帶寬時(shí)延乘積時(shí)出現(xiàn)了擁塞，如BBR。
- 基于學(xué)習(xí)的擁塞控制：沒(méi)有特定的擁塞信號(hào)，而是借助評(píng)價(jià)函數(shù)，基于訓(xùn)練數(shù)據(jù)，使用機(jī)器學(xué)習(xí)的方法形成一個(gè)控制策略，如Remy。
擁塞控制算法的核心是選擇一個(gè)有效的策略來(lái)控制擁塞窗口的變化，下面介紹幾種經(jīng)典的擁塞控制算法。
Vegas
Vegas[1]將時(shí)延RTT的增加作為網(wǎng)絡(luò)出現(xiàn)擁塞的信號(hào)，RTT增加，擁塞窗口減小，RTT減小，擁塞窗口增加。具體來(lái)說(shuō)，Vegas通過(guò)比較實(shí)際吞吐量和期望吞吐量來(lái)調(diào)節(jié)擁塞窗口的大小，期望吞吐量：Expected = cwnd / BaseRTT，實(shí)際吞吐量：Actual = cwnd / RTT，diff = (Expected-Actual) * BaseRTT，BaseRTT是所有觀測(cè)來(lái)回響應(yīng)時(shí)間的最小值，一般是建立連接后所發(fā)的第一個(gè)數(shù)據(jù)包的RTT，cwnd是目前的擁塞窗口的大小。Vegas定義了兩個(gè)閾值a，b，當(dāng)diff > b時(shí)，擁塞窗口減小，當(dāng)a <= diff <=b時(shí)，擁塞窗口不變，當(dāng)diff < a時(shí)，擁塞窗口增加。
Vegas算法采用RTT的改變來(lái)判斷網(wǎng)絡(luò)的可用帶寬，能精確地測(cè)量網(wǎng)絡(luò)的可用帶寬，效率比較好。但是，網(wǎng)絡(luò)中Vegas與其它算法共存的情況下，基于丟包的擁塞控制算法會(huì)嘗試填滿網(wǎng)絡(luò)中的緩沖區(qū)，導(dǎo)致Vegas計(jì)算的RTT增大，進(jìn)而降低擁塞窗口，使得傳輸速度越來(lái)越慢，因此Vegas未能在Internet上普遍采用。
適用場(chǎng)景：適用于網(wǎng)絡(luò)中只存在Vegas一種擁塞控制算法，競(jìng)爭(zhēng)公平的情況。
Reno
Reno[2]將擁塞控制的過(guò)程分為四個(gè)階段：慢啟動(dòng)、擁塞避免、快重傳和快恢復(fù)，是現(xiàn)有的眾多擁塞控制算法的基礎(chǔ)，下面詳細(xì)說(shuō)明這幾個(gè)階段。
慢啟動(dòng)階段，在沒(méi)有出現(xiàn)丟包時(shí)每收到一個(gè)ACK就將擁塞窗口大小加一（單位是MSS，最大單個(gè)報(bào)文段長(zhǎng)度），每輪次發(fā)送窗口增加一倍，呈指數(shù)增長(zhǎng)，若出現(xiàn)丟包，則將擁塞窗口減半，進(jìn)入擁塞避免階段；當(dāng)窗口達(dá)到慢啟動(dòng)閾值或出現(xiàn)丟包時(shí)，進(jìn)入擁塞避免階段，窗口每輪次加一，呈線性增長(zhǎng)；當(dāng)收到對(duì)一個(gè)報(bào)文的三個(gè)重復(fù)的ACK時(shí)，認(rèn)為這個(gè)報(bào)文的下一個(gè)報(bào)文丟失了，進(jìn)入快重傳階段，立即重傳丟失的報(bào)文，而不是等待超時(shí)重傳；快重傳完成后進(jìn)入快恢復(fù)階段，將慢啟動(dòng)閾值修改為當(dāng)前擁塞窗口值的一半，同時(shí)擁塞窗口值等于慢啟動(dòng)閾值，然后進(jìn)入擁塞避免階段，重復(fù)上訴過(guò)程。
Reno算法將收到ACK這一信號(hào)作為擁塞窗口增長(zhǎng)的依據(jù)，在早期低帶寬、低時(shí)延的網(wǎng)絡(luò)中能夠很好的發(fā)揮作用，但是隨著網(wǎng)絡(luò)帶寬和延時(shí)的增加，Reno的缺點(diǎn)就漸漸體現(xiàn)出來(lái)了，發(fā)送端從發(fā)送報(bào)文到收到ACK經(jīng)歷一個(gè)RTT，在高帶寬延時(shí)（High Bandwidth-Delay Product，BDP）網(wǎng)絡(luò)中，RTT很大，導(dǎo)致?lián)砣翱谠鲩L(zhǎng)很慢，傳輸速度需要經(jīng)過(guò)很長(zhǎng)時(shí)間才能達(dá)到最大帶寬，導(dǎo)致帶寬利用率將低。
適用場(chǎng)景：適用于低延時(shí)、低帶寬的網(wǎng)絡(luò)。
Cubic
Cubic[3]是Linux內(nèi)核2.6之后的默認(rèn)TCP擁塞控制算法，使用一個(gè)立方函數(shù)（cubic function）
作為擁塞窗口的增長(zhǎng)函數(shù)，其中，C是調(diào)節(jié)因子，t是從上一次縮小擁塞窗口經(jīng)過(guò)的時(shí)間，Wmax是上一次發(fā)生擁塞時(shí)的窗口大小
，β是乘法減小因子。從函數(shù)中可以看出擁塞窗口的增長(zhǎng)不再與RTT有關(guān)，而僅僅取決上次發(fā)生擁塞時(shí)的最大窗口和距離上次發(fā)生擁塞的時(shí)間間隔值。
Cubic擁塞窗口增長(zhǎng)曲線如下，凸曲線部分為穩(wěn)定增長(zhǎng)階段，凹曲線部分為最大帶寬探測(cè)階段。如圖2所示，在剛開(kāi)始時(shí)，擁塞窗口增長(zhǎng)很快，在接近Wmax口時(shí)，增長(zhǎng)速度變的平緩，避免流量突增而導(dǎo)致丟包；在Wmax附近，擁塞窗口不再增加；之后開(kāi)始緩慢地探測(cè)網(wǎng)絡(luò)最大吞吐量，保證穩(wěn)定性（在Wmax附近容易出現(xiàn)擁塞），在遠(yuǎn)離Wmax后，增大窗口增長(zhǎng)的速度，保證了帶寬的利用率。
當(dāng)出現(xiàn)丟包時(shí)，將擁塞窗口進(jìn)行乘法減小，再繼續(xù)開(kāi)始上述增長(zhǎng)過(guò)程。此方式可以使得擁塞窗口一直維持在Wmax附近，從而保證了帶寬的利用率。
Cubic算法的優(yōu)點(diǎn)在于只要沒(méi)有出現(xiàn)丟包，就不會(huì)主動(dòng)降低自己的發(fā)送速度，可以最大程度的利用網(wǎng)絡(luò)剩余帶寬，提高吞吐量，在高帶寬、低丟包率的網(wǎng)絡(luò)中可以發(fā)揮較好的性能。
但是，Cubic同之前的擁塞控制算法一樣，無(wú)法區(qū)分擁塞丟包和傳輸錯(cuò)誤丟包，只要發(fā)現(xiàn)丟包，就會(huì)減小擁塞窗口，降低發(fā)送速率，而事實(shí)上傳輸錯(cuò)誤丟包時(shí)網(wǎng)絡(luò)不一定發(fā)生了擁塞，但是傳輸錯(cuò)誤丟包的概率很低，所以對(duì)Cubic算法的性能影響不是很大。
Cubic算法的另一個(gè)不足之處是過(guò)于激進(jìn)，在沒(méi)有出現(xiàn)丟包時(shí)會(huì)不停地增加擁塞窗口的大小，向網(wǎng)絡(luò)注入流量，將網(wǎng)絡(luò)設(shè)備的緩沖區(qū)填滿，出現(xiàn)Bufferbloat（緩沖區(qū)膨脹）。由于緩沖區(qū)長(zhǎng)期趨于飽和狀態(tài)，新進(jìn)入網(wǎng)絡(luò)的的數(shù)據(jù)包會(huì)在緩沖區(qū)里排隊(duì)，增加無(wú)謂的排隊(duì)時(shí)延，緩沖區(qū)越大，時(shí)延就越高。另外Cubic算法在高帶寬利用率的同時(shí)依然在增加擁塞窗口，間接增加了丟包率，造成網(wǎng)絡(luò)抖動(dòng)加劇。
適用場(chǎng)景：適用于高帶寬、低丟包率網(wǎng)絡(luò)，能夠有效利用帶寬。
BBR
BBR[4]是谷歌在2016年提出的一種新的擁塞控制算法，已經(jīng)在Youtube服務(wù)器和谷歌跨數(shù)據(jù)中心廣域網(wǎng)上部署，據(jù)Youtube官方數(shù)據(jù)稱，部署B(yǎng)BR后，在全球范圍內(nèi)訪問(wèn)Youtube的延遲降低了53%，在時(shí)延較高的發(fā)展中國(guó)家，延遲降低了80%。目前BBR已經(jīng)集成到Linux 4.9以上版本的內(nèi)核中。
BBR算法不將出現(xiàn)丟包或時(shí)延增加作為擁塞的信號(hào)，而是認(rèn)為當(dāng)網(wǎng)絡(luò)上的數(shù)據(jù)包總量大于瓶頸鏈路帶寬和時(shí)延的乘積時(shí)才出現(xiàn)了擁塞，所以BBR也稱為基于擁塞的擁塞控制算法（Congestion-Based Congestion Control）。BBR算法周期性地探測(cè)網(wǎng)絡(luò)的容量，交替測(cè)量一段時(shí)間內(nèi)的帶寬極大值和時(shí)延極小值，將其乘積作為作為擁塞窗口大?。ń惶鏈y(cè)量的原因是極大帶寬和極小時(shí)延不可能同時(shí)得到，帶寬極大時(shí)網(wǎng)絡(luò)被填滿造成排隊(duì)，時(shí)延必然極大，時(shí)延極小時(shí)需要數(shù)據(jù)包不被排隊(duì)直接轉(zhuǎn)發(fā)，帶寬必然極小），使得擁塞窗口始的值始終與網(wǎng)絡(luò)的容量保持一致。
由于BBR的擁塞窗口是精確測(cè)量出來(lái)的，不會(huì)無(wú)限的增加擁塞窗口，也就不會(huì)將網(wǎng)絡(luò)設(shè)備的緩沖區(qū)填滿，避免了出現(xiàn)Bufferbloat問(wèn)題，使得時(shí)延大大降低。如圖4所示，網(wǎng)絡(luò)緩沖區(qū)被填滿時(shí)時(shí)延為250ms，Cubic算法會(huì)繼續(xù)增加擁塞窗口，使得時(shí)延持續(xù)增加到500ms并出現(xiàn)丟包，整個(gè)過(guò)程Cubic一直處于高時(shí)延狀態(tài)，而B(niǎo)BR由于不會(huì)填滿網(wǎng)絡(luò)緩沖區(qū)，時(shí)延一直處于較低狀態(tài)。
由于BBR算法不將丟包作為擁塞信號(hào)，所以在丟包率較高的網(wǎng)絡(luò)中，BBR依然有極高的吞吐量，如圖5所示，在1%丟包率的網(wǎng)絡(luò)環(huán)境下，Cubic的吞吐量已經(jīng)降低90%以上，而B(niǎo)BR的吞吐量幾乎沒(méi)有受到影響，當(dāng)丟包率大于15%時(shí)，BBR的吞吐量才大幅下降。
BBR算法是反饋驅(qū)動(dòng)的，有自主調(diào)節(jié)機(jī)制，不受TCP擁塞控制狀態(tài)機(jī)的控制，通過(guò)測(cè)量網(wǎng)絡(luò)容量來(lái)調(diào)整擁塞窗口，發(fā)送速率由自己掌控，而傳統(tǒng)的擁塞控制算法只負(fù)責(zé)計(jì)算擁塞窗口，而不管發(fā)送速率（pacing rate），怎么發(fā)由TCP自己決定，這樣會(huì)在瓶頸帶寬附近因發(fā)送速率的激增導(dǎo)致數(shù)據(jù)包排隊(duì)或出現(xiàn)丟包。
經(jīng)過(guò)測(cè)試，在高延時(shí)、高丟包率的環(huán)境下，BBR相對(duì)于Cubic算法在傳輸速度上有較大的提升。
BBR算法的不足之處在于設(shè)備隊(duì)列緩存較大時(shí)，BBR可能會(huì)競(jìng)爭(zhēng)不過(guò)Cubic等比較激進(jìn)算法，原因是BBR不主動(dòng)去占據(jù)隊(duì)列緩存，如果Cubic的流量長(zhǎng)期占據(jù)隊(duì)列緩存，會(huì)使得BBR在多個(gè)周期內(nèi)測(cè)量的極小RTT增大，進(jìn)而使BBR的帶寬減小。
適用場(chǎng)景：適用于高帶寬、高時(shí)延、有一定丟包率的長(zhǎng)肥網(wǎng)絡(luò)，可以有效降低傳輸時(shí)延，并保證較高的吞吐量。
Remy
Remy[5]也稱為計(jì)算機(jī)生成的擁塞控制算法（computer-generated congestion-control algorithm），采用機(jī)器學(xué)習(xí)的方式生成擁塞控制算法模型。通過(guò)輸入各種參數(shù)模型（如瓶頸鏈路速率、時(shí)延、瓶頸鏈路上的發(fā)送者數(shù)量等），使用一個(gè)目標(biāo)函數(shù)定量判斷算法的優(yōu)劣程度，在生成算法的過(guò)程中，針對(duì)不同的網(wǎng)絡(luò)狀態(tài)采用不同的方式調(diào)整擁塞窗口，反復(fù)修改調(diào)節(jié)方式，直到目標(biāo)函數(shù)最優(yōu)，最終會(huì)生成一個(gè)網(wǎng)絡(luò)狀態(tài)到調(diào)節(jié)方式的映射表，在真實(shí)的網(wǎng)絡(luò)中，根據(jù)特定的網(wǎng)絡(luò)環(huán)境從映射表直接選取擁塞窗口的調(diào)節(jié)方式。
Remy試圖屏蔽底層網(wǎng)絡(luò)環(huán)境的差異，采用一個(gè)通用的擁塞控制算法模型來(lái)處理不同的網(wǎng)絡(luò)環(huán)境。這種方式比較依賴輸入的訓(xùn)練集（歷史網(wǎng)絡(luò)模型），如果訓(xùn)練集能夠全面覆蓋所有可能出現(xiàn)的網(wǎng)絡(luò)環(huán)境及擁塞調(diào)節(jié)算法，Remy算法在應(yīng)用到真實(shí)的網(wǎng)絡(luò)環(huán)境中時(shí)能夠表現(xiàn)的很好，但是如果真實(shí)網(wǎng)絡(luò)與訓(xùn)練網(wǎng)絡(luò)差異較大，Remy算法的性能會(huì)比較差。
適用場(chǎng)景：網(wǎng)絡(luò)環(huán)境為復(fù)雜的異構(gòu)網(wǎng)絡(luò)，希望計(jì)算機(jī)能夠針對(duì)不同網(wǎng)絡(luò)場(chǎng)景自動(dòng)選擇合適的擁塞控制方式，要求現(xiàn)有的網(wǎng)絡(luò)模型能夠覆蓋所有可能出現(xiàn)情況。
總結(jié)
每一種擁塞控制算法都是在一定的網(wǎng)絡(luò)環(huán)境下誕生的，適合特定的場(chǎng)景，沒(méi)有一種一勞永逸的算法。網(wǎng)絡(luò)環(huán)境越來(lái)越復(fù)雜，擁塞控制算法也在不斷地演進(jìn)。本文不是要去選擇一個(gè)最好的算法，只是簡(jiǎn)單介紹了幾種典型算法的設(shè)計(jì)思路、優(yōu)缺點(diǎn)以及適用場(chǎng)景，希望能給大家?guī)?lái)一些啟發(fā)。
參考論文
[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.
