The math behind dynamics of TCP BBR

引

BBR中有很多諸如1.25，0.75，0.89，0.77之類的魔數字，它們是調教出來的經驗值呢，還是可以用數學推導發出來呢？

這些問題在結果導向的當今非常無聊，但也勉強僅圖一樂吧。對我自己而言，除了興趣還有一些執念。

我不相信背後沒有數學解釋的東西，一開始我看不上BBR，就是因為它沒有數學模型，類似AIMD，response function那樣優美的數學模型，沒有Reno/CUBIC中 t = α β p t=\alpha \sqrt {\dfrac{\beta}{p}} t=αpβ​

​這樣的公式。

後來經neal在内的BBR Development groups大佬們的指點，加入一些自己的思考，發現BBR的确沒有統一的數學模型，但在零散的每個細節背後都有嚴謹的數學，這讓人感到舒服且興奮。國慶節的清早，就把這些寫寫。

Startup狀态gain的确定

Startup狀态的gain在曆史上有兩個值，分别為2.89和2.77，它們的差别在于：

• 從cwnd算出pacing rate，則為2.89，這也是原始的理想結論。

• 從pacing rate算出cwnd，則為2.77，這是更加合理的最新結論。

  關于該話題，引述2018年和neal在BBR郵件讨論組裡的交流：

  

  下面挨個看。

2.77的推導

設 f ( x ) f(x) f(x)和 g ( x ) g(x) g(x)分别為BBR在Startup狀态的pacing rate函數和cwnd函數， P i n i t P_{init} Pinit​和 W i n i t W_{init} Winit​分别為初始pacing rate和初始cwnd，根據慢啟動原理：

f ( x ) = P i n i t × 2 x f(x)=P_{init}\times 2^x f(x)=Pinit​×2x

g ( x ) = W i n i t × 2 x g(x)=W_{init}\times 2^x g(x)=Winit​×2x

計算簡化起見，設 P i n i t = W i n i t = 1 P_{init}=W_{init}=1 Pinit​=Winit​=1.

cwnd與BDP是等計量的，BDP顯然是pacing rate在一個區間的積分：

如上圖，顯然有：

B D P x − 2 x − 1 = ∫ x − 2 x − 1 f ( x ) = ∫ x − 2 x − 1 2 x d x = 2 x 4 ln ⁡ 2 BDP_{x-2}^{x-1}=\int_{x-2}^{x-1}f(x)=\int_{x-2}^{x-1}2^xdx=\dfrac{2^x}{4\ln2} BDPx−2x−1​=∫x−2x−1​f(x)=∫x−2x−1​2xdx=4ln22x​

根據cwnd函數，則有：

W x = g ( x ) = 2 x W_{x}=g(x)=2^x Wx​=g(x)=2x

若 W x W_{x} Wx​是在 B D P x − 2 x − 1 BDP_{x-2}^{x-1} BDPx−2x−1​的基礎上通過乘以一個gain而來，設gain為 g g g，則：

W x = g × B D P x − 2 x − 1 = g × 2 x 4 ln ⁡ 2 = 2 x W_x=g\times BDP_{x-2}^{x-1}=g\times \dfrac{2^x}{4\ln 2}=2^x Wx​=g×BDPx−2x−1​=g×4ln22x​=2x

解出 g g g：

g = 4 ln ⁡ 2 ≈ 2.77 g=4\ln 2\approx 2.77 g=4ln2≈2.77

2.89的推導

預設和2.77的推導一緻，圖示不一樣：

如上圖，顯然有：

B D P x − 1 x = ∫ x − 1 x f ( x ) d x = 2 x 2 ln ⁡ 2 BDP_{x-1}^{x}=\int_{x-1}^xf(x)dx=\dfrac{2^x}{2\ln 2} BDPx−1x​=∫x−1x​f(x)dx=2ln22x​

