安基網 首頁 系統 網絡學院 查看內容

2012雪缘园比分:淺談TCP/IP傳輸層TCP BBR算法

英超雪缘园 www.trual.com.cn 2020-2-16 16:02| 投稿: xiaotiger |來自: 互聯網


免責聲明:本站系公益性非盈利IT技術普及網,本文由投稿者轉載自互聯網的公開文章,文末均已注明出處,其內容和圖片版權歸原網站或作者所有,文中所述不代表本站觀點,若有無意侵權或轉載不當之處請從網站右下角聯系我們處理,謝謝合作!

摘要: 今天一起來學習下最新Linux內核中增加的擁塞控制算法: TCP BBR算法。鑒于TCP擁塞控制算法背后有一套復雜的數學理論和控制策略,因此本文也只能是 淺談 ,通過本文你將了解到以下內容( 溫馨提示:文章較長需要一些耐心,也可以先收藏再閱讀 ):回顧傳統擁塞控制算法TCP BBR算法的概況BBR算法 ...

0x00.前言

今天一起來學習下最新Linux內核中增加的擁塞控制算法: TCP BBR算法。

鑒于TCP擁塞控制算法背后有一套復雜的數學理論和控制策略,因此本文也只能是 淺談 ,通過本文你將了解到以下內容( 溫馨提示:文章較長需要一些耐心,也可以先收藏再閱讀 ):

  • 回顧傳統擁塞控制算法
  • TCP BBR算法的概況
  • BBR算法的原理簡介

0x01. 擁塞控制簡史

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

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

范·雅各布森Van Jacobson是目前作為 互聯網技術基礎的TCP/IP協議棧的主要起草者 ,他以其 在網絡性能的提升和優化的開創性成就而聞名 。

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

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

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

如圖為Van Jacobson計算機名人堂的簡介:

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

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

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

0x02.傳統擁塞控制算法回顧

2.1 算法目的

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

TCP擁塞控制算法的目的可以簡單概括為: 公平競爭、充分利用網絡帶寬、降低網絡延時、優化用戶體驗, 然而就目前而言要實現這些目標就難免有 權衡和取舍。

但是現在的網絡通信基礎設施水平一直在飛速提高,相信在未來的某個時間點這些目標都可以達到, 小孩子才選擇,我們大人全都要 !

2.2 算法分類

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

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

在明確這個 共識問題 之后,我們對待各個擁塞控制算法的態度要 平和一些,不要偏激 地認為誰就是最好,幾十年前的網絡狀況和現在是截然不同的, 我們永遠都是站在巨人的肩膀之上的,這也是科學和文明進步的推動力 。

傳統擁塞控制算法并 不是一蹴而就 的, 復雜的網絡環境和用戶的高要求推動著擁塞控制算法的優化和迭代 ,我們看下 基于丟包策略 的傳統擁塞控制算法的幾個迭代版本,如圖所示:

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

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

關于基于RTT的TCP Vegas算法的詳細介紹可以查閱文檔 :

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

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

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

2.3 算法原則

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

如果連接端都無所顧忌地發生數據包,那么網絡鏈路很快就到了瓶頸了,數據通信完全無法保障,所以要到達一個 穩定高效的網絡環境 還是需要費很大心思的,這其中有兩個重要的概念: 公平性和收斂性 。

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

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

接下來我們來重點看下AIMD特性,先來貼一張經典的圖,直觀看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將線性增加擁塞窗口和擁塞時乘性減少窗口相結合 ,基于AIMD的多個連接理想狀態下會達到 最終收斂 ,共享相同數量的網絡帶寬,與其相關的 乘性增乘性減MIMD策略 和 增性加增性減少AIAD 都 無法保證穩定性 。

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

2.4 弱網絡環境下的AIMD

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

再拉回到現在,從2010年之后 移動互聯網 蓬勃發展,移動終端的持有量已經可以稱為海量,無線網絡的引入讓網絡環境變得更加復雜,因此 不穩定丟包變得更加頻繁 ,但是這時的 丟包就不一定是網絡擁堵 造成的了,因為整個數據包經過多重路由、交換機、基站等基礎通信設備每個環節都可能發生異常。

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

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

我們都知道在移動網絡環境下是由終端以無線形式和附近的基站交互數據,之后數據傳輸至核心網,最后落到具體的服務器所在的有線網絡,其中最后一公里的區域屬于高延時場景,有線網絡屬于低延時高帶寬場景。

在國外有相關實驗證明弱網環境下RTT的變化對于使用傳統擁塞控制算法下網絡吞吐量的影響,數據和曲線如圖所示:

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

看下實驗者的原文表述:

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.

0x03 TCP BBR算法簡介

BBR算法是個 主動的閉環反饋系統 ,通俗來說就是根據帶寬和RTT延時來不斷動態探索尋找合適的發送速率和發送量。

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

相關文獻: https://queue.acm.org/detail.cfm?id=3022184

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

