BBR 的 buffer 動力學觀感

這周很忙，今天還加了一天班，但還是抽空實現了五一在安徽涇縣山區喝著一壺酒寫的 BBR ProbeRTT 的想法，沒多少行代碼，它真就消除了帶寬鋸齒，皮了個鞋👞，昨天我還在群里說了今天再說說 BBR 的，回到家就作圖作文了。

去年夏天，我花了些精力量化 BBR 動力學，并給出一些相圖以及收斂方程的數值解，但數學也只是描述而非解釋，就像牛頓定律只能描述萬有引力卻無法解釋引力的由來(任何理論都無法解釋)一樣。所以這個話題要不斷推敲，常看常新，搞不好就有新思路了。

BBR 動力學核心是收斂，歸為一句話就是 “帶寬越大 Probe 加速比越小”，這句話是收斂的原因，進一步通俗解釋，大的想更大更難，是為邊際收益遞減，小的想更大也難，但邊際收益單調遞減，卻仍高于大的，相對而言其加速比就更大。buffer 動力學解釋，即小流 Probe 的結果比大流的更大，大流就表現出凈損而讓給小流了。

《道德經》里早有論述，“天之道，損有余而補不足”，看來這是天道，容不得解釋。而 “人之道則不然，損不足以奉有余”，則與《新約 · 馬太福音》相呼應了。

我也常常提到 “矩”，它是一個乘積，與一個值不同的是，它體現了兩個維度的膠合，兩個維度的矩針對一個維度的值，其結果就是邊際收益遞減了，因為兩個維度的伸縮比例并不常一致，所謂矩的效應，就比如面積相同而周長不等，或周長相同而面積各異，正如力和力臂，矩不變，但費料不同。

套用解釋 buffer 動力學，BDP 就是擠出帶寬的矩，BBR 靠 1.25 倍增益來體現邊際收益遞減，直到當它繼續再減下去時，對方也要跟著減下去，這時候收斂到公平，方可停止，驚奇的是，這件事確實自然發生。

5 月 2 日晚，我在安徽宣城寫了一篇 BBR ProbeRTT 新改，提出一個新思路，近日測試，是那么回事。我大致說的是，BBR 一定需要借宿于 buffer 中收斂到公平，為守其初衷，卻又要 ProbeRTT，但原生 ProbeRTT 的假設太苛刻，對全局同步過度依賴，這境況在強弱不等的持續統計波動中未必能保持，何不哺其糟而歠其醨，將自己因 Probe 而建立的 queue 吐出即可。

我模仿 Jaffe’s style，用四則混合運算描述 BBR buffer 動力學，基于表達式推出一個結論，基于該結論給出上述 ProbeRTT 描述，即刻取消 BBR 由于 ProbeRTT 導致的邪惡帶寬鋸齒(BBR 終于擺脫了 cwnd 鋸齒，卻為何還要面對 bw 鋸齒)。

設總帶寬為 1，流 1 帶寬為 x，則流 2 帶寬則為 1 - x，以 ProbeBW 之 ProbeUP phase 論，流 1 和流 1 的帶寬增量表示為：

$f_1(x)=\dfrac{\mathrm{g}\cdot x}{\mathrm{g}\cdot x+1-x}-\dfrac{x}{x+1-x}$

$f_2(x)=\dfrac{\mathrm{g}\cdot (1-x)}{\mathrm{g}\cdot (1-x)+x}-\dfrac{(1-x)}{(1-x)+x}$

不必化簡，直接畫圖：
在這里插入圖片描述

最下面灰線是 f1(x) - f2(x)，可清晰看出 x = 0.5 的分水嶺，當 x < 0.5，f1(x) 屬小流帶寬演進，f2(x) 屬大流帶寬演進，小流擠壓大流帶寬，反之亦然。

這也不難直觀理解，以 AIMD 為例，當 x，y 分別為兩流不同的初始 cwnd 時，設 x < y，那么 $\dfrac{x+L}{y+L}$ 當 L 越大，值越趨向 1 收斂到公平，即只要 additive increase 一直持續，總會收斂，BBR 同樣，每次 Probe 都會堆一小丟丟 queue，大流堆的少，小流堆得更多些， $\dfrac{x+L_{bigger}}{y+L_{smaller}}$ 看起來要比 AIMD 更快趨向 1，但 L 都超級小(如圖所示，我還特意縮放了坐標比例)，總體上還是 AIMD 應有的收斂速度。

f1(x)，f2(x) 顯然關于 x = 0.5 對稱，它們之做差結果顯示了 “損有余而補不足” 的過程，該過程強度逐漸收緩(如圖綠藍線之間的間隙)，直至兩者再無差異，它們與 x = 0.5 相交的此點即穩定點，它是不動點。

依照上述 5 月 2 日的 ProbeRTT 方法，釋放自己堆積的 queue，在上圖的意義就是分別求綠線 x 到 0.5 以及藍線 0.5 到 1 - x 的積分，肉眼觀測，面積是相等的，大差不差一個相位。

現在演示一下實際上是不是這樣：