若 B D P x − 1 x BDP_{x-1}^x BDPx−1x​是在 W x − 2 W_{x-2} Wx−2​的基礎上通過乘以一個gain而來，設gain為 g g g，則：

B D P x − 1 x = 2 x 2 ln ⁡ 2 = g × g ( x − 2 ) = g × 2 x 4 BDP_{x-1}^x=\dfrac{2^x}{2\ln 2}=g\times g(x-2)=g\times \dfrac{2^x}{4} BDPx−1x​=2ln22x​=g×g(x−2)=g×42x​

解出 g g g：

g = 2 ln ⁡ 2 ≈ 2.89 g=\dfrac{2}{\ln 2}\approx2.89 g=ln22​≈2.89

Drain狀态gain的确定

詳見下面“ProbeBW狀态drain階段的另一種可能(關于drain-to-target)”小節。

ProbeBW狀态使用minRTT界定cycle phase的原因

當需要計時，有minRTT和packet-timed RTT可供使用，而BBR在ProbeBW狀态采用了minRTT而不是packet-timed RTT，原因如下：

• probe同步問題

  感謝neal的解釋：

  For what it’s worth, the motivation for using wall clock time rather than packet-timed round trips for triggering the end of a cycle phase was to avoid entrainment. We originally tried using packet-timed round trips, but noticed that this caused entrainment: flows aligned their phases based on the dynamics of the bottleneck queue; in turn this caused some flows to repeatedly probe for bandwidth at the same time as other flows, causing each flow in the synchronized ensemble to fail to realize that its fair share was higher. We found better bandwidth convergence by avoiding entrainment by explicitly randomizing the initial phase of the flows and then using wall clock time to trigger the progress through the bandwidth probing cycle.

  使用packet-timed RTT的問題在于會發生所謂的Entrainment，這将導緻幾個流同時進入probe階段，之後又同時進行drain，進而破壞BBR在ProbeBW狀态固有的公平收斂性。同步probe會讓BBR造成誤判，事實上并沒有發生擁塞，隻是大家一起probe導緻的暫時假性擁塞。

  和簡諧振動同步一樣，probe同步也是有害的，詳細解釋為什麼多個流會對齊它們的phase start時間不是本文的目的，隻能直覺上感受一下。

  多條流顯然是在同一個buffer中互相作用的系統，它們之間的互動是probe同步的原因：

  

  和蕩秋千時為了讓秋千快速停下來需要随機搖晃一樣，随機化是破解同步的利器。我前段時間嘗試以固定時間執行ProbeBW，也是有probe同步的風險的，解除這個風險有好幾個方案：
  • 随機化每一個cycle phase的順序。
  • 每一個cycle phase的時間在小時間範圍随機化。
  • 小範圍随機化cruise phase的數量。
  以上的随機方案可以疊加實施。

• 高丢包問題

  顯然，packet-timed RTT大于等于minRTT的，使用更久的packet-timed RTT堅持probe可能會造成很高的丢包，比如在已經開始排隊的系統中。下面是一個描述該場景的tcptrace圖示：

  

  凡事要分析兩面性，縱然使用packet-timed round可能會出現probe同步以及高丢包，但它的好處是，packet-timed RTT可以天然識别排隊。比如，通過packet-timed RTT和minRTT的比較，在識别出排隊時，便可以跳過probe階段了，是以此時的probe将會加劇擁塞。

  是以說，ProbeBW狀态完全可以根據實際情況進行觸發式自适應：

  • 觸發式probe：在采集到minRTT或者RTT小到一定程度是馬上進行probe。
  • 周期性probe：在時間段 T T T内，至少保證要probe一次，以防餓死
  • probe和cruise階段使用minRTT周期計數。
  • drain階段使用packet-timed RTT周期計數(見最後一節)。

ProbeBW狀态probe階段BBR如何公平收斂

設一條流的帶寬為 B B B，probe增益為 g g g，理想情況下，在probe之前和其它流完全共享整個帶寬，設為1，帶寬使用率為100%，則其它流的帶寬為 1 − B 1-B 1−B.

