當(dāng)前位置:首頁 > 公眾號精選 > 小林coding
[導(dǎo)讀]大家好,我是小林。很早之前跟大家圖解過TCP的擁塞控制:你還在為TCP重傳、滑動窗口、流量控制、擁塞控制發(fā)愁嗎?看完圖解就不愁了但是沒有提及到谷歌的BBR擁塞控制算法,我們之前講的都是傳統(tǒng)的擁塞控制算法,傳統(tǒng)的擁塞控制是基于丟包反饋的方式來做控制的,而谷歌的BBR?擁塞控制算法就...



大家好,我是小林。



很早之前跟大家圖解過 TCP擁塞控制:你還在為 TCP 重傳、滑動窗口、流量控制、擁塞控制發(fā)愁嗎?看完圖解就不愁了



但是沒有提及到谷歌的 BBR 擁塞控制算法,我們之前講的都是傳統(tǒng)的擁塞控制算法,傳統(tǒng)的擁塞控制是基于丟包反饋的方式來做控制的,而谷歌的 BBR 擁塞控制算法就比較牛逼,是基于時延檢測的方式來做控制的,也就是當(dāng)網(wǎng)絡(luò)延遲到一定程度后,就會自動減少擁塞窗口,避免造成丟包,因為丟包后,就要從慢啟動開始了,這樣 TCP 的傳輸速率會瞬間下降的。



今天,我們再來深入談一談 TCP 擁塞控制,還有谷歌的 BBR 算法,比較硬核,文章共 1W 字。



發(fā)車?yán)玻?


1.擁塞控制簡史

來看下維基百科對TCP/IP協(xié)議棧的一些介紹,筆者做了少量的修改來確保語句通順


 互聯(lián)網(wǎng)協(xié)議套件是一個網(wǎng)絡(luò)通信模型以及整個網(wǎng)絡(luò)傳輸協(xié)議家族,由于該協(xié)議簇包含兩個核心協(xié)議:TCP(傳輸控制協(xié)議)和IP(網(wǎng)際協(xié)議),因此常被通稱為TCP/IP協(xié)議族


TCP/IP協(xié)議對于數(shù)據(jù)應(yīng)該如何封裝、定址、傳輸、路由以及在目的地如何接收等基本過程都加以標(biāo)準(zhǔn)化。它將通信過程抽象化為四個層次,并采取協(xié)議堆棧的方式分別實現(xiàn)出不同通信協(xié)議,實際使用的四層結(jié)構(gòu)是七層OSI模型的簡化。


我們可以看到TCP/IP協(xié)議棧是一個簡化的分層模型,是互聯(lián)網(wǎng)世界連接一切的基石,一起來看一張七層模型vs四層模型的簡圖:





大約在1988年之前TCP/IP是沒有擁塞控制的,但是隨著網(wǎng)絡(luò)接入規(guī)模的發(fā)展之前僅有的端到端窗口控制已經(jīng)無法滿足要求,在1986年引發(fā)大規(guī)模網(wǎng)絡(luò)癱瘓,此時就要提到一個重量級人物:Van Jacobson范·雅各布森。


這位力挽狂瀾的人物入選了計算機(jī)名人堂Internet Hall of Fame,Van Jacobson大神提出并設(shè)計實施了TCP/IP擁塞控制,解決了當(dāng)時最大的問題,來簡單看下Van Jacobson的維基百科簡介(筆者做了部分刪減):


范·雅各布森Van Jacobson是目前作為互聯(lián)網(wǎng)技術(shù)基礎(chǔ)的TCP/IP協(xié)議棧的主要起草者,他以其在網(wǎng)絡(luò)性能的提升和優(yōu)化的開創(chuàng)性成就而聞名。


2006年8月,他加入了帕洛阿爾托研究中心擔(dān)任研究員,并在位于相鄰的施樂建筑群的Packet Design公司擔(dān)任首席科學(xué)家。在此之前,他曾是思科系統(tǒng)公司首席科學(xué)家,并在位于勞倫斯伯克利國家實驗室的網(wǎng)絡(luò)研究小組任領(lǐng)導(dǎo)者。


范·雅各布森因為在提高IP網(wǎng)絡(luò)性能提升和優(yōu)化所作的工作而為人們所知,1988到1989年間,他重新設(shè)計了TCP/IP的流控制算法(Jacobson算法),他因設(shè)計了RFC 1144中的TCP/IP頭壓縮協(xié)議即范·雅各布森TCP/IP頭壓縮協(xié)議而廣為人知。此外他也曾與他人合作設(shè)計了一些被廣泛使用的網(wǎng)絡(luò)診斷工具,如traceroute,pathchar以及tcpdump 。


范·雅各布森于2012年4月入選第一批計算機(jī)名人堂,計算機(jī)名人堂簡介:https://www.internethalloffame.org/inductees/van-jacobson


如圖為Van Jacobson計算機(jī)名人堂的簡介:



筆者找了Van Jacobson和Michael J. Karels在1988年11月發(fā)布的關(guān)于擁塞避免和控制的論文,總計25頁,感興趣的讀者可以查閱:


https://ee.lbl.gov/papers/congavoid.pdf


我們常用的tracetoute和tcpdump也是van-jacobson大神的杰作,作為互聯(lián)網(wǎng)時代的受益者不由得對這些互聯(lián)網(wǎng)發(fā)展早期做出巨大貢獻(xiàn)的開拓者、創(chuàng)新者、變革者心生贊嘆和敬意。


2.流量控制和擁塞控制