該算法使用網絡最近出站數據分組當時的 最大帶寬 和 往返時間 來創建網絡的顯式模型。數據包傳輸的每個累積或選擇性確認用于生成記錄在數據包傳輸過程和確認返回期間的時間內所傳送數據量的采樣率。

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

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

基于丟包反饋屬于 被動式機制 ,根源在于這些擁塞控制算法依據是否出現丟包事件來判斷網絡擁塞做減窗調整,這樣就可能會出現一些問題:

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

3.2 TCP BBR算法基本原理

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

3.2.1 一些術語

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

  • 長肥網絡我們把具有 長RTT往返時間和高帶寬 的網絡成為 長肥網絡或者長肥管道,它的帶寬延時積BDP很大大,這種網絡理論上吞吐量很大也是研究的重點。
  • TCP Pacing機制可以簡單地理解 TCP Pacing機制 就是將擁塞控制中數據包的做 平滑 發送處理,避免數據的突發降低 網絡抖動。

3.2.2 帶寬和延時的測量

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

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

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

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

3.2.3 發送速率和RTT曲線

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

1.曲線圖示說明:

這張圖是由兩個圖組合而成,目前是展示[ 數據發送速率vs網絡數據 ]和[ RTTvs網絡數據] 的關系

,橫軸是網絡數據數量。

兩個縱軸從上到下分別為RTT和發送速率,并且整個過程分為了3個階段: 應用限制階段、帶寬限制階段、緩沖區限制階段 。

2.曲線過程說明:

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

3.一些看法

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

3.2.4 BBR算法的主要過程

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

  • StartUp慢啟動階段BBR的慢啟動階段類似于CUBIC的慢啟動,同樣是進行探測式加速區別在于BBR的慢啟動使用2ln2的增益加速,過程中即使發生丟包也不會引起速率的降低,而是依據返回的確認數據包來判斷帶寬增長,直到帶寬不再增長時就停止慢啟動而進入下一個階段,需要注意的是在尋找最大帶寬的過程中產生了多余的2BDP的數據量,關于這塊可以看下英文原文的解釋:
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排空階段排空階段是為了把慢啟動結束時多余的2BDP的數據量清空,此階段發送速率開始下降,也就是單位時間發送的數據包數量在下降,直到未確認的數據包數量
  • ProbeBW帶寬探測階段經過慢啟動和排空之后,目前發送方進入穩定狀態進行數據的發送,由于網絡帶寬的變化要比RTT更為頻繁,因此ProbeBW階段也是BBR的主要階段,在探測期中增加發包速率如果數據包ACK并沒有受影響那么就繼續增加,探測到帶寬降低時也進行發包速率下降。
  • ProbeRTT延時探測階段前面三個過程在運行時都可能進入ProbeRTT階段,當某個設定時間內都沒有更新最小延時狀態下開始降低數據包發送量,試圖探測到更小的MinRTT,探測完成之后再根據最新數據來確定進入慢啟動還是ProbeBW階段。

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

曲線說明 : 這兩個坐標給出了10Mbps和40msRTT的網絡環境下CUBIC和BBR的一個對比過程,在上面的圖中藍色表示接收者,紅色表示CUBIC,綠色表示BBR,在下面的圖中給出了對應上圖過程中的RTT波動情況,紅色代表CUBIC,綠色代表BBR。

0x04.TCP BBR算法的一些效果

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

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

0x05.總結

本文先回顧了以CUBIC為代表傳統的擁塞控制算法,之后展開了對BBR算法的一些介紹。

網絡上關于BBR的文章很多,筆者也嘗試結合很多文章和外文資料進行理解和歸納,但是由于筆者工作經驗和水平所致上述文字中可能存在一些問題,對此表達歉意,并且很多細節也并未展開,所以只能當做是一次淺談了。



小編推薦:欲學習電腦技術、系統維護、網絡管理、編程開發和安全攻防等高端IT技術,請 點擊這里 注冊賬號,公開課頻道價值萬元IT培訓教程免費學,讓您少走彎路、事半功倍,好工作升職加薪!

本文出自:https://www.toutiao.com/a6793861338096468491/

免責聲明:本站系公益性非盈利IT技術普及網,本文由投稿者轉載自互聯網的公開文章,文末均已注明出處,其內容和圖片版權歸原網站或作者所有,文中所述不代表本站觀點,若有無意侵權或轉載不當之處請從網站右下角聯系我們處理,謝謝合作!

相關閱讀

最新評論

 最新
返回頂部
{ganrao} 11选5走势图吉林 青海十一选五彩票控基础 3分赛车开奖 财富之都 短线股票推荐 46 开拓者vs勇士视频直播 3d开机号试机号 中国股票涨跌幅限制 天津快乐十分开奖记录 3d最近30期开机 排列3 古田美穗东京热种子 3d杀码专家码 苍井空50分钟无码 新浙江十一选五走势图表 3d过滤 苹果