當該流probe時，分兩種情況：

• 有空餘帶寬加進來，該流理所當然獲得 g × B g\times B g×B的帶寬。

• 無空餘帶寬，probe導緻了排隊，隊列出口按照buffer中各流包量比例配置設定帶寬。

  無論如何probe之後，該流帶寬在目前總帶寬的占比為：

  g × B g × B + 1 − B \dfrac{g\times B}{g\times B+1-B} g×B+1−Bg×B​

  該流在probe前後的帶寬占比的變化為：

  p ( B ) = g × B g × B + 1 − B B B + 1 − B p(B)=\dfrac{\frac{g\times B}{g\times B+1-B}}{\frac{B}{B+1-B}} p(B)=B+1−BB​g×B+1−Bg×B​​

  如果吧 G × B G\times B G×B看作是在 B B B的基礎上增加了一個增量 α \alpha α，即 g = 1 + α g=1+\alpha g=1+α，則有：

  g × B g × B + 1 − B = B + α B + α + 1 − B \dfrac{g\times B}{g\times B+1-B}=\dfrac{B+\alpha}{B+\alpha+1-B} g×B+1−Bg×B​=B+α+1−BB+α​

  相比于probe之前的帶寬占比，分子分母同時加上一個值，其占比是擴大的，是以 p ( B ) > 1 p(B)>1 p(B)>1，化簡為：

  p ( B ) = g ( g − 1 ) B + 1 p(B)=\dfrac{g}{(g-1)B+1} p(B)=(g−1)B+1g​

  g g g大于1，是以$ p ( B ) p(B) p(B)是一個大于1的減函數，初始帶寬越小獲得的加速比就越大。這趨向于收斂到公平。

ProbeBW狀态的RTT不公平性

設 λ ( t ) \lambda(t) λ(t)為時間 t t t時刻一條BBR流的測量速率，根據Bottleneck通量原理：

λ ( t ) = B D P R T T \lambda(t)=\dfrac{BDP}{RTT} λ(t)=RTTBDP​

記傳播時延 R T p r o p RTprop RTprop為 T T T，排隊時延 D e l a y q u e u i n g Delay_{queuing} Delayqueuing​為 D D D，進而有：

λ ( t ) = B D P T + D \lambda(t)=\dfrac{BDP}{T+D} λ(t)=T+DBDP​

注意 D D D對于排入同一個buffer的所有流而言是一緻的，是以不區分流。

在ProbeBW狀态 λ ( t ) \lambda(t) λ(t)是上一輪測量帶寬 λ ( t − 8 T ) \lambda(t-8T) λ(t−8T)基礎上以增益 g g g進行probe的結果，該過程發送的資料量即BDP：

λ ( t ) = g × T × λ ( t − 8 T ) T + D = λ ( t ) = g × T T + D λ ( t − 8 T ) \lambda(t)=\dfrac{g\times T\times \lambda(t-8T)}{T+D}=\lambda(t)=\dfrac{g\times T}{T+D}\lambda(t-8T) λ(t)=T+Dg×T×λ(t−8T)​=λ(t)=T+Dg×T​λ(t−8T)

其中 g × T T + D \dfrac{g\times T}{T+D} T+Dg×T​為有效增益系數。

可以從測量帶寬 λ ( t ) \lambda(t) λ(t)的有效增益系數 g × T T + D \dfrac{g\times T}{T+D} T+Dg×T​看出BBR的RTT不公平性：

• RTT越大，有效增益系數越大，搶占能力越強。

ProbeBW狀态drain階段如何在minRTT時間将隊列排掉

在drain階段剛開始的時候，根據BBR的probe算法描述，在進入drain的那一刻，端到端的inflight為(at least BBR.RTprop and either inflight has reached 5/4 * estimated_BDP)：