TCP是一種面向連接的、可靠的、全雙工傳輸協(xié)議,前輩們寫了很多復(fù)雜的算法為其保駕護(hù)航,其中有一組像海爾兄弟一樣的算法:流量控制和擁塞控制,這也是我們今天的主角。




2.1 流量控制簡介

流量控制和擁塞控制從漢語字面上并不能很好的區(qū)分,本質(zhì)上這一對算法既有區(qū)別也有聯(lián)系。



維基百科對于流量控制Flow Control的說明:


 In data communications, flow control is the process of managing the rate of data transmission between two nodes to prevent a fast sender from overwhelming a slow receiver.


It provides a mechanism for the receiver to control the transmission speed, so that the receiving node is not overwhelmed with data from transmitting node.


翻譯一下:


 在數(shù)據(jù)通信中,流量控制是管理兩個節(jié)點之間數(shù)據(jù)傳輸速率的過程,以防止快速發(fā)送方壓倒慢速接收方。


它為接收機(jī)提供了一種控制傳輸速度的機(jī)制,這樣接收節(jié)點就不會被來自發(fā)送節(jié)點的數(shù)據(jù)淹沒。


可以看到流量控制是通信雙方之間約定數(shù)據(jù)量的一種機(jī)制,具體來說是借助于TCP協(xié)議的確認(rèn)ACK機(jī)制和窗口協(xié)議來完成的。



窗口分為固定窗口和可變窗口,可變窗口也就是滑動窗口,簡單來說就是通信雙方根據(jù)接收方的接收情況動態(tài)告訴發(fā)送端可以發(fā)送的數(shù)據(jù)量,從而實現(xiàn)發(fā)送方和接收方的數(shù)據(jù)收發(fā)能力匹配。



這個過程非常容易捕捉,使用wireshark在電腦上抓或者tcpdump在服務(wù)器上抓都可以看到,大白在自己電腦上用wireshark抓了一條:






我們以兩個主機(jī)交互來簡單理解流量控制過程:




接收方回復(fù)報文頭部解釋:




 圖中RcvBuffer是接收區(qū)總大小,buffered data是當(dāng)前已經(jīng)占用的數(shù)據(jù),而free buffer space是當(dāng)前剩余的空間,rwnd的就是free buffer space區(qū)域的字節(jié)數(shù)。


HostB把當(dāng)前的rwnd值放入報文頭部的接收窗口receive window字段中,以此通知HostA自己還有多少可用空間, 而HostA則將未確認(rèn)的數(shù)據(jù)量控制在rwnd值的范圍內(nèi),從而避免HostB的接收緩存溢出。


可見流量控制是端到端微觀層面的數(shù)據(jù)策略,雙方在數(shù)據(jù)通信的過程中并不關(guān)心鏈路帶寬情況,只關(guān)心通信雙方的接收發(fā)送緩沖區(qū)的空間大小,可以說是個速率流量匹配策略。



流量控制就像現(xiàn)實生活中物流領(lǐng)域中A和B兩個倉庫,A往B運送貨物時只關(guān)心倉庫B的剩余空間來調(diào)整自己的發(fā)貨量,而不關(guān)心高速是否擁堵。


2.2 擁塞控制的必要性

前面我們提到了微觀層面點到點的流量控制,但是我們不由地思考一個問題:只有流量控制夠嗎?答案是否定的。



我們還需要一個宏觀層面的控去避免網(wǎng)絡(luò)鏈路的擁堵,否則再好的端到端流量控制算法也面臨丟包、亂序、重傳問題,只能造成惡性循環(huán)。




我們從一個更高的角度去看大量TCP連接復(fù)用網(wǎng)絡(luò)鏈路的通信過程:




所以擁塞控制和每一條端到端的連接關(guān)系非常大,這就是流量控制和擁塞控制的深層次聯(lián)系,所謂每一條連接都順暢那么整個復(fù)雜的網(wǎng)絡(luò)鏈路也很大程度是通暢的。




在展開擁塞控制之前我們先考慮幾個問題:


  • 如何感知擁塞


TCP連接的發(fā)送方在向?qū)Χ税l(fā)送數(shù)據(jù)的過程中,需要根據(jù)當(dāng)前的網(wǎng)絡(luò)狀況來調(diào)整發(fā)送速率,所以感知能力很關(guān)鍵。在TCP連接的發(fā)送方一般是基于丟包來判斷當(dāng)前網(wǎng)絡(luò)是否發(fā)生擁塞,丟包可以由重傳超時RTO和重復(fù)確認(rèn)來做判斷。
  • 如何利用帶寬


誠然擁塞影響很大,但是一直低速發(fā)包對帶寬利用率很低也是很不明智的做法,因此要充分利用帶寬就不能過低過高發(fā)送數(shù)據(jù),而是保持在一個動態(tài)穩(wěn)定的速率來提高帶寬利用率,這個還是比較難的,就像茫茫黑夜去躲避障礙物
  • 擁塞時如何調(diào)整


擁塞發(fā)生時我們需要有一套應(yīng)對措施來防止擁塞惡化并且恢復(fù)連接流量,這也是擁塞控制算法的精要所在。

3.理解擁塞控制

看到一篇文章說到TCP 傳輸層擁塞控制算法并不是簡單的計算機(jī)網(wǎng)絡(luò)的概念,也屬于控制論范疇,感覺這個觀點很道理。


TCP擁塞控制算法的目的可以簡單概括為:公平競爭、充分利用網(wǎng)絡(luò)帶寬、降低網(wǎng)絡(luò)延時、優(yōu)化用戶體驗,然而就目前而言要實現(xiàn)這些目標(biāo)就難免有權(quán)衡和取舍。


