2021-05-12 14:32:11
Google's BBR擁塞控制演算法如何對抗丟包
2020-06-16 17:30:04
我不知道該怎麼說。總之，便舍船，從口入，我看不到黃髮垂髫並怡然自樂！
在BBR之前，存在著兩種擁塞控制演算法，基於丟包的和基於時延的，不管哪一種都是基於探測的，換句話說，基於丟包的演算法將丟包作為一種發現擁塞的手段，而基於時延的演算法則是將時延增加作為發現擁塞的手段，它們之所以錯誤是因為它們的初衷就是錯的：
丟包演算法：
為了發現擁塞就不得不製造擁塞，這TMD的太JIBA諷刺了，為了戒毒，就必須先TMD的染上毒癮！然而根本沒毒癮的話何談戒毒！TCP之所以這麼玩我覺得很大程度上”歸功“於30多年前最初的關於擁塞控制的論文。在那個年代，和我們現在的網路完全不同，幾乎很少的佇列，由於記憶體比較貴，所以路由器和交換機上幾乎都沒有太深的佇列，甚至都是很淺的佇列，在那種情況下，丟包確實表明了擁塞的信號，然而後來隨著裝置佇列越來越深(摩爾定律使然)，在丟包前，一個TCP連線必須不斷的去填充非常深的佇列，當深佇列被填滿後，是什麼情況？是擁塞！
我不得不再次重複解釋時間延展性快取和時間牆快取的區別，對於前者，時間可以消耗掉任何封包，然而對於後者，時間牆的存在則必然會發生擁塞，如果不明白這個基本區別的話，就會設計出錯誤的擁塞控制方案。不幸的是，TCP在30年來都沒有對這兩類快取進行區分！同樣的大小，二者的表現完全不同！
後面我把時間延展性快取稱作第一類快取，時間牆快取稱作第二類快取。只有當第二類快取被填滿的時候，演算法才會發現擁塞，而此時，擁塞已經要開始緩解了！滯後性！
時延演算法：
OK！我承認時延演算法主動避免了第二類快取的資料堆積(如果你意識不到這一點，請停止閱讀。)，然而由於丟包演算法的存在，時延演算法一直處在被壓制的狀態。想知道時延演算法的問題，請自己百度，根本不需要google。
所以說，這些演算法都是錯的！那麼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.擁塞被動丟包
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
我之前說過，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.持續一段時間保持高丟包率；
當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移植到了核心，你呢？！)
本文永久更新連結地址：http://www.linuxidc.com/Linux/2016-10/136259.htm
相關文章