g p r o b e × B l t B W × R T p r o p g_{probe}\times BltBW\times RTprop gprobe​×BltBW×RTprop

假設drain持續的時間為 T d r a i n T_{drain} Tdrain​，則整個drain階段發出的資料包量為：

g d r a i n × B l t B W × T d r a i n g_{drain}\times BltBW\times T_{drain} gdrain​×BltBW×Tdrain​

在整個drain階段，由于已經排隊，帶寬持續保持 B l t B W BltBW BltBW，是以被确認的資料包量為：

B l t B W × T d r a i n BltBW\times T_{drain} BltBW×Tdrain​

根據資料包守恒原則，drain階段發出的資料包和被确認的資料包之差正好等于一個不排隊時的BDP，有下列等式：

g p r o b e × B l t B W × R T p r o p + g d r a i n × B l t B W × T d r a i n − B l t B W × T d r a i n = B D P m i n = B l t B W × R T p r o p g_{probe}\times BltBW\times RTprop + g_{drain}\times BltBW\times T_{drain}-BltBW\times T_{drain}=BDP_{min}=BltBW\times RTprop gprobe​×BltBW×RTprop+gdrain​×BltBW×Tdrain​−BltBW×Tdrain​=BDPmin​=BltBW×RTprop

一步步化簡為：

g p r o b e × R T p r o p + g d r a i n × T d r a i n − T d r a i n = R T p r o p g_{probe}\times RTprop+g_{drain}\times T_{drain}-T_{drain}=RTprop gprobe​×RTprop+gdrain​×Tdrain​−Tdrain​=RTprop

( g p r o b e − 1 ) × R T p r o p = ( 1 − g d r a i n ) × T d r a i n (g_{probe}-1)\times RTprop = (1-g_{drain})\times T_{drain} (gprobe​−1)×RTprop=(1−gdrain​)×Tdrain​

我們希望在最多一個 R T p r o p RTprop RTprop的時間内完成drain，那麼 R T p r o p > T d r a i n RTprop>T_{drain} RTprop>Tdrain​，則有：

g p r o b e − 1 > 1 − g d r a i n g_{probe}-1 > 1-g_{drain} gprobe​−1>1−gdrain​

解上述不等式：

g d r a i n > 2 − g p r o b e g_{drain}>2-g_{probe} gdrain​>2−gprobe​

目前BBR中 g p r o b e = 1.25 g_{probe}=1.25 gprobe​=1.25代入，得到：

g d r a i n > 0.75 g_{drain}>0.75 gdrain​>0.75

理想情況下，當 g d r a i n = 0.75 g_{drain}=0.75 gdrain​=0.75時，BBR可以在一個 R T p r o p RTprop RTprop中完成drain階段的收斂。

這就是BBR算法ProbeBW中probe和drain兩個階段的Gain的關系：

phase 1 of the gain cycle is designed to drain any queue at the bottleneck (the likely outcome of phase 0 if the pipe was full) by using a pacing_gain of 3/4, chosen to be the same distance below 1 that 5/4 is above 1.

https://datatracker.ietf.org/doc/html/draft-cardwell-iccrg-bbr-congestion-control-00#section-4.3.4.1

ProbeBW狀态drain階段的另一種可能(關于drain-to-target)

如上節描述，如果隊列僅是同一個流在probe階段堆積，接下來的drain階段，預期可在一個minRTT之内排空該堆積。如果隊列并非由自己所造，便不能保證在一個minRTT内排空自己的堆積了。

此時需要一個修正，即drain-to-target patch的邏輯：

• 一直堅持到将inflight下降到BDP，否則不離開drain階段。

事實上，如果不使用minRTT而使用packet-timed round來triggering the end of drain cycle phase，便可以保證可以在一個round内drain掉堆積。然而如本文第一小節所描述，使用packet-timed round是有弊端的，是以還是要使用minRTT。