在理解擁塞控制算法之前我們需要明確一個核心的思想:聞道有先后 術(shù)業(yè)有專攻,筆者覺得這是一個非常重要的共識問題,把A踩在泥土里,把B吹捧到天上去,都不是很好的做法。


實際的網(wǎng)絡(luò)環(huán)境十分復(fù)雜并且變化很快,并沒有哪個擁塞控制算法可以全部搞定,每一種算法都有自己的特定和適用領(lǐng)域,每種算法都是對幾個關(guān)鍵點的權(quán)衡,在無法兼得的條件下有的算法選擇帶寬利用率,有的算法選擇通信延時等等。


在明確這個共識問題之后,我們對待各個擁塞控制算法的態(tài)度要平和一些,不要偏激地認(rèn)為誰就是最好,幾十年前的網(wǎng)絡(luò)狀況和現(xiàn)在是截然不同的,我們永遠(yuǎn)都是站在巨人的肩膀之上的,這也是科學(xué)和文明進(jìn)步的推動力。



傳統(tǒng)擁塞控制算法并不是一蹴而就的,復(fù)雜的網(wǎng)絡(luò)環(huán)境和用戶的高要求推動著擁塞控制算法的優(yōu)化和迭代,我們看下基于丟包策略的傳統(tǒng)擁塞控制算法的幾個迭代版本,如圖所示:




與此同時還有一類算法是基于RTT延時策略來進(jìn)行控制的,但是這類算法在發(fā)包速率上可能不夠激進(jìn)爭性能不如其他算法,因此在共享網(wǎng)絡(luò)帶寬時有失公平性,但是算法速率曲線卻是很平滑,我們暫且把這類算法當(dāng)做君子吧!



其中比較有名的Vegas算法是大約在1995年由亞利桑那大學(xué)的研究人員拉里·彼得森和勞倫斯·布拉科夫提出,這個新的TCP擁塞算法以內(nèi)華達(dá)州最大的城市拉斯維加斯命名,后成為TCP Vegas算法。


關(guān)于基于RTT的TCP Vegas算法的詳細(xì)介紹可以查閱文檔


http://www.cs.cmu.edu/~srini/15-744/F02/readings/BP95.pdf


文檔對Vegas算法和New Reno做了一些對比,我們從直觀圖形上可以看到Vegas算法更加平滑,相反New Reno則表現(xiàn)除了較大的波動呈鋸齒狀,如圖所示:





實際上還有更細(xì)粒度的分類,由于不是今天的重點,就不再深入展開了,當(dāng)前使用的擁塞控制算法還是基于丟包Loss-Based作為主流。


3.1 擁塞窗口cwnd

從流量控制可以知道接收方在header中給出了rwnd接收窗口大小,發(fā)送方不能自顧自地按照接收方的rwnd限制來發(fā)送數(shù)據(jù),因為網(wǎng)絡(luò)鏈路是復(fù)用的,需要考慮當(dāng)前鏈路情況來確定數(shù)據(jù)量,這也是我們要提的另外一個變量cwnd,筆者找了一個關(guān)于rwnd和cwnd的英文解釋:


 Congestion Window (cwnd) is a TCP state variable that limits the amount of data the TCP can send into the network before receiving an ACK.


The Receiver Window (rwnd) is a variable that advertises the amount of data that the destination side can receive.


Together, the two variables are used to regulate data flow in TCP connections, minimize congestion, and improve network performance.


筆者在rfc5681文檔中也看到cwnd的定義:



這個解釋指出了cwnd是在發(fā)送方維護(hù)的,cwnd和rwnd并不沖突,發(fā)送方需要結(jié)合rwnd和cwnd兩個變量來發(fā)送數(shù)據(jù),如圖所示:



cwnd的大小和MSS最大數(shù)據(jù)段有直接關(guān)系,MSS是TCP報文段中的數(shù)據(jù)字段的最大長度,即MSS=TCP報文段長度-TCP首部長度。


3.2 擁塞控制基本策略

擁塞控制是一個動態(tài)的過程,它既要提高帶寬利用率發(fā)送盡量多的數(shù)據(jù)又要避免網(wǎng)絡(luò)擁堵丟包RTT增大等問題,基于這種高要求并不是單一策略可以搞定的,因此TCP的擁塞控制策略實際上是分階段分策略的綜合過程



注:有的版本的TCP算法不一定沒有快速恢復(fù)階段



如圖為典型的包含4個策略的擁塞控制:



如圖為發(fā)生超時重傳RTO時的過程:



3.3 TCP擁塞控制算法常見版本

實際上TCP算法有很多版本,每個版本存在一些差異,在這里簡單看一下維基百科的介紹:



  • 算法命名規(guī)則


 TCP 算法名的命名方式最早出現(xiàn)在Kevin Fall和Sally Floyd1996年發(fā)布的論文中。


  • TCP Tahoe 和TCP Reno


 這兩個算法代號取自太浩湖Lake Tahoe和里諾市,兩者算法大致一致,對于丟包事件判斷都是以重傳超時retransmission timeout和重復(fù)確認(rèn)為條件,但是對于重復(fù)確認(rèn)的處理兩者有所不同,對于超時重傳RTO情況兩個算法都是將擁塞窗口降為1個MSS,然后進(jìn)入慢啟動階段。


TCP Tahoe算法:如果收到三次重復(fù)確認(rèn)即第四次收到相同確認(rèn)號的分段確認(rèn),并且分段對應(yīng)包無負(fù)載分段和無改變接收窗口的話,Tahoe算法則進(jìn)入快速重傳,將慢啟動閾值改為當(dāng)前擁塞窗口的一半,將擁塞窗口降為1個MSS,并重新進(jìn)入慢啟動階段。


