BBR, the new kid on the TCP block | APNIC Blog 這篇文章挺好的，下面很多內容也基于這篇文章而來。
擁塞避免用于避免因為發送者發送數據過快導致鏈路上因為擁塞而出現丟包。
TCP 連接建立后先經過 Slow Start 階段，每收到一個 ACK，CWND 翻倍，數據發送率以指數形式增長，等出現丟包，或達到 ssthresh，或到達接收方 RWND 限制后進入 Congestion Avoidance 階段。下面這個圖挺好的，描述了好幾個過程，找不到出處了，只是列一下圖吧。
一些基礎東西可以看： TCP congestion control - Wikipedia
BDP
BDP 是 Bandwidth and Delay Product. 就是帶寬 (單位 bps) 和延遲 (單位 s) 的乘積，單位是 bit，也是 Source 和 Destination 之間允許處在 Flying 狀態的最大數據量。Flying 也叫 Inflights，就是發送了但還未收到的 Ack 的數據。
來自[3]。
實際發送速率乘以延遲得到的值越接近 BDP 說明算法的效率越高。
Reno
Reno 這種叫做 ACK-Pacing ，基于 Ack 來確認網絡狀況。如果能持續收到 ACK，表示網絡能正常承載當前發送速率。
Reno maintains an estimate of the time to send a packet and receive the corresponding ACK (the “round trip time,” or RTT), and while the ACK stream is showing that no packets are being lost in transit, then Reno will increase the sending rate by one additional segment each RTT interval.
Reno 下，每收到一個 ACK，CWND 加一，等出現丟包之后發送者將發送速率減半。理想狀況下，Reno 能走出如下曲線：
來自[1]
Reno 有如下假設：
- 丟包一定因為網絡出現擁塞，但實際可能網絡本身不好，可能有固有的丟包概率，所以假設并不嚴謹；
- 網絡擁塞一定是因為網絡上某個 buffer overflow 了；
- 網絡的 RTT 和帶寬穩定不容易變化；
- 將速率減半以后，網絡上的 buffer 一定能夠從 overflow 變為 drain。也即對網絡上 Buffer 大小也有假設；
從上面假設能看出，Reno 下受鏈路上 Buffer 大小影響很大。當 Buffer 較小的時候，鏈路上實際處在發送狀態的數據量還未達到 BDP (Bandwidth delay product) 時候可能就會出現丟包，導致 Reno 立刻減半發送速率，從而無法高效的利用網絡帶寬。如果 Buffer 很大，超過 BDP，可能會進入 “Buffer Bloat” 狀態，即延遲畸高，因為即使 Reno 速度降為一半依然不能保證使鏈路 Buffer 清空，或者說可能大部分時間鏈路上 Buffer 都處在非空狀態，且每次 Reno 因為丟包而降速時，會做數據重傳，導致之前發送的可能還依舊在鏈路上排隊的數據空占資源沒起到作用最終白白丟掉，于是讓整條鏈路上持續存在固有延遲。
Reno 的問題：
- 上面提到了，受鏈路 Buffer 影響很大；
- 對高帶寬網絡，比如帶寬是 10Gbps，即使假設延遲非常低只有 30ms，每個 RTT 下 CWND 增加 1500 個八進制數，得好幾個小時才能真的利用起這個帶寬量，并且要求這幾個小時內數據都不能有丟包，不然 Reno 會降速；
- Reno 每收到一個 Ack 就開始擴大 CWND，對鏈路上一起共享鏈路的其它 RTT 較大的連接不友好。比如一個連接 RTT 很低，它的 CWND 會比別的共享鏈路的連接大，不公平的占用更多帶寬；
BIC
BIC 叫 Binary Increase Congestion Control，是在 Reno 基礎上做改進，將 CWND 擴大過程分成三個階段，第一階段是在遇到丟包后將 CWND 降為 β × Wmax ，（一般 β 是 0.5，Wmax 是丟包時 CWND）但記住之前 Wmax 最大值，之后以一個較快速度增加 CWND，在接近 Wmax 后 CWND 增加量是一個 Wmax 和 CWND 之間的二次函數，稱為 Binary Increase，逐步去接近 Wmax，到達 Wmax 后又轉換為二次曲線去探測下一個極限。具體內容可以看 Wiki，在這里： BIC TCP - Wikipedia
大概是這么個圖，好處就是丟包后能快速恢復，并在穩定期盡力保持更長時間，還能支持探測更高帶寬值。
來自[3]
Cubic
Cubic 在 BIC 的基礎上，一個是通過三次函數去平滑 CWND 增長曲線，讓它在接近上一個 CWND 最大值時保持的時間更長一些，再有就是讓 CWND 的增長和 RTT 長短無關，即不是每次 ACK 后就去增大 CWND，而是讓 CWND 增長的三次函數跟時間相關，不管 RTT 多大，一定時間后 CWND 一定增長到某個值，從而讓網絡更公平，RTT 小的連接不能擠占 RTT 大的連接的資源。
平滑后的 CWND 和時間組成的曲線如下，可以看到三次曲線保留了 BIC 的優點，即在丟包后初期，CWND 能快速增長，減小丟包帶來的影響；并且在接近上一個 CWND 最大值時 CWND 增長速度又會非常慢，要經歷很長時間才能超越 Wmax，從而能盡力保持穩定，穩定在 Wmax 上；最后在超越 Wmax 后初期也是增長的非常慢，直到后來才快速的指數形式增長，用于探測下一個 Wmax。
來自[3]
Cubic 最終出來的曲線如下。黃色是 CWND，藍色線是網絡上隊列擁塞包數。藍色箭頭表示 queue fill，綠色箭頭表示 queue drain。看到有兩個淺綠色的線，高的是開始丟包，低的是隊列開始排隊。因為這里畫的是說網絡上 bandwidth 是固定的，buffer 也是固定的，所以 Cubic 下沒有超越 Last Wmax 繼續探測下一個 Wmax 的曲線，都是還未到達第一次的 Wmax 時候就因為丟包而被迫降低了 CWND。第一次個黃色尖峰能那么高是因為當時網絡上 buffer 是空的，后來每次丟包后 Buffer 還沒來得及完全清空 CWND 又漲上來導致數據排隊了，所以后來的黃色尖峰都沒有第一個高。
來自[3]
Cubic 的優勢：
- 因為跟 RTT 無關所以更公平；
- 更適合 BDP 大的網絡。Reno 不適合是因為它依賴 RTT，BDP 大的時候 RTT 如果很高，會很久才能將傳輸效率提上去；
Cubic 缺點：
- 當 Bandwidth 變化時候，Cubic 需要很長時間才能從穩定點進入探測下一個 Wmax 的階段；
- 更易導致 Bufferbloat。Reno 下如果鏈路上 Buffer 很大出現擁塞后 RTT 也會很長，很久才會收到 ACK，才會增加 CWND；但 Cubic 的 CWND 增長跟 RTT 無關，到時間就增長，從而更容易加劇鏈路負擔。Bufferbloat 可以看下節。
綜合來看 Cubic 適合 BDP 大的高性能網絡，性能意思是帶寬或者說發送速率，發送速率足夠大 Cubic 把 Buffer 占滿后才能快速清空，才能有較低的延遲。
一個挺好的講 Cubic 的 PPT： Cubic ，還有 論文 。linux 2.6 時候用的 CUBIC。
Bufferbloat
Bufferbloat 在 Bufferbloat - Wikipedia 講的挺好了。簡單說就是隨著內存越來越便宜，鏈路上有些設備的 Buffer 傾向于配置的特別大，而流行的 TCP Congestion Avoidance 算法又是基于丟包的。數據在隊列排隊說明鏈路已經出現擁塞，本來應該立即反饋給發送端讓發送端減小發送速度的，但因為 Buffer 很大，數據都在排隊，發送端根本不知道自己發出去的數據已經開始排隊，還在以某個速度 (Reno）甚至更高速度(Cubic，到時間就增加 CWND) 發送。等真的出現丟包時候，發送端依然不知道出現了丟包，還會快速發消息，直到丟的這個包被接收端感知到，回復 ACK 后發送端才終于知道要降低發送速度。而重傳的包放在鏈路上還得等之前的數據包都送達接收端后才能被處理。如果接收端的 Buffer 不足夠大，很多數據送達接收端后都會丟棄，得等重傳的包到達（Head Of Line 問題）后才能送給上游，大大增加延遲。
Bufferbloat 一方面是會導致網絡上超長的延遲，再有就是導致網絡傳輸不穩定，有時候延遲很小，有的時候延遲又很大等。
可以參考： Bufferbloat: Dark Buffers in the Internet - ACM Queue
PRR
在 CUBIC 之上又有個優化，叫做 Proportional Rate Reduction (PRR)，用以讓 CUBIC 這種算法在遇到丟包時候能更快的恢復到當前 CWND 正常值，而不過分的降低到過低的水平。
參考： draft-mathis-tcpm-proportional-rate-reduction-01 - Proportional Rate Reduction for TCP 。不進一步記錄了。Linux 3.X 的某個版本引入的，配合 CUBIC 一起工作。
鏈路上的隊列模型
為了進一步優化 Cubic，可以先看看鏈路上隊列的模型。
- 當鏈路上數據較少時，所有數據都在發送鏈路上進行發送，沒有排隊的數據。這種情況下延遲最低；
- 當傳輸的數據更多時候，數據開始排隊，延遲開始增大；
- 當隊列滿的時候進入第三個狀態，隊列滿了出現丟包；
來自[1]
最優狀態是 State 1 和 State 2 之間，即沒有出現排隊導致延遲升高，又能完全占滿鏈路帶寬發送數據，又高效延遲又低。 而基于丟包的 Congestion Avoidance 策略都是保持在 State 2 的狀態。而 Cubic 是讓 CWND 盡可能保持在上一個 Wmax 的狀態，也即 State 2 末尾和即將切換到 State 3 的狀態。所以 Cubic 相當于盡可能去占用鏈路資源，使勁發數據把下游鏈路占滿但犧牲了延遲。
于是可以看到，為了保持在 State 1 和 State 2 狀態，我們可以監控每個數據包的 RTT，先盡力增大 CWND 提高發送率如果發現發送速率提高后 RTT 沒有升高則可以繼續提高發送速率，直到對 RTT 有影響時就減速，說明從 State 1 切換到了 State 2。
我們希望讓 CWND 盡力保持在下面圖中標記為 optimum operating point 的點上，即 RTT 又小，鏈路上帶寬又被占滿。在這個圖上，RTprop 叫做 round-trip propagation time ，BtlBw 叫做 bottleneck bandwidth 。橫軸是 inflights 數據量，縱軸有兩個一個是 RTT 一個是送達速度。看到圖中間有個很淡很淡的黃色的線把圖分成了上下兩部分，上半部分是 Inflights 數據量和 Round trip time 的關系。下半部分是 Inflights 和 Delivery Rate 的關系。
這里有四個東西需要說一下 CWND、發送速度、inflights，發送者帶寬。inflights 就是發送者發到鏈路中還未收到 ACK 的數據量，發送速度是發送者發送數據的速度，發送者帶寬是發送者能達到的最大發送速度，CWND 是根據擁塞算法得到的當前允許的 inflights 最大數據量，它也影響著發送速度。比如即使有足夠大的帶寬，甚至有足夠多的數據要發，但 CWND 不夠，于是只能降低發送速度。這么幾個東西會糾纏在一起，有很多文章在描述擁塞算法的時候為了方便可能會將這幾個東西中的某幾個混淆在一起描述，看的時候需要盡力心里有數。
回到圖，藍色的線表示 CWND 受制于 RTprop，綠色的線表示受制于 BltBw。灰色區域表示不可能出現的區域，至少會受到這兩個限制中的一個影響。白色區域正常來說也不會出現，只是說理論上有可能出現，比如在鏈路上還有其它發送者一起在發送數據相互干擾等。灰色區域是無論如何不會出現。
先看上半部分，Inflights 和 Round-Trip Time 的關系，一開始 Inflights 數據量小，RTT 受制于鏈路固有的 RTprop 時間影響，即使鏈路上 Buffer 是空的 RTT 也至少是 RTprop。后來隨著 Inflights 增大到達 BDP 之后，RTT 開始逐步增大，斜率是 1/BtlBw ，因為 BDP 點右側藍色虛線就是 Buffer 大小，每個藍點對應的縱軸點就是消耗完這么大 Buffer 需要的時間。 消耗 Buffer 的時間 / Buffer 大小 就是 1/BltBw ，因為消耗 Buffer 的時間乘以 BltBw 就是 Buffer 大小。感覺不好描述，反正就這么理解一下吧。主要是看到不可能到灰色部分，因為發送速率不可能比 BltBw 大。等到 Inflights 把 Buffer 占滿后到達紅色區域開始丟包。
下半部分，Inflights 比較小，隨著 Inflights 增大 Delivery Rate 越大，因為此時還未達到帶寬上限，發的數據越多到達率也就越高。等 Inflights 超過 BDP 后，Delivery Rate 受制于 BtlBw 大小不會繼續增大，到達速度達到上限，Buffer 開始積累。當 Buffer 達到最大限度后，進入紅色區域開始丟包。
之前基于丟包的擁塞算法實際上就是和鏈路 Buffer 一起配合控制 Inflights 數據量在 BDP 那條線后面與 BDP 線的距離。以前內存很貴，可能只比 BDP 大一點，基于丟包的算法延遲就不會很高，可能比最優 RTT 高一點。但后來 Buffer 越來越便宜，鏈路上 Buffer 就傾向于做的很大，此時基于丟包的擁塞算法就容易導致實際占用的 Buffer 很大，就容易出現 BufferBloat。
為了達到最優點，發送速率必須達到 BltBw，從而占滿鏈路帶寬，最高效的利用帶寬；再有需要控制 Inflight 數據量不能超過鏈路的 BDP = BtlBw * RTprop ，從而有最優的延遲。發送速率可以超過 BltBw，可以有隊列暫時產生，但數據發送總量不能超 BDP，從而讓平均下來延遲還是能在最優點附近。
來自[4]
TCP Vegas
Vegas 就如上面說的理想中算法一樣，它會監控 RTT，在嘗試增加發送速率時如果發現丟包或者 RTT 增加就降低發送速率，認為網絡中出現擁塞。但它有這些問題：
- CWND 增長是線性的，跟 Reno 一樣需要很久才能很好的利用網絡傳輸速率；
- 最致命的是它不能很好的跟基于丟包的 Congestion Avoidance 共存，因為這些算法是讓隊列處在 State 2 和 3 之間，即盡可能讓隊列排隊，也相當于盡可能的增大延遲，但 Vegas 是盡可能不排隊，一發現排隊就立即降低發送速率，所以 Vegas 和其它基于丟包算法共存時會逐步被擠出去；
BBR
估計 BtlBw 和 RTprop
延續前面說的，要把發送速率調整到跟 BDP 差不多大是最優的。因為網絡環境會持續變化，所以需要持續監控 RTprop 和 BtlBw 的值。
RTprop 是鏈路固有傳輸延遲，我們無法直接監控到它，我們只能通過監控數據包的 RTT 來間接的得到 RTprop 的趨近值。RTT 和 RTprop 關系如下：
η 是其它因素導致的 noise 延遲，包括接收端延遲 ack 等原因導致的延遲。因為 RTprop 是鏈路上的固有延遲，可以認為只有鏈路上選擇的路徑變化時候它才會變化，并認為它變化頻率很低，變化間隔時間遠大于 η。η 一定是正數，RTT 無論如何不可能低于 RTprop，所以可以在一個時間窗口 Wr 內（一般是在幾十秒到幾分鐘之間）監控最小的 RTT 的最小值，認為就是近似為 RTprop。
BtlBw 也是靠 Ack 來監控。每收到一個 Ack 一方面是知道數據延遲 RTT 是多少，再有送達的數據量是多少。我們在一個短的時間窗口 deltaT 內通過 Ack 計算對面收到了多少數據，得到 deliveryRate = deltaT 時間內送達數據量 / deltaT ，這個速率一定低于鏈路上瓶頸速率，bottleneck rate。因為我們計算 deliveryRate 時使用的數據送達量是精確值，是在 Ack 里數據接收方明確告訴我們的。而我們為了做帶寬計算等待的 deltaT 時間一定大于實際時間，所以 deltaT 時間內送達數據量 / deltaT 計算得到的 deliveryRate 一定小于等于真實 deliveryRate，這個真實 deliveryRate 又一定小于等于鏈路物理 bottleneck rate。所以：
這里時間窗口 Wb 一般是 10 個 RTT。
RTprop 和 BtlBw 是兩個獨立的量，RTprop 變化比如選擇的鏈路變化時，bottleneck 可能是一樣的 BltBw 不變；BtlBw 變化時候選擇的鏈路可能沒有變化，比如一個無線網絡改變了發送速率，鏈路不變但帶寬變大了。
從之前看過的下面這個圖能知道，RTprop 只能在 BDP 線左側被觀測到，即發送數據比較少，inflight 數據量沒有到 BDP 的時候；BtlBw 只能在 BDP 線右側能被觀察到，即 inflight 數據超過 BDP，延遲開始增大時被觀測到。直觀一點說就是鏈路上隊列沒排隊時候，你知道鏈路延遲是多少，但不知道隊列最大消費速度是多少，當隊列開始出現排隊后，你在發送端計算得到接收率不變了，RTT 延遲也升高了，知道最大接收率是多少，但又不知道鏈路上實際延遲是多大了，因為多了數據排隊的時間。
估計帶寬時候還一個需要處理的，跟 RTT 不同，RTT 是只要有應用層數據發就能測得，就能更新估計值，但 BtlBw 的話必須應用層有足夠數據發才能估計。所以下圖可以看到有個 App Limited。BBR 會將因為 app 沒足夠數據發而導致測得的 BtlBw 過小的情況丟棄，只記錄有足夠數據發的情況下得到的 BtlBw。實際上鏈路中實際 BtlBw 是個 hard limit，就是無論我們怎么測都不可能超過鏈路上實際 BtlBw，所以只要在窗口內測得小的 BtlBw 都可以丟掉，就用測試周期內最大的 BtlBw。
來自[4]
BBR 的狀態機
BBR 在控制擁塞時候會在一組狀態之間進行切換，如下圖：
來自[2]
先簡單介紹一下下面再針對每個狀態更細一些說。初始狀態就是 Startup，BBR 因為不知道當前帶寬到底是多少，也會有類似 Slow Start 的過程，逐步增加發送速度探測 BtlBw。等到探測到 BtlBw 后因為 Startup 階段發了很多數據出去，inflights 很大，可能鏈路會有排隊，所以進入 Drain 階段去做清理，讓鏈路上的隊列清空；之后進入穩定期，會周期性的在 ProbeBW 和 ProbeRTT 兩個狀態之間進行切換，間歇的探測 BtlBw 和 RTprop。
BBR 穩定期工作機制
先記錄穩定期再寫 Startup 等。BBR 每收到一個 ACK ，就會估計 RTprop 和 BtlBW (deliveryRate)，盡力保證 inflight 數據量跟估計得到的 BDP 差不多。BBR 下 inflights 數據量由內部的 target_cwnd 控制，而 target_cwnd 是個比 BDP 稍微大一點點的量。
假設鏈路上 RTprop 和 deliveryRate 一直保持不變，BBR 處在穩定狀態一直發送數據，它保證 inflights 的數據量不會超估計的 BDP 很多。此時鏈路上 Bottleneck 在發送端，由發送端控制發送速度。如果鏈路上帶寬提高了，因為 Bottleneck 在發送端，發送端會感知不到帶寬變化。所以 BBR 需要周期性的提高發送速率將 Bottleneck 從發送端移到鏈路上去探測鏈路上的帶寬，這就是 ProbeBW 狀態的來源。名字也可以看出它含義是探測帶寬，探測的是鏈路上 Bottleneck 的帶寬。
ProbeBW 狀態下先開始增周期，即提高發送率到穩定期的 1.25 倍，直到出現丟包或 inflights 數據量達到 1.25 倍 BDP 為止。觀察延遲是否升高，如果延遲升高且 deliveryRate 不變，說明鏈路上帶寬沒有變化且產生了隊列堆積；接下來會進入減周期，降低發送率到穩定期的 0.75 倍，等待一個 RTprop 或 inflights 數據量低于 BDP 為止，用以讓鏈路上在增周期出現堆積的隊列清空。之后再保持 inflights 等于 BDP 穩定數個 RTprop 后再次開始增周期。
之前提到 BBR 每次收到 ACK 會嘗試更新 RTprop，而 RTprop 取的是窗口期內最低的 RTprop。如果 BBR 運行了很長時間一直沒有更新 RTprop，即很長一段時間都沒有比當前使用的 RTprop 更低的 RTprop 時，BBR 會進入 ProbeRTT 狀態，用于探測 RTprop。比如鏈路上帶寬出現減少，鏈路上出現堆積，保持發送速度或繼續進行 ProbeBW 的話會讓鏈路上堆積更加嚴重，RTT 上升。所以 RTprop 一直不會被更新。
ProbeRTT 下 BBR 將 CWND 降到很低的值，典型的是 4 個 MSS，持續一段至少 200ms 或一個 RTprop。這么一來 Inflights 數據量會突降。再判斷鏈路是否處在 full_pipe 狀態，是的話則進入 ProbeBW，不是則進入 Startup。
full_pipe 判斷主要是靠最近的增周期中，發送率提高后 deliveryRate 是否有大幅度增加，有相應幅度的增加說明鏈路可能還沒有滿載，我們加快發送速率還是能發的出去，沒增加則表示鏈路是滿載的，發送速度加快但是接收速率沒跟上。有個 Linux 內的 BBR 實現 ，可以看。
之前提到了 RTprop 和 BtlBw 兩個量是測準一個另一個就測不準，穩定期測量這兩個值的任務大多數時候都由 ProbeBW 獨自完成，在增周期提高發送帶寬發多數據到鏈路探測 BtlBW，在減周期減小發送帶寬減少發送速率從而減小 Inflights，看估計的 RTprop 是否降低，降低了則說明測到了最新的 RTprop。如果很長時間都沒有更低的 RTprop 出現，可能鏈路發生了切換，這時候才需要切換到 ProbeRTT 去探測最新的 RTprop。從 ProbeRTT 的機制能看到它對性能是有影響的，所以 BBR 是盡力減少 ProbeRTT 時間占比，大部分時間都在 ProbeBW 狀態。
整體過程如下圖，在一個 10Mbps 帶寬，延遲 40ms 的網絡下取了 700ms 時長的數據。圖中縱軸有 RTT，inflight，和 Bandwidth (BW)。帶寬部分有兩個值，紅色的是發送方計算出來的 Delivery Rate，緊挨著紅色線的黑線是當前估計出來的 BtlBw。可以看到 Delivery Rate 波動但估計出來的 BtlBw 變動不大，因為是每次有估計出 Delivery Rate 后將這個值放入估計 BtlBw 的滑動統計窗口內，取滑動窗口內的最大值為 BtlBw，也即那個黑色線，所以紅色線變動后，黑色線不會立即變動。黑色線上面的灰色框是 cycle gain 用于控制發送速度， cycle gain * 估計的 BtlBw 就是發送方當前需要的發送速度。每個周期通過控制 cycle gain 來定期的提高發送速度，以探測當前鏈路上 BtlBw 是否提高。
對于黑色的圈我們從起點開始說，起點是紅線，即 Delivery Rate 計算出來后，放入 max BtlBw 滑動窗口估算 BtlBw 是多少。之后 1.25 這個 cycle_gain 時用之前估算的 BtlBw 乘以 1.25 作為發送速度發消息，增周期發消息多了以后鏈路 Inflights 增大，RTT 增大，發出的消息看到是在 1.00 這個 cycle_gain 才被 Ack，計入 Delivery Rate，并讓 max BtlBw 稍微增加了一點點，看到紅線峰值比紅線上面的細黑線高了一點，于是將細黑線也向上推了一點點。
圖中 RTT，Inflights， cycle_gain ，Delivery Rate 大致都是對齊的，可以看到增周期時候 Delivery Rate ，Inflights 和 RTT 增加，減周期是減少。
來自[4]
下圖是帶寬從 10Mbps，40ms 延遲提到到 20Mbps 又降回 10Mbps 的過程。帶寬提高后看到在 ProbeBW 的增周期， BBR 發現提高發送速度后 RTT 沒有變化，且計算出來的 deliveryRate 有升高，更新 BtlBw 到新值，穩定期發送速度比原來高了 25%。在接下來三個周期內，每一次發送速率提高 25% 后延遲都沒有變化，且 deliveryRate 得到提高，最終在第四個探測周期重新出現藍色小三角，即鏈路上隊列有排隊后說明鏈路進入 full_pipe 狀態開始穩定發送速率。
下半部分是帶寬從 20Mbps 降低到 10Mbps，BBR 內因為維護了 BtlBW max filter 即從一個窗口期內采樣得到的 BtlBw 值中取最大值作為當前鏈路的 BtlBw。所以即使帶寬出現突降，因為 20Mbps 的 BtlBw 還在 max filter 內緩存著，這段時間 BBR 依然認為 BtlBw 是 20Mbps，會按照原來的發送速度繼續發數據。于是帶寬突降后延遲和 inflight 數據量大幅度增加。 但 inflights 數據量最大不能超過 BBR 內的 target cwnd，其值等于 `cwnd gain * 估計的 BDP`，BBR 會始終控制發送速率保持 inflights 在 target cwnd 內，cwnd gain 比 1 大，但不會大很多，所以帶寬突然變小后 inflights 不會無限增加，并且會維持一個固定值，在圖中表現為 40s ~ 42s 之間的一條水平線。這個期間即使處在 ProbeBW 階段也無法執行增周期按 1.25 倍速率發數據，因為 target cwnd 是滿的，必須遵從它的限制，它限制了發送端不能讓 inflights 數據量比它大。Inflights 和 RTT 能是一條水平線說明鏈路上 Buffer 比較大，能承載 target cwnd 下的數據量且不出現丟包。
補充一下 BBR 里有兩個聽起來很像的東西，pacing gain 和 cwnd gain。pacing gain 用來在 ProbeBW 內周期性的控制發送速率，發送速率等于估計的 `BtlBw * pacing gain`。而 cwnd gain 用于控制 target cwnd，限制 inflights 數據量。
在 42s 開始，之前 20Mbps 的 BtlBw 估計值過期了，從 BtlBw max filter 的采樣窗口中滑出，根據過去一段時間 Ack 計算出來的到達重新估算 BtlBw，根據這個重新估算的 BtlBw 調整發送速度，所以發送速率大幅度下滑。因為當前的 Inflights 數量遠大于當前的 target_cwnd 也即 cwnd_gain * 新估計的 BtlBw ，所以發送方會完全不發數據等待 Inflights 下降，在圖上表現出 Inflights 突然掉下來。當 Inflights 小于當前 target_cwnd 后，ProbeBW 的周期特性又開始顯現，一個一個的小三角開始出來了。最終發送速率重新回到穩態。
看到這里時候我開始一直有個疑問，在 42s 到 44s 期間，隊列內一直有堆積，一個周期發送速度是 1.25，一個周期發送速度是 0.75，豈不是剛好把發多少數據消費掉，但隊列內堆積的 inflights 不是依然保持沒有被消費掉嗎？不該是下降趨勢。
后來知道，ProbeBW 期間一個周期大致上是一個 RTT 時間，但發送速度 1.25 的周期和發送速度 0.75 的周期并不是嚴格等長的。1.25 周期時長是 inflights 數量到達 1.25 倍估計的 BDP 或有數據丟包。0.75 周期長度是一個完整的估計的 RTprop，或者 inflights 低于估計的 BDP。發送者能感知到 inflights 低于 BDP 的時候實際 inflights 一定低很多了，所以 BBR 的 inflights 曲線都是像心跳一樣，上面一個三角下面一個三角，而不是只有上面的三角。在 19 ~ 20s 的時候，上三角比下三角大。20 ~ 21s 因為帶寬變大了，但發送帶寬只是緩慢增加上去，所以下三角比上三角大很多，等到穩態以后又變成上三角大于下三角。42s 以后因為每個減周期都要等到 Inflights 低于估計的 BDP，所以綠線一路向下。
對于藍色的線我們知道鏈路上延遲是固有時間，所以它最低點是一條直線，增周期時延遲只會有上三角，沒下三角。
注意下圖沒有 ProbeRTT 出現。我理解是因為 RTprop 還未超時就被更小的值更新了。
來自[4]
BBR 的 startup
鏈路上帶寬跨度很大，從幾個 bps 到上百 Gbps，所以 BBR 一開始也會以指數形式增大 BtlBw，每一個 RTT 下發送速度都增大 2/ln(2) 約 2.89 倍，從而在 O(log(BDP)) 個 RTT 內找到鏈路的 BtlBw，log 的底是 2。BBR 在發現提高發送速度但 deliveryRate 提高很小的時候標記 full_pipe ，開始進入 Drain 階段，將排隊的數據包都消費完。BBR 能保證排隊的數據最多為實際 BDP 的 1.89 倍。BBR 下并沒有 ssthresh，即 CUBIC 那樣增加到某個配置值后開始進入線性增加 CWND 階段。
Drain 階段就是把發送速率調整為 Startup 階段的倒數。比如 Startup 階段發送速度是 2.89，那 Drain 階段發送速度是 1/2.89 。BBR 會計算 inflights 數據包量，當與估計的 BDP 差不多的時候，BBR 進入 ProbeBW 狀態，后續就在 ProbeBW 和 ProbeRTT 之間切換。
下圖是在 10Mbps，40ms 延遲網絡下的 Startup 階段的圖，綠色是發送方發送數據量，藍色是接收方收到的數據量。紅色是 CUBIC 在同樣環境的發送數據量，作為對比。下圖綠色線的斜率就是發送速度，同一時間點綠色線上的點和藍色線上的點的差值就是那個時刻 inflights 數據量。
看到 BBR 在 0.25s 之前是曲線，10Mbps 40ms 延遲的網絡下 BBR 允許的 BDP 為 0.04Mb，0.25 時間點上綠色和藍色線差值大約 0.1Mb，大致是 0.04Mb 的 2.89 倍。即 BBR 在一開始指數的快速提升發送速度，但快到了 0.25s 的時候，RTT 開始升高，inflights 提高后 deliveryRate 并沒有相應提高，BBR 開始維持在一個速度等待幾個 RTT 周期以確認鏈路確實承載不了當前的發送速度，所以 0.25s ~ drain 之前綠線斜率不變。到 Drain 后 RTT 迅速下降，Acked 數據量圖的斜率也降低很多。在找到 RTprop 之后進入 ProbeBW 狀態。
紅線的話就是看到 CUBIC 更早的切換到線性增長，但之后會逐步增加發送包數量直到丟包。但下圖上半部分看紅線看不太出來發送率在增加，只是能隱約的感覺到 0.25 時間點時紅線和藍線的間隔似乎小于 0.75 時間點時他倆的間隔。
來自[4]
下面是 BBR 和 Cubic 在延遲時間上的對比。BBR 開始延遲大但隨即恢復。CUBIC 一直增長下去直到丟包，再減小再增長。
來自[4]
當多個 BBR 流在同一個鏈路時如下圖。基本上就是靠 BtlBw max filter 內 BtlBw 超時過期以及 ProbeRTT 逐步讓每個 BBR 流都找到自己合適的份額。在一開始只有紅色的線，之后綠的來了，紅色線繼續按原來速度發數據鏈路一定會擁塞，并且因為有兩個流了紅線的 deliveryRate 一定會下降，BtlBw 超時后紅線降低發送速率。大致上就是這么相互作用，每來一個流需要調整一下直到穩定。
來自[4]
BBR 跟 CUBIC 等基于丟包的算法共存時會有問題嗎？
列一下 Reno，CUBIC，BBR 三個在時間和發送速率上的圖做對比。
來自[1]
之前提到 TCP Vegas，Vegas 會被基于丟包的算法擠掉份額，不能跟這些算法共存，所以無法流行起來。對于 BBR 的話，它搶占份額的方式主要靠 ProbeBW 期間按 1.25 倍估計值發送數據，會給鏈路帶去壓力，為自己搶占生存空間；再有就是 Startup 階段，BBR 相對 CUBIC 來說會為鏈路帶去更多數據去搶占份額，這個只在初始階段有用，但如果 BBR 上的數據如果能持續發送，初始期占的份額可能就能一直保持下去。
對 BBR 和基于丟包的 Congestion Avoidance 的分析有兩種不同的結果：
- BBR 在 ProbeBW 階段雖然會將發送速度提高到 1.25 倍但畢竟持續時間短，一半以上的時間還是以估計速率在發數據。如果不能給鏈路帶去足夠壓力，BBR 會被其它基于丟包的算法擠掉，因為 BBR 會認為延遲升高了，需要降低自己的發送速度，這么逐步降低；
- BBR 可能錯誤的估計鏈路延遲，比如估算鏈路是否有排隊主要通過 RTT 有沒增加完成，但 RTT 即使不增加可能鏈路也有排隊，比如鏈路上隊列處在基本滿的狀態，BBR 認為此時的 RTT 就是鏈路 RTT 最小值，于是保持速度發數據，它還容忍丟包，但基于丟包的算法在此時就會降速。
據說 google 給出來說 BBR 可以很好的跟 CUBIC 等算法共存，但參考 [1] 的Sharing 一節在兩種場景測試發現 BBR 比 CUBIC 占用更多資源或者說份額。
BBR 如何處理丟包
在網上搜很多文章都說 BBR 根本不管丟包，完全基于自己的周期即 ProbeBW 內的周期去計算發送率，CWND 來發數據包，所以 BBR 根本無視丟包。但實際上 BBR 作者寫的 BBR 介紹里明確說了 BBR 是會管丟包情況的，來自 BBR: Congestion-Based Congestion Control - ACM Queue ：
The network path and traffic traveling over it can make sudden dramatic changes. To adapt to these smoothly and robustly, and reduce packet losses in such cases, BBR uses a number of strategies to implement the core model. First, BBR treats cwnd_gain×BDP as a target that the current cwnd approaches cautiously from below, increasing cwnd by no more than the amount of data acknowledged at any time. Second, upon a retransmission timeout, meaning the sender thinks all in-flight packets are lost, BBR conservatively reduces cwnd to one packet and sends a single packet (just like loss-based congestion-control algorithms such as CUBIC). Finally, when the sender detects packet loss but there are still packets in flight, on the first round of the loss-repair process BBR temporarily reduces the sending rate to match the current delivery rate; on second and later rounds of loss repair it ensures the sending rate never exceeds twice the current delivery rate. This significantly reduces transient losses when BBR encounters policers or competes with other flows on a BDP-scale buffer.
更長的在這里： Modulating cwnd in Loss Recovery
細節很多，我看的很暈。在看 BBR 處理丟包策略前，至少得先回憶一下 TCP 的丟包處理機制，一個是 Retransmission Timeout (RTO)，一個是 Fast Retransmission，這兩個概念就不記錄了，可以翻一下 Wiki。大致上是說如果遇到重傳 RTO，發送者會認為所有 Inflights 數據都丟了，CWND 會降為 1 MSS，行為和 CUBIC 類似。在之后持續收到 ACK 的話，會逐步增加 CWND 值。每次 ACK 時候一方面會更新各種統計值，再有會更新 CWND 值，CWND 的增幅就是每次收到 ACK 時候 ACK 的數據量。每個 ACK 都會嘗試去更新，直到 CWND 達到 target_cwnd 即當前估計的 BDP 和 cwnd_gain 的乘積。
如果是 Fast Retransmission，發送者則認為鏈路遇到丟包但仍然存在有效 Inflights 數據。 這時首先將 CWND 降低到當前與當前 deliveryRate 相匹配的值，之后一段時間發送速率不能超過 deliveryRate 的兩倍。直到退出 Fast Retransmission 階段后，CWND 恢復為丟包出現前記錄的 CWND 值。就是說在 RTO 或 Fast Retransmission 前會記錄當時 CWND，在出 Fast Retransmission 或 RTO 后恢復到記錄的 CWND。
總之說 BBR 處理丟包的時候需要區分 RTO 和 Fast Retransmission 兩個場景，RTO 下與 CUBIC 差不多；只有 Fast Retransmission 下，發送速率還能保持在較高位置，但也是受影響的。
下面是 CUBIC （紅色）和 BRR （綠色）在面對丟包的時候吞吐量表現。CUBIC 在丟包 1% 的時候基本就無法工作了，BRR 能扛到 20% 的丟包率。黑線是理想狀況下的吞吐量，因為有丟包存在，所以吞吐量隨著丟包率升高而遞減。
來自[4]
對于右側綠線是個斷崖式有這么一些原因：
- 丟包率高了以后一個是會引起 Fast Retransmission，會對吞吐量有影響，另一個是可能出現 RTO，出現 RTO 后 CWND 立即降到 1 跟 CUBIC 表現就一致了，吞吐量會大幅度下滑；
- 丟包率高了之后會嚴重影響實際 Delivery Rate 的計算，讓計算得到的值比實際值小，進而讓 BBR 錯誤估計當前 BtlBw，減小發送速率。因為丟包率固定不變，減小發送速率后 Delivery Rate 可能會進一步減小，最終降為 0；
- 最后，這個圖本身就是指數的，即使是理想狀態也會是個斷崖；
對于為什么是丟包率接近 ProbeBW 增周期增益 (1.25) 時會出現吞吐量大幅度下滑我理解是這樣的：
在估計 BtlBw 時是取過去一段時間內的最大值，比如丟包率是 10%，如果沒有增周期發送者通過 Delivery Rate 計算得到的帶寬比實際 BtlBw 會低 10%，之后會調整發送速度變成 90% BtlBw，因為依然有 10% 的丟包率，在 90% BtlBw 從估計帶寬用的滑動窗口過期移除后，發送速率會降為 90% * 90% BtlBw = 81% BtlBw ，最終這么一步步下降到 0，這是沒有增周期的場景。
但是因為有增周期的存在，假設當前估算的帶寬為 BtlBw，普通周期發送速率就是 BtlBw，增周期是 1.25 BtlBw，減周期是 0.75 BtlBw。當丟包率是 10%，普通周期時計算出來的 Delivery Rate 是 90% BtlBw，增周期計算出來的是 1.25 * 90% * BtlBw = 1.125 BtlBw ，但實際上 BtlBw 是鏈路帶寬不可能超越 BtlBw，所以增周期 Delivery Rate 還是 BtlBw，減周期是 0.75 * 90% * BtlBw = 0.675 BtlBw ，這么一來根據過去一段時間 Delivery Rate 最大值估算帶寬時得到的帶寬還是 BtlBw，所以 10% 丟包率的時候吞吐量受丟包的影響不大。
當丟包率增長到 20% 的時候，根據上面的算法，增周期計算出來的 Delivery Rate 就馬馬虎虎剛好是 1 倍 BtlBw 了，因為 1.25 * 80% * BtlBw = 1 BtlBw 。只要有風吹草動讓計算的 Delivery Rate 低于最初的 BtlBw，那一步步的計算的 Delivery Rate 就會和實際帶寬偏離越來越大，最終降到 0。也就是說增周期的增益和丟包率的乘積能大于 1，就能保持發送速度，小于 1 則會斷崖式下滑，大于 1 是不可能的。
所以 BBR 對 CUBIC 在丟包方面的優勢是說，CUBIC 是算法結構上導致丟包一定會讓性能大幅度下滑。而 BBR 是在一定程度上能通過配置去容忍丟包。比如增周期增益提升到 1.5，抗丟包能力一定會大幅度提升，但性能受重傳數據影響會越來越大。
采樣的時候如果應用層沒數據發送怎么辦
BBR 數據都是基于采樣的，比如 ProbeBW 時候要按照 1.25 倍速率發數據，如果應用層沒有那么多數據要發怎么辦？
BBR 采樣時候會標記數據是不是 app limited。如果是因為 app 原因導致沒有足夠數據可發從而讓 deliveryRate 降低了，收到 ACK 的時候如果這個 deliveryRate 沒有高于現在估計的 BtlBw 最大值，則會丟棄這個 deliveryRate 不放入 BtlBw max filter。高于當前 BtlBw 最大值能放入 max filter 的原因是鏈路上的實際 BtlBw 是個 Hard Limit，不管怎樣都不可能超過，所以如果 app limited 狀態下 deliveryRate 都高于當前估算的 BtlBw，則說明估計值太小了。
既然 BtlBw max filter 是直接取采樣得到的 deliveryRate 的最大值，那 app limited 時候即使測得的 deliveryRate 不高于現在 BtlBw 也直接放入 max filter 不就好了，反正因為它小也不會被取到？
目前來看雖然理論上說每次 BBR 都取的是 deliveryRate 的最大值就行了，就是 BtlBw，但實際上 BtlBw max filter 并不是簡單的取最大值就完了，里面還有點基于時間的函數對窗口期內的所有 deliveryRate 做了一些計算才得到的 BtlBw。可以看參考 [2]。所以 app limited 的值如果沒有超過 BtlBw 則直接丟棄。