那麼，能否僅針對drain階段使用packet-timed round呢？我想也未嘗不可，隻是如此一來，drain階段的gain就不再是 2 − 1.25 = 0.75 2-1.25=0.75 2−1.25=0.75，而是 1 1.75 = 4 5 \dfrac{1}{1.75}=\dfrac{4}{5} 1.751​=54​。

這是為什麼？按照上節推導方式，隻需要将 T d r a i n T_{drain} Tdrain​換為 T p a c k e t r o u n d T_{packet round} Tpacketround​即可：

g p r o b e × B l t B W × R T p r o p + g d r a i n × B l t B W × T p a c k e t r o u n d − B l t B W × T p a c k e t r o u n d = B D P m i n = B l t B W × R T p r o p g_{probe}\times BltBW\times RTprop + g_{drain}\times BltBW\times T_{packet round}-BltBW\times T_{packet round}=BDP_{min}=BltBW\times RTprop gprobe​×BltBW×RTprop+gdrain​×BltBW×Tpacketround​−BltBW×Tpacketround​=BDPmin​=BltBW×RTprop

而 T p a c k e t r o u n d T_{packetround} Tpacketround​包括 R T p r o p RTprop RTprop和排隊時延，進一步可以将排隊時延替換成

g p r o b e × B l t B W × R T p r o p − B l t B W × R T p r o p B l t B W \dfrac{g_{probe}\times BltBW\times RTprop-BltBW\times RTprop }{BltBW} BltBWgprobe​×BltBW×RTprop−BltBW×RTprop​

代入上面的等式，化簡為：

g p r o b e + g d r a i n × g p r o b e − g p r o b e = 1 g_{probe} + g_{drain}\times g_{probe}-g_{probe}=1 gprobe​+gdrain​×gprobe​−gprobe​=1

最終結果：

g d r a i n = 1 g p r o b e g_{drain}=\dfrac{1}{g_{probe}} gdrain​=gprobe​1​

二者互為倒數。而這個結果也正是BBR在Startup狀态和Drain狀态時其gain的關系。

ProbeBW的cwnd上界

BBR采用pacing rate作為其primary control parameter，而cwnd隻是secondary control parameter，之是以仍然需要一個cwnd作為一個control parameter，很大程度上是為了規定一個發送量的上界。

根據BBR的模型，在理想情況下，BBR是無排隊，不丢包的。但在被動排隊的場景下，BBR無法兌現上面的承諾，為了最大限度降低被動排隊對BBR造成的影響，在被動排隊場景下，一個cwnd的上界是必要的。

假設一個buffer queue長度為 C C C，BltBW為 B B B，隊列中已經被占據的比例為 p p p，那麼留給BBR排隊的空間為 C × ( 1 − p ) C\times (1-p) C×(1−p)。

若想讓BBR獲得最大帶寬，則需要将 C × ( 1 − p ) C\times (1-p) C×(1−p)的空間排滿，而此時采集到的其minRTT則為排入的第一個資料包的RTT，是以我們可以得到：

B W m a x = B × ( 1 − p ) BW_{max}=B\times (1-p) BWmax​=B×(1−p)

R T T m i n = C × p B RTT_{min}=\dfrac{C\times p}{B} RTTmin​=BC×p​ （注意，BBR被動排在後面，是以前面的資料包以 B B B輸出）

是以，我們可以計算得到一個帶有增益系數 g g g的cwnd：

C ( p ) = g × ( 1 − p ) × p × C C(p)=g\times (1-p)\times p\times C C(p)=g×(1−p)×p×C

很明顯，這是一個抛物線，其最大值在 p = 0.5 p=0.5 p=0.5的時候，即：

C ( 0.5 ) = 0.25 × g × C C(0.5)=0.25\times g\times C C(0.5)=0.25×g×C

BBR标準版本選擇了 g = 2 g=2 g=2，那麼cwnd的上界則是 0.5 × C 0.5\times C 0.5×C，也就是說，BBR最多隻能夠占據一半的buffer，而這個比例是比較合理的：