TCP Reno算法:如果收到三次重復(fù)確認(rèn),Reno算法則進(jìn)入快速重傳只將擁塞窗口減半來跳過慢啟動階段,將慢啟動閾值設(shè)為當(dāng)前新的擁塞窗口值,進(jìn)入一個稱為快速恢復(fù)的新設(shè)計階段。


  • TCP New Reno


 TCP New Reno是對TCP Reno中快速恢復(fù)階段的重傳進(jìn)行改善的一種改進(jìn)算法,New Reno在低錯誤率時運行效率和選擇確認(rèn)SACK相當(dāng),在高錯誤率仍優(yōu)于Reno。


  • TCP BIC 和TCP CUBIC


 TCP BIC旨在優(yōu)化高速高延遲網(wǎng)絡(luò)的擁塞控制,其擁塞窗口算法使用二分搜索算法嘗試找到能長時間保持擁塞窗口最大值,Linux內(nèi)核在2.6.8至2.6.18使用該算法作為默認(rèn)TCP擁塞算法。


CUBIC則是比BIC更溫和和系統(tǒng)化的分支版本,其使用三次函數(shù)代替二分算法作為其擁塞窗口算法,并且使用函數(shù)拐點作為擁塞窗口的設(shè)置值,Linux內(nèi)核在2.6.19后使用該算法作為默認(rèn)TCP擁塞算法。


  • TCP PRR


 TCP PRR是旨在恢復(fù)期間提高發(fā)送數(shù)據(jù)的準(zhǔn)確性,該算法確?;謴?fù)后的擁塞窗口大小盡可能接近慢啟動閾值。在Google進(jìn)行的測試中,能將平均延遲降低3~10%恢復(fù)超時減少5%,PRR算法后作為Linux內(nèi)核3.2版本默認(rèn)擁塞算法


  • TCP BBR


TCP BBR是由Google設(shè)計于2016年發(fā)布的擁塞算法,該算法認(rèn)為隨著網(wǎng)絡(luò)接口控制器逐漸進(jìn)入千兆速度時,分組丟失不應(yīng)該被認(rèn)為是識別擁塞的主要決定因素,所以基于模型的擁塞控制算法能有更高的吞吐量和更低的延遲,可以用BBR來替代其他流行的擁塞算法。


Google在YouTube上應(yīng)用該算法,將全球平均的YouTube網(wǎng)絡(luò)吞吐量提高了4%,BBR之后移植入Linux內(nèi)核4.9版本。


3.4 擁塞控制過程詳解

我們以典型慢啟動、擁塞避免、快速重傳、快速恢復(fù)四個過程進(jìn)行闡述。


  • 慢啟動


慢啟動就是對于剛啟動的網(wǎng)絡(luò)連接,發(fā)送速度不是一步到位而是試探性增長,具體來說:連接最初建立時發(fā)送方初始化擁塞窗口cwnd為m,之后發(fā)送方在一個RTT內(nèi)每收到一個ACK數(shù)據(jù)包時cwnd線性自增1,發(fā)送方每經(jīng)過一個RTT時間,cwnd=cwnd*2指數(shù)增長,經(jīng)過一段時間增長直到cwnd達(dá)到慢啟動閾值ssthresh。


之后cwnd不再呈指數(shù)增長從而進(jìn)入擁塞避免階段(注cwnd增長的單位是MSS),當(dāng)然如果在慢啟動階段還未到達(dá)閾值ssthresh而出現(xiàn)丟包時進(jìn)入快速重傳等階段,需要注意的是如果網(wǎng)絡(luò)狀況良好RTT時間很短,那么慢啟動階段將很快到達(dá)一個比較高的發(fā)送速率,所以將慢啟動理解為試探啟動更形象。





  • 擁塞避免


當(dāng)慢啟動階段cwnd的值到達(dá)ssthresh時就不再瘋狂增長,進(jìn)入更加理性的線性階段直至發(fā)送丟包,本次的閾值ssthresh是上一次發(fā)生丟包時cwnd的1/2,因此這是一個承上啟下的過程。


本次發(fā)送丟包時仍然會調(diào)整ssthresh的值,具體擁塞避免增長過程:發(fā)送方每收到一個ACK數(shù)據(jù)包時將cwnd=cwnd 1/cwnd,每經(jīng)過一個RTT將cwnd自增1。


  • 超時重傳和快速重傳


TCP作為一個可靠的協(xié)議面臨的很大的問題就是丟包,丟包就要重傳因此發(fā)送方需要根據(jù)接收方回復(fù)的ACK來確認(rèn)是否丟包了,并且發(fā)送方在發(fā)送數(shù)據(jù)之后啟動定時器,如圖所示:



RTO是隨著復(fù)雜網(wǎng)絡(luò)環(huán)境而動態(tài)變化的,在擁塞控制中發(fā)生超時重傳將會極大拉低cwnd,如果網(wǎng)絡(luò)狀況并沒有那么多糟糕,偶爾出現(xiàn)網(wǎng)絡(luò)抖動造成丟包或者阻塞也非常常見,因此觸發(fā)的慢啟動將降低通信性能,故出現(xiàn)了快速重傳機(jī)制。


所謂快速重傳時相比超時重傳而言的,重發(fā)等待時間會降低并且后續(xù)盡量避免慢啟動,來保證性能損失在最小的程度,如圖所示:



快速重傳和超時重傳的區(qū)別在于cwnd在發(fā)生擁塞時的取值,超時重傳會將cwnd修改為最初的值,也就是慢啟動的值,快速重傳將cwnd減半,二者都將ssthresh設(shè)置為cwnd的一半。


