歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
Linux教程網 >> Linux基礎 >> Linux教程 >> Googles BBR擁塞控制算法如何對抗丟包

Googles BBR擁塞控制算法如何對抗丟包

日期:2017/2/28 13:47:52   编辑:Linux教程
我不知道該怎麼說。總之,便捨船,從口入,我看不到黃發垂髫並怡然自樂!我不會說什麼,除了咒罵!
在BBR之前,存在著兩種擁塞控制算法,基於丟包的和基於時延的,不管哪一種都是基於探測的,換句話說,基於丟包的算法將丟包作為一種發現擁塞的手段,而基於時延的算法則是將時延增加作為發現擁塞的手段,它們之所以錯誤是因為它們的初衷就是錯的:

丟包算法:

為了發現擁塞就不得不制造擁塞,這TMD的太JIBA諷刺了,為了戒毒,就必須先TMD的染上毒瘾!然而根本沒毒瘾的話何談戒毒!TCP之所以這麼玩我覺得很大程度上”歸功“於30多年前最初的關於擁塞控制的論文。在那個年代,和我們現在的網絡完全不同,幾乎很少的隊列,由於存儲器比較貴,所以路由器和交換機上幾乎都沒有太深的隊列,甚至都是很淺的隊列,在那種情況下,丟包確實表明了擁塞的信號,然而後來隨著設備隊列越來越深(摩爾定律使然),在丟包前,一個TCP連接必須不斷的去填充非常深的隊列,當深隊列被填滿後,是什麼情況?是擁塞!
我不得不再次重復解釋時間延展性緩存和時間牆緩存的區別,對於前者,時間可以消耗掉任何數據包,然而對於後者,時間牆的存在則必然會發生擁塞,如果不明白這個基本區別的話,就會設計出錯誤的擁塞控制方案。不幸的是,TCP在30年來都沒有對這兩類緩存進行區分!同樣的大小,二者的表現完全不同!
後面我把時間延展性緩存稱作第一類緩存,時間牆緩存稱作第二類緩存。只有當第二類緩存被填滿的時候,算法才會發現擁塞,而此時,擁塞已經要開始緩解了!滯後性!

時延算法:

OK!我承認時延算法主動避免了第二類緩存的數據堆積(如果你意識不到這一點,請停止閱讀。),然而由於丟包算法的存在,時延算法一直處在被壓制的狀態。想知道時延算法的問題,請自己百度,根本不需要google。

兩類方法中的無論哪一類,都是傻逼雞屎做法!擁塞的判斷應該關注“congestion (queue buildup) starts to occur”,而不是“buffer full”!!!


所以說,這些算法都是錯的!那麼BBR就一定對嗎?
近幾日,從9月16號開始,BBR被炒作的沸沸揚揚,好像就是神一般,但事實會證明都JIBA扯淡,TCP擁塞控制領域本身就是一個無解的領域,現在用BBR撕CUBIC好像還比較得心應手,到頭來來個RBB就可以跟BBR勢均力敵了,帶寬還是那麼多,硬件資源就擺在那,大家要公平共享這才是王道,任由一家獨大搶占別人的帶寬還不告訴別人,這是傻逼。所以我說,TCP加速這個行當是個丑行。

BBR不是神,甚至不是人,但它...
BBR區分了兩類緩存,並且發誓不再將第二類緩存作為BDP的計算,然而BBR有原則,它將堅持在max-BW和min-RTT處,任由其它的算法去搶那些第二類緩存吧,CAO!TCP的君子協定讓那些別的算法發現第二類緩存填滿後,會降速到不足以填充第一類緩存的地步,此時,BBR會說:這是你們出讓給我的。
總結一點,BBR不去搶占沒有意義的第二類緩存,這類緩存不光沒有意義--不會增加速率,一旦填滿後後還要付出代價而降速!BBR只要屬於自己的。BBR會盡可能完全利用第一類緩存!

所以,我覺得BBR既不是基於丟包的算法,也不是基於時延的算法,而是一個基於反饋的算法!既然搞不定猜測,那就不猜測,BBR只基於現在,而不考慮歷史(win_minmax表明其僅僅在意時間窗口內的歷史!)!

BBR算法避免了填充第二類緩存,因此它的初衷就是避免擁塞-真正的cong_avoid!。

避免了擁塞,在Linux傳統看來就是避免了丟包!BBR的收斂點在第二類緩存左邊,因此不會因為擁塞而丟包,但是丟包分三類:
1.噪聲丟包
2.擁塞被動丟包
3.流量監管主動丟包

BBR已經可以應對1和2(對於1,通過時間窗口可以過濾,對於2,算法本身的反饋收斂特性決定),那麼對於3,BBR有何殺手锏呢?這就是BBR的long-term rate特性。
我先來展示一段關於BBR long-term的注釋:
Token-bucket traffic policers are common (see "An Internet-Wide Analysis of Traffic Policing", SIGCOMM 2016). BBR detects token-bucket policers and explicitly
models their policed rate, to reduce unnecessary losses. We estimate that we're policed if we see 2 consecutive sampling intervals with consistent throughput
and high packet loss. If we think we're being policed, set lt_bw to the "long-term" average delivery rate from those 2 intervals.