• 在已經堆積了一半的場景下，BBR激進容忍到極限，可以撐到AQM丢包的極限。
• 在尚未堆積到一半的場景下，BBR偏保守，等待緩解。
• 在堆積超過一半的場景下，BBR偏保守，避免了丢包。

無論如何，隻要發生了被動排隊，BBR均不會采取激進措施，以最大限度維持BBR的模型。

如果不選擇2作為cwnd_gain會怎樣？

• cwnd_gain大于2，當隊列已經堆積了一半時，BBR發送量将會超過隊列容量的一半，造成丢包。

• cwnd_gain小于2，當隊列堆積尚未達到一半時，BBR發送量就到達上界，如果被其它流餓死。

  不多不少，2作為cwnd_gain剛剛好。

probe擠占導緻的排隊問題以及解法

設流的帶寬為 B 1 B_1 B1​，probe之後測量其帶寬為 B 2 B_2 B2​

B 2 × ( T m i n + Δ t ) = g × B 1 × T m i n B_2\times (T_{min}+\Delta t)=g\times B_1\times T_{min} B2​×(Tmin​+Δt)=g×B1​×Tmin​

B 2 > B 1 B_2>B_1 B2​>B1​的情況下，真的意味着該流probe到新的帶寬 B 2 − B 1 B_2-B_1 B2​−B1​了嗎？

分兩種情況：

• 如果 Δ t = 0 \Delta t=0 Δt=0，說明真的是probe到了新的空閑帶寬。
• 如果 Δ t > 0 \Delta t>0 Δt>0，說明是擠占了其它流的帶寬。

無論哪種情況，更大的 B 2 B_2 B2​均将進入windowed-max-filter中并在至少10個packet-timed rounds中以 B 2 B_2 B2​作為send pacing rate，同時其它BBR流由于windowed-max-filter會堅持10個packet-timed round，并不會降低send pacing rate。

在 Δ t > 0 \Delta t>0 Δt>0的情況下，Bottleneck将是以而過載，進而造成buffer擁塞。這顯然違背了BBR的初衷。那麼，如何修正這個問題呢？

在判斷新采集的帶寬 B 2 B_2 B2​是否要進入windowed-max-filter的時候，增加一個條件。設 T c u r r T_{curr} Tcurr​為最新采集到的RTT，如果滿足下面的條件，則不将新的更大的帶寬 B 2 B_2 B2​放入windowed-max-filter：

T c u r r − T m i n = Δ t T_{curr}-T_{min}=\Delta t Tcurr​−Tmin​=Δt

由于完全理想情況難遇，在實際操作中，需要在計算時給予一定的寬容，允許一定的偏差。

後記

終于寫完了，公式排版太難搞，不像文字可以一氣呵成，不過總算還是寫完了。

在調研BBR以及看它的源碼的時候，總是可以看到範雅各布森的大名，他總是被列入作者的行列，但我一直不清楚範大師在BBR具體做了哪些工作，是真的做了一些工作還是說隻是為了尊敬，希望知道的朋友告訴我，我一直都對曆史和科技考古非常感興趣。

我了解到的，範雅各布森對bufferbloat是有過很深的研究的，除此之外，範雅各布森1988年的成果更是奠定了後來關于TCP擁塞控制的基調。

另一方面，QUIC方面無論從源碼，IETF draft，還是各類文案，均找不到範雅各布森的名字，即便是QUIC版的CUBIC，BBR也都沒有提他，哈哈，是不是有點不尊師重道了呢 (─‿‿─)

參考：

• BBR開發團隊的分析

  https://github.com/google/bbr/tree/master/Documentation/startup/gain/analysis

• 之前寫過的一些文章

  https://blog.csdn.net/dog250/article/details/80660091

  https://blog.csdn.net/dog250/article/details/80754825

浙江溫州皮鞋濕，下雨進水不會胖。