從二者的區(qū)別可以看到,快速重傳更加主動,有利于保證鏈路的傳輸性能,但是有研究表明3個ACK的機(jī)制同樣存在問題,本文就不做深入闡述了,感興趣的讀者可以自主查閱。


快速重傳是基于對網(wǎng)絡(luò)狀況沒有那么糟糕的假設(shè),因此在實際網(wǎng)絡(luò)確實還算好的時候,快速重傳還是很有用的,在很差的網(wǎng)絡(luò)環(huán)境很多算法都很難保證效率的。


  • 快速恢復(fù)


在快速重傳之后就會進(jìn)入快速恢復(fù)階段,此時的cwnd為上次發(fā)生擁塞時的cwnd的1/2,之后cwnd再線性增加重復(fù)之前的過程。

4.弱網(wǎng)環(huán)境的AIMD特性

我們知道在網(wǎng)絡(luò)鏈路中連接的數(shù)量是動態(tài)變化且數(shù)量巨大的,每一條連接都面臨著一個黑盒子式的網(wǎng)絡(luò)環(huán)境,這并不像我們平時出行時看看地圖就知道哪里堵了,為了維護(hù)一個好的網(wǎng)絡(luò)環(huán)境,每一條連接都需要遵守一些約定。



如果連接端都無所顧忌地發(fā)生數(shù)據(jù)包,那么網(wǎng)絡(luò)鏈路很快就到了瓶頸了,數(shù)據(jù)通信完全無法保障,所以要到達(dá)一個穩(wěn)定高效的網(wǎng)絡(luò)環(huán)境還是需要費很大心思的,這其中有兩個重要的概念:公平性和收斂性



說來慚愧筆者在網(wǎng)絡(luò)上找了很多資料去理解TCP擁塞控制的公平性和收斂性,但是仍然沒有獲得一個很好的權(quán)威解釋,所以只能結(jié)合一些資料和自身的理解去闡述所謂的公平性和收斂性。



筆者認(rèn)為公平性是相對于網(wǎng)絡(luò)鏈路中的所有連接而言的,這些共享鏈路的連接啟動和結(jié)束的時間不同,在實際的交互過程中每條連接占有帶寬的機(jī)會是均等的,并且由于帶寬限制連接雙方通信的數(shù)據(jù)量是動態(tài)調(diào)整并且近似收斂于某個值,也就是呈現(xiàn)一個鋸齒狀或者更加平滑的波動曲線,對于基于丟包的擁塞控制算法而言AIMD線性增乘性減策略起了關(guān)鍵控制作用。



接下來我們來重點看下AIMD特性,先來貼一張經(jīng)典的圖,直觀看AIMD的過程:




看看維基百科對于AIMD的定義:


The additive-increase/multiplicative-decrease(AIMD) algorithm is a feedback control algorithm best known for its use in TCP congestion control.


AIMD combines linear growth of the congestion window with an exponential reduction when congestion is detected.


Multiple flows using AIMD congestion control will eventually converge to use equal amounts of a shared link.


The related schemes of multiplicative-increase/multiplicative-decrease (MIMD) and additive-increase/additive-decrease (AIAD) do not reach stability.


簡單翻譯一下:線性增加乘性減少算法是一個反饋控制算法,因其在TCP擁塞控制中的使用而廣為人知,AIMD將線性增加擁塞窗口和擁塞時乘性減少窗口相結(jié)合,基于AIMD的多個連接理想狀態(tài)下會達(dá)到最終收斂,共享相同數(shù)量的網(wǎng)絡(luò)帶寬,與其相關(guān)的乘性增乘性減MIMD策略增性加增性減少AIAD無法保證穩(wěn)定性。



AIMD相比MIMD和AIAD在連接進(jìn)入擁塞避免階段使用試探線性加策略而不是乘性加策略更加安全,在探測丟包時則大幅度乘性減少到1/2這樣對于緩解擁塞會有比較好的效果更加快速,相反如果探測到丟包時采用線性減少AD可能擁塞持續(xù)的時間會更長,總體來說AIMD算是一個比較簡單實用的工程版本的反饋控制,也具備可工程收斂性,因而被廣泛實用。



時間拉回20多年前,在互聯(lián)網(wǎng)早期幾乎所有的設(shè)備都是通過有線網(wǎng)絡(luò)進(jìn)行連接通信的,這也是擁塞控制在設(shè)計之后一直都起到不錯作用的重要因素,有線連接的網(wǎng)絡(luò)穩(wěn)定性比較好,因此把丟包作為網(wǎng)絡(luò)擁堵的一個特征也很正常。



再拉回到現(xiàn)在,從2010年之后移動互聯(lián)網(wǎng)蓬勃發(fā)展,移動終端的持有量已經(jīng)可以稱為海量,無線網(wǎng)絡(luò)的引入讓網(wǎng)絡(luò)環(huán)境變得更加復(fù)雜,因此不穩(wěn)定丟包變得更加頻繁,但是這時的丟包就不一定是網(wǎng)絡(luò)擁堵造成的了,因為整個數(shù)據(jù)包經(jīng)過多重路由、交換機(jī)、基站等基礎(chǔ)通信設(shè)備每個環(huán)節(jié)都可能發(fā)生異常。



在弱網(wǎng)環(huán)境下,尤其是移動互聯(lián)網(wǎng)中之前的基于AIMD的擁塞控制策略可能會由于丟包的出現(xiàn)而大幅降低網(wǎng)絡(luò)吞吐量,從而對網(wǎng)絡(luò)帶寬的利用率也大大下降,這時我們采用更加激進(jìn)的控制策略,或許可以獲得更好的效果和用戶體驗。