import numpy as np
import matplotlib.pyplot as plt
import randomx0 = 0.2  
y0 = 0.8 
g = 1.25  
bx, by = 0, 0
R = 2
C = 1num_steps = 500
t = np.arange(num_steps)  # 帶寬
x = np.zeros(num_steps)
y = np.zeros(num_steps)
# BDP
Bx = np.zeros(num_steps)
By = np.zeros(num_steps)
# RTwait
r = np.zeros(num_steps)
# 自己堆占的 queue
Ax = np.zeros(num_steps)
Ay = np.zeros(num_steps)
# 自己堆棧 queue 的平均
sAx = np.zeros(num_steps)
sAy = np.zeros(num_steps)x[0] = x0
y[0] = y0
r[0] = 0Bx[0], By[0] = x0, y0
Ax[0], Ay[0], sAx[0], sAy[0] = 0, 0, 0, 0
nx, ny = random.randint(5, 15), random.randint(5, 15)for i in range(1, num_steps):if i > 150:C = 5if i > 350:C = 0.2dec = 0x[i] = C * (g * x[i-1]) / (g * x[i-1] + y[i-1]) tx = C * x[i-1] / (x[i-1] + y[i-1])bx += R * (x[i] - tx)if i % nx == 0: # x 隨意 ProbeRTT，不再依賴同步dec += bxbx = 0      # 退掉自己 Probe 造成的 queue，堆多少退多少nx = random.randint(5, 15)Ax[i] = bxsAx[i] = 0.9 * sAx[i-1] + 0.1 * bx#y[i-1] = C - x[i]   # 忘記 max-filter bwy[i] = C * (g * y[i-1]) / (g * y[i-1] + x[i])  ty = C * y[i-1]/(y[i-1] + x[i])by += R * (y[i] - ty)if i % ny == 0: # y 隨意 ProbeRTT，不再依賴同步dec += byby = 0      # 退掉自己 Probe 造成的 queue，堆多少退多少ny = random.randint(5, 15)Ay[i] = bysAy[i] = 0.9 * sAy[i-1] + 0.1 * by#x[i] = C - y[i]  # 忘記 max-filter bwr[i] = (((x[i] + y[i]) * R) + bx + by- dec) / C - Rif r[i] < 0:r[i] = 0Bx[i] = r[i] * x[i]By[i] = r[i] * y[i]fig, (ax1, ax2, ax3) = plt.subplots(3, 1, figsize=(8, 6))ax1.plot(t, r, label='rtt(t)', color='green')ax1.plot(t, x, label='bw_x(t)', linestyle=':', color='blue')
ax1.plot(t, y, label='bw_y(t)', linestyle=':', color='red')
ax2.plot(t, Bx, label='bdp_x(t)', linestyle=':')
ax2.plot(t, By, label='bdp_y(t)', linestyle=':')
ax3.plot(t, Ax, label='buf_x(t)', linestyle=':')
ax3.plot(t, Ay, label='buf_y(t)', linestyle=':')
ax3.plot(t, sAx, label='avg_buf_x(t)', linestyle='-')
ax3.plot(t, sAy, label='avg_buf_y(t)', linestyle='-')
ax1.set_xlabel('t')
ax1.set_ylabel('v')
ax2.set_xlabel('t')
ax2.set_ylabel('BDP')
ax2.set_xlabel('t')
ax2.set_ylabel('total buffer')
ax1.legend()
ax1.grid(True)
ax2.legend()
ax2.grid(True)
ax3.legend()
ax3.grid(True)
plt.show()

給出幾個結局：
在這里插入圖片描述

觀測到的現象是：

total buffer 寫錯了，應該去掉，因為已經有了圖例；
RTT 總體在一個很小范圍內波動，視 ProbeRTT 平均期望窗口而定，窗口越大，RTT 振幅越大；
bw，BDP，自己堆積 queue 總體都屬于統計公平狀態；
BDP 隨總帶寬 C 而漲跌，但整體非常公平；

這才像個真實的樣子，沒有任何假設和約束，但卻收斂到了公平。

但這里有個 BBR 細節，“為什么要在一個 max-filter bw 窗口內至少進入 Probe phase 一次”，比如 10-round 的 max-filter bw 窗口，要設計 8-round 的 ProbeBW cycle。如果將上述 python 代碼的兩行 “忘記 max-filter bw” 注釋放開，結局如下：
在這里插入圖片描述

這個結果寫出遞推式就能看明白，完全不必分析不動點和相圖。

最后，給出完全由 buffer 動力學驅動而不是照著 “算法” 臨摹的實際效果。還是先給出仿真代碼：

for i in range(1, num_steps):if i > 150:C = 5if i > 350:C = 0.2dec = 0# 根據 buffer 占比求帶寬x[i] = C * (g * x[i-1] * R) / (g * x[i-1] * R + y[i-1] * (r[i-1] + R)) # 如果不 probe 的帶寬tx = C * x[i-1] * (r[i-1] + R) / (x[i-1] * (r[i-1] + R) + y[i-1] * (r[i-1] + R))bx += R * (x[i] - tx)# 隨機而生的 ProbeRTT，不依賴同步if i % nx == 0:dec += bxbx = 0nx = random.randint(5, 15)# 即時 bufferAx[i] = bx# 即時 buffer 移動指數平均sAx[i] = 0.9 * sAx[i-1] + 0.1 * bx# 同 x，略y[i] = C * (g * y[i-1] * R) / (g * y[i-1] * R + x[i] * (r[i-1] + R))  ty = C * y[i-1] * (r[i-1] + R)/(y[i-1] * (r[i-1] + R) + x[i] * (r[i-1] + R))by += R * (y[i] - ty)if i % ny == 0:dec += byby = 0ny = random.randint(5, 15)Ay[i] = bysAy[i] = 0.9 * sAy[i-1] + 0.1 * by# RTwait = total_bdp / C - RTpropr[i] = (((x[i] + y[i]) * R) + bx + by- dec) / C - Rif r[i] < 0:r[i] = 0Bx[i] = r[i] * x[i]By[i] = r[i] * y[i]