我之前說過,BBR會基於即時測量的上一次發送帶寬來計算這次該發送的速率和cwnd,好像BBR根本不會經歷丟包一樣!但這是不真實的!任何算法都不能忽略上述第3種丟包。沒有擁塞,沒有噪聲,但就是丟包了,Why?因為路由器有權力決定任何數據包的丟失。幾乎所有的路由器交換機裡都會一個令牌桶!TCP流在路由器面前就是渣!雖然是渣渣,BBR還是可以發現路由器的這種丟包行為。

BBR在采集即時帶寬的同時,還在默默觀察丟包率。
如果BBR發現連續兩個delivered周期(類似RTT,但是在擁塞或者被監管情形下,RTT會變化)內,TCP連接內滿足兩點,其一是吞吐速率恆定,其二是持有高丟包率,那說明什麼?說明連接被中間設備限速或者流量整形了...除此之外,你還能想到發生了別的什麼情況,如果你想到了,那你就可以自己做一個算法了。

我已經提示了,溫州皮鞋老板們,搞起來!我有能力,但我不會去做,因為我對瞎子哲學嗤之以鼻!

TCP這部分的代碼在哪裡?請patch最新的BBR補丁,然後就可以探知究竟了。
現在是中午12點整,老婆出去上班了,丈母娘在廚房做飯,而我卻在這裡寫這些亂七八糟的東西!CAO!我在玩火!我很想多說幾句,但我不得不上代碼了:
static void bbr_lt_bw_sampling(struct sock *sk, const struct rate_sample *rs)
{
...
}

...
我還是還是不想去分析源碼。我在這裡只講邏輯。

TCP發送端如何檢測到自己連接的流量受到了限速設備的流量監管呢?我仍以經典VJ擁塞模型圖為例:

如圖上所示,雖然由於發送端不斷增加發送數據量或者別的連接增加了發送量,但是對於位置A而言,速率都是一定的,對於位置B而言,要麼它是空的,要麼它已經滿了,這是TCP所察覺不到的!TCP唯一能做的是,按照反饋的ACK來進行發送速率的抉擇!

這樣的BBR可以避免第2類丟包,並且可以識別第1類丟包,但是對於第3類丟包無能為力,對於BBR而言,目前而言,第3類丟包的處理是最後要做的了。
BBR處理第三類丟包的手段,非常簡單,僅僅是記錄丟包本身即可。當發生以下情況時,BBR認為網絡Path上有流量監管或者限速:
1.持續一段時間保持高丟包率;
2.持續一段時間測量的當前帶寬幾乎一致。

當BBR檢測到這種情況額時候,就不再用當前測量的帶寬為計算Pacing Rate和cwnd的基准了,而是將這段時間內的平均測量帶寬為基准!這個檢測在最開始!
詳細閱讀bbr_lt_bw_sampling函數的代碼,花上個十幾分鐘,就什麼都懂了。BBR如此一來就相當於樸素地識別了流量監管設備的存在並且適配了它的速率!注意,這是一種樸素的算法,而不是什麼可以讓一群人噼裡啪啦扯淡的算法!
靠這種long-term算法,BBR可以對抗監管設備的策略造成的丟包了。於此,BBR幾乎可以檢測到所有的丟包了:
1).如果收到重復ACK(重復ACK,SACKed數量,SACKed最高值...),雖然TCP核心認為發生了丟包,但是不會進入PRR,BBR會不屑一顧,繼續自己的策略,參見BBR引擎說明書;
2).如果真的發生了擁塞,BBR在最小RTT周期之後會發現這是真的,雖然滯後,但總比CUBIC之類滯後發現第二類緩存被填滿強多了。BBR不會盲目降速,而是依然根據檢測到的max-BW來,除非max-BW已經非常小!
3).如果發生監管丟包,BBR會在一段比較長的周期內檢測到,它發現在這個周期內持續持有比較高的丟包率(檢測到的Lost計數器偏大),且速率保持一致,那麼BBR會將發送量限制在實際帶寬的平均值。
...

我一向對TCP是嗤之以鼻的,就像我對SSL/TLS協議嗤之以鼻一樣,於工作,我持續七年先後與SSL,TCP打交道,並且有時候還做的不錯,於私下,我呻吟著在詛咒中夾雜著叫罵,希望盡快結束這個丑行。每當我想到這些的時候,我甚至都有摔電腦的沖動,然而很多人會有疑問,我既然如此惡心這些,還為何分析它們,還為何如此上心...
我的求助開始了!

你有更好玩的東西嗎?昨晚我看了將TLS offload到網卡的一個演講,瞬間有了興趣,可是我不可能去搞什麼硬件,在後半夜又幸運的發現了一個KTLS的方案,我特別想今天把這個完成,然而作罷了,因為我沒有時間!(我曾經不還吐槽過OpenSSL嗎?是的,其實別人也有人吐槽,但人家改造了世界,實現額KTLS,而我,就是個傻逼!即便我是個傻逼,我也將OpenVPN移植到了內核,你呢?!)

TCP本身就是渣!這個渣渣玷污了IP網絡的偉大,破壞了IP網絡的簡單,就想一碗拉面裡的雞屎一樣!我希望,我希望呻吟著,呻吟著毆打所有與TCP相關的公司的老板,或者說,僅僅是咒罵!

Copyright © Linux教程網 All Rights Reserved