惡意丟包的情況下,基于AIMD的擁塞控制確實就相當(dāng)于被限速了,因為AIMD確實有些保守謹(jǐn)慎了,這個其實也很好理解的哈。



我們都知道在移動網(wǎng)絡(luò)環(huán)境下是由終端以無線形式和附近的基站交互數(shù)據(jù),之后數(shù)據(jù)傳輸至核心網(wǎng),最后落到具體的服務(wù)器所在的有線網(wǎng)絡(luò),其中最后一公里的區(qū)域?qū)儆诟哐訒r場景,有線網(wǎng)絡(luò)屬于低延時高帶寬場景。



在國外有相關(guān)實驗證明弱網(wǎng)環(huán)境下RTT的變化對于使用傳統(tǒng)擁塞控制算法下網(wǎng)絡(luò)吞吐量的影響,數(shù)據(jù)和曲線如圖所示:






實驗含義:RTT的增大影響了比如CUBIC這類擁塞控制算法的慢啟動等階段,我們知道慢啟動階段每經(jīng)過1個RTT周期擁塞窗口cwnd將加倍,但是更大的RTT就意味著發(fā)送方以很低的速率發(fā)送數(shù)據(jù),更多的時間是空閑的,發(fā)包的加速度極大將低了,所以整個吞吐量就下降很明顯。



看下實驗者的原文表述:


The delay before acknowledgment packets are received (= latency) will have an impact on how fast the TCP congestion window increases (hence the throughput).


When latency is high, it means that the sender spends more time idle (not sending any new packets), which reduces how fast throughput grows.


5.BBR算法基本原理

BBR算法是個主動的閉環(huán)反饋系統(tǒng),通俗來說就是根據(jù)帶寬和RTT延時來不斷動態(tài)探索尋找合適的發(fā)送速率和發(fā)送量。



看下維基百科對BBR算法的說明和資料:


相關(guān)文獻(xiàn):https://queue.acm.org/detail.cfm?id=3022184


TCP BBR(Bottleneck Bandwidth and Round-trip propagation time)是由Google設(shè)計,并于2016年發(fā)布的擁塞算法,以往大部分擁塞算法是基于丟包來作為降低傳輸速率的信號,而BBR基于模型主動探測。


該算法使用網(wǎng)絡(luò)最近出站數(shù)據(jù)分組當(dāng)時的最大帶寬往返時間來創(chuàng)建網(wǎng)絡(luò)的顯式模型。數(shù)據(jù)包傳輸?shù)拿總€累積或選擇性確認(rèn)用于生成記錄在數(shù)據(jù)包傳輸過程和確認(rèn)返回期間的時間內(nèi)所傳送數(shù)據(jù)量的采樣率。


該算法認(rèn)為隨著網(wǎng)絡(luò)接口控制器逐漸進(jìn)入千兆速度時,分組丟失不應(yīng)該被認(rèn)為是識別擁塞的主要決定因素,所以基于模型的擁塞控制算法能有更高的吞吐量和更低的延遲,可以用BBR來替代其他流行的擁塞算法例如CUBIC。Google在YouTube上應(yīng)用該算法,將全球平均的YouTube網(wǎng)絡(luò)吞吐量提高了4%,在一些國家超過了14%。BBR之后移植入Linux內(nèi)核4.9版本,并且對于QUIC可用。


5.1 基于丟包反饋策略可能在的問題

基于丟包反饋屬于被動式機(jī)制,根源在于這些擁塞控制算法依據(jù)是否出現(xiàn)丟包事件來判斷網(wǎng)絡(luò)擁塞做減窗調(diào)整,這樣就可能會出現(xiàn)一些問題:


  • 丟包即擁塞
    現(xiàn)實中網(wǎng)絡(luò)環(huán)境很復(fù)雜會存在錯誤丟包,很多算法無法很好區(qū)分擁塞丟包和錯誤丟包,因此在存在一定錯誤丟包的前提下在某些網(wǎng)絡(luò)場景中并不能充分利用帶寬。
  • 緩沖區(qū)膨脹問題BufferBloat
    網(wǎng)絡(luò)連接中路由器、交換機(jī)、核心網(wǎng)設(shè)備等等為了平滑網(wǎng)絡(luò)波動而存在緩沖區(qū),這些緩存區(qū)就像輸液管的膨脹部分讓數(shù)據(jù)更加平穩(wěn),但是Loss-Based策略在最初就像網(wǎng)絡(luò)中發(fā)生數(shù)據(jù)類似于灌水,此時是將Buffer全部算在內(nèi)的,一旦buffer滿了,就可能出現(xiàn)RTT增加丟包等問題,就相當(dāng)于有的容量本不該算在其中,但是策略是基于包含Buffer進(jìn)行預(yù)測的,特別地在深緩沖區(qū)網(wǎng)絡(luò)就會出現(xiàn)一些問題。
  • 網(wǎng)絡(luò)負(fù)載高但無丟包事件
    假設(shè)網(wǎng)絡(luò)中的負(fù)載已經(jīng)很高了,只要沒有丟包事件出現(xiàn),算法就不會主動減窗降低發(fā)送速率,這種情況下雖然充分利用了網(wǎng)絡(luò)帶寬,同時由于一直沒有丟包事件出現(xiàn)發(fā)送方仍然在加窗,表現(xiàn)出了較強(qiáng)的網(wǎng)絡(luò)帶寬侵略性,加重了網(wǎng)絡(luò)負(fù)載壓力。
  • 高負(fù)載丟包
    高負(fù)載無丟包情況下算法一直加窗,這樣可以預(yù)測丟包事件可能很快就出現(xiàn)了,一旦丟包出現(xiàn)窗口將呈現(xiàn)乘性減少,由高位發(fā)送速率迅速降低會造成整個網(wǎng)絡(luò)的瞬時抖動性,總體呈現(xiàn)較大的鋸齒狀波動。
  • 低負(fù)載高延時丟包
    在某些弱網(wǎng)環(huán)境下RTT會增加甚至出現(xiàn)非擁塞引起丟包,此時基于丟包反饋的擁塞算法的窗口會比較小,對帶寬的利用率很低,吞吐量下降很明顯,但是實際上網(wǎng)絡(luò)負(fù)載并不高,所以在弱網(wǎng)環(huán)境下效果并不是非常理想。

5.2 TCP BBR算法基本原理

前面我們提到了一些Loss-Based算法存在的問題,TCP BBR算法是一種主動式機(jī)制,簡單來說BBR算法不再基于丟包判斷并且也不再使用AIMD線性增乘性減策略來維護(hù)擁塞窗口,而是分別采樣估計極大帶寬和極小延時,并用二者乘積作為發(fā)送窗口,并且BBR引入了Pacing Rate限制數(shù)據(jù)發(fā)送速率,配合cwnd使用來降低沖擊。



5.2.1 一些術(shù)語

  • BDPBDP是Bandwidth-Delay Product的縮寫,可以翻譯為帶寬延時積,我們知道帶寬的單位是bps(bit per second),延時的單位是s,這樣BDP的量綱單位就是bit,從而我們知道BDP就是衡量一段時間內(nèi)鏈路的數(shù)據(jù)量的指標(biāo)。這個可以形象理解為水管灌水問題,帶寬就是水管的水流速度立方米/s,延時就是灌水時間單位s,二者乘積我們就可以知道當(dāng)前水管內(nèi)存儲的水量了,這是BBR算法的一個關(guān)鍵指標(biāo),來看一張陶輝大神文章中的圖以及一些網(wǎng)絡(luò)場景中的BDP計算


  • 長肥網(wǎng)絡(luò)
    我們把具有長RTT往返時間和高帶寬的網(wǎng)絡(luò)成為長肥網(wǎng)絡(luò)或者長肥管道,它的帶寬延時積BDP很大大,這種網(wǎng)絡(luò)理論上吞吐量很大也是研究的重點。


  • TCP Pacing機(jī)制
    可以簡單地理解TCP Pacing機(jī)制就是將擁塞控制中數(shù)據(jù)包的做平滑發(fā)送處理,避免數(shù)據(jù)的突發(fā)降低網(wǎng)絡(luò)抖動。



5.2.2 帶寬和延時的測量

BBR算法的一些思想在之前的基于延時的擁塞控制算法中也有出現(xiàn),其中必有有名的是TCP WestWood算法。


TCP Westwood改良自New Reno,不同于以往其他擁塞控制算法使用丟失來測量,其通過對確認(rèn)包測量來確定一個合適的發(fā)送速度,并以此調(diào)整擁塞窗口和慢啟動閾值。其改良了慢啟動階段算法為敏捷探測和設(shè)計了一種持續(xù)探測擁塞窗口的方法來控制進(jìn)入敏捷探測,使鏈接盡可能地使用更多的帶寬。


TCP WestWood算法也是基于帶寬和延時乘積進(jìn)行設(shè)計的,但是帶寬和延時兩個指標(biāo)無法同時測量,因為這兩個值是有些矛盾的極值,要測量最大帶寬就要發(fā)送最大的數(shù)據(jù)量但是此時的RTT可能會很大,如果要測量最小的RTT那么久意味著數(shù)據(jù)量非常少最大帶寬就無法獲得。



TCP BBR算法采用交替采樣測量兩個指標(biāo),取一段時間內(nèi)的帶寬極大值和延時極小值作為估計值,具體的實現(xiàn)本文就不展開了。



5.2.3 發(fā)送速率和RTT曲線

前面提到了BBR算法核心是尋找BDP最優(yōu)工作點,在相關(guān)論文中給出了一張組合的曲線圖,我們一起來看下:




1.曲線圖示說明:
這張圖是由兩個圖組合而成,目前是展示[數(shù)據(jù)發(fā)送速率vs網(wǎng)絡(luò)數(shù)據(jù)]和[RTTvs網(wǎng)絡(luò)數(shù)據(jù)]的關(guān)系,橫軸是網(wǎng)絡(luò)數(shù)據(jù)數(shù)量。



兩個縱軸從上到下分別為RTT和發(fā)送速率,并且整個過程分為了3個階段:應(yīng)用限制階段、帶寬限制階段、緩沖區(qū)限制階段


2.曲線過程說明:


  • app limit應(yīng)用限制階段
    在這個階段是應(yīng)用程序開始發(fā)送數(shù)據(jù),目前網(wǎng)絡(luò)通暢RTT基本保持固定且很小,發(fā)送速率與RTT成反比,因此發(fā)送速率也是線性增加的,可以簡單認(rèn)為這個階段有效帶寬并沒有達(dá)到上限,RTT是幾乎固定的沒有明顯增長。
  • band limit帶寬限制階段
    隨著發(fā)送速率提高,網(wǎng)絡(luò)中的數(shù)據(jù)包越來越多開始占用鏈路Buffer,此時RTT開始增加發(fā)送速率不再上升,有效帶寬開始出現(xiàn)瓶頸,但是此時鏈路中的緩存區(qū)并沒有占滿,因此數(shù)據(jù)還在增加,RTT也開始增加。
  • buffer limit緩沖區(qū)限制階段
    隨著鏈路中的Buffer被占滿,開始出現(xiàn)丟包,這也是探測到的最大帶寬,這個節(jié)點BDP BufferSize也是基于丟包的控制策略的作用點。

3.一些看法


網(wǎng)上有一些資料都提及到了這張圖,其中的一些解釋也并不算非常清晰,結(jié)合這些資料和自己的認(rèn)識,筆者認(rèn)為在網(wǎng)絡(luò)鏈路的緩存區(qū)沒有被使用時RTT為最小延時MinRTT,在網(wǎng)絡(luò)鏈路緩沖區(qū)被占滿時出現(xiàn)最大帶寬MaxBW(鏈路帶寬 鏈路緩存),但是此時的MaxBW和MinRTT并不是最優(yōu)的而是水位比較高的水平,有數(shù)據(jù)表明按照2ln2的增益計算此時為3BDP,整個過程中MinRTT和MaxBW是分開探測的,因為這二者是不能同時被測量的。



5.2.4 BBR算法的主要過程

BBR算法和CUBIC算法類似,也同樣有幾個過程:StartUp、Drain、Probe_BW、Probe_RTT,來看下這幾個狀態(tài)的遷移情況:





  • StartUp慢啟動階段
    BBR的慢啟動階段類似于CUBIC的慢啟動,同樣是進(jìn)行探測式加速區(qū)別在于BBR的慢啟動使用2ln2的增益加速,過程中即使發(fā)生丟包也不會引起速率的降低,而是依據(jù)返回的確認(rèn)數(shù)據(jù)包來判斷帶寬增長,直到帶寬不再增長時就停止慢啟動而進(jìn)入下一個階段,需要注意的是在尋找最大帶寬的過程中產(chǎn)生了多余的2BDP的數(shù)據(jù)量,關(guān)于這塊可以看下英文原文的解釋:
To handle Internet link bandwidths spanning 12 orders of magnitude, Startup implements a binary search for BtlBw by using a gain of 2/ln2 to double the sending rate while delivery rate is increasing. This discovers BtlBw in log2BDP RTTs but creates up to 2BDP excess queue in the process.


  • Drain排空階段
    排空階段是為了把慢啟動結(jié)束時多余的2BDP的數(shù)據(jù)量清空,此階段發(fā)送速率開始下降,也就是單位時間發(fā)送的數(shù)據(jù)包數(shù)量在下降,直到未確認(rèn)的數(shù)據(jù)包數(shù)量


  • ProbeBW帶寬探測階段
    經(jīng)過慢啟動和排空之后,目前發(fā)送方進(jìn)入穩(wěn)定狀態(tài)進(jìn)行數(shù)據(jù)的發(fā)送,由于網(wǎng)絡(luò)帶寬的變化要比RTT更為頻繁,因此ProbeBW階段也是BBR的主要階段,在探測期中增加發(fā)包速率如果數(shù)據(jù)包ACK并沒有受影響那么就繼續(xù)增加,探測到帶寬降低時也進(jìn)行發(fā)包速率下降。


  • ProbeRTT延時探測階段
    前面三個過程在運行時都可能進(jìn)入ProbeRTT階段,當(dāng)某個設(shè)定時間內(nèi)都沒有更新最小延時狀態(tài)下開始降低數(shù)據(jù)包發(fā)送量,試圖探測到更小的MinRTT,探測完成之后再根據(jù)最新數(shù)據(jù)來確定進(jìn)入慢啟動還是ProbeBW階段。


們來看一下這四個過程的示意圖:




曲線說明這兩個坐標(biāo)給出了10Mbps和40msRTT的網(wǎng)絡(luò)環(huán)境下CUBIC和BBR的一個對比過程,在上面的圖中藍(lán)色表示接收者,紅色表示CUBIC,綠色表示BBR,在下面的圖中給出了對應(yīng)上圖過程中的RTT波動情況,紅色代表CUBIC,綠色代表BBR。


5.3 TCP-BBR算法效果

有一些文章認(rèn)為BBR有鮮明的特點,把擁塞控制算法分為BBR之前和BBR之后,可見BBR還是有一定影響,但是BBR算法也不是銀彈,不過可以先看看BBR算法在谷歌推動下的一些應(yīng)用效果,其中包括吞吐量、RTT、丟包率影響






從圖中我們可以看到在YouTube應(yīng)用BBR算法之后,就吞吐量普遍有4%左右的提升,特別地在日本的提升達(dá)到14%,RTT的下降更為明顯平均降低33%,其中IN(印度地區(qū))達(dá)到50%以上,在丟包率測試中BBR并不想CUBIC那么敏感,在丟包率達(dá)到5%是吞吐量才開始明顯下降。







本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點,本站亦不保證或承諾內(nèi)容真實性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請及時聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫毥谦F公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉(zhuǎn)型技術(shù)解決方案公司Trianz今天宣布,該公司與Amazon Web Services (AWS)簽訂了...

關(guān)鍵字: AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認(rèn)證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動 BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運行,同時企業(yè)卻面臨越來越多業(yè)務(wù)中斷的風(fēng)險,如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報道,騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機(jī) 衛(wèi)星通信

要點: 有效應(yīng)對環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實提質(zhì)增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競爭力 堅持高質(zhì)量發(fā)展策略,塑強(qiáng)核心競爭優(yōu)勢...

關(guān)鍵字: 通信 BSP 電信運營商 數(shù)字經(jīng)濟(jì)

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺與中國電影電視技術(shù)學(xué)會聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會上宣布正式成立。 活動現(xiàn)場 NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會上,軟通動力信息技術(shù)(集團(tuán))股份有限公司(以下簡稱"軟通動力")與長三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