从 TCP Reno 经 BIC 到 CUBIC

重读 TCP拥塞控制算法-从BIC到CUBIC 以及 cubic 的 tcp friendliness 与拐点控制 这两篇文章，感觉还是啰嗦了，今日重新一气呵成这个话题。

reno 线性逼近管道容量 Wmax，相当于一次查询(capacity-seeking)，但长肥管道从 0.5*Wmax 到 Wmax 的线性遍历太慢，期间一旦遭遇丢包，则前功尽弃。

以下的两条 rtt 相差 5 倍的流在同等丢包率下的带宽和 inflt 发展图：

对已排序序列的查询，二分法是普适方法，首选用二分法替换，查询管道容量 Wmax 的速度快得不是一点半点，这就是 bic：

$w_n=w_{n-1}+\frac{W_{max}-w_{n-1}}{2}$

代码很简单：

B, I = 4, 1 # B 理论值取 2，但不够平滑 
for n in range(1, len(times)):...if wx[n-1] < wmax_x and wmax_x - wx[n-1] > I:wx[n] = wx[n-1] + (wmax_x - wx[n-1])/Belif wx[n-1] > wmax_x:wx[n] =  wx[n-1] + (wx[n-1] - wmax_x)/Belse:wx[n] = wx[n-1] + I..

bic 的 cwnd 曲线形状如下：

加入下列 red 模拟：

for n in range(1, len(times)):...if wx[n] + wy[n] > 1.5*C*R:if random.random() < 0.3:wmax_x = wx[n]wx[n] = (1 - beta)*wx[n]if random.random() < 0.3:wmax_y = wy[n]wy[n] = (1 - beta)*wy[n]if wx[n] + wy[n] > 2*C*R:if random.random() < 0.5:wmax_x = wx[n]wx[n] = (1 - beta)*wx[n]if random.random() < 0.5:wmax_y = wy[n]wy[n] = (1 - beta)*wy[n]while wx[n] + wy[n] > 4*C*R:wmax_x = wx[n]wx[n] = (1 - beta)*wx[n]wmax_y = wy[n]wy[n] = (1 - beta)*wy[n]

双流共存效果如下(忽略 z)：

它极大解决了 reno 长流打开 cwnd 慢的问题，文初相同的环境，用 y-bic 和 x-reno 重跑结果如下(忽略 z)：

但由于 bic 步进完全由 ack-selfclock 驱动，同为 bic 的不同流，对较大 rtt 不友好，用以下代码包裹 x 和 y 两条流，给出一个 4 倍的 rtt 关系：

for n in range(1, len(times)):if n % 5:# 流 x 的计算if n % 20:# 流 y 的计算

模拟如下(忽略 z)：

于是抽离 rtt，就是 cubic，cubic 用一条式子里与 rtt 无关的 3 次曲线拟合 bic 折线：

$w(t)=C\cdot (t-\sqrt[3]{\frac{(1-\beta )\cdot W_{max}}{C}}{)}^3+W_{max}$

公式看起来很复杂，实际就是个数学处理技巧：

• 目标：拟合 bic 折线，平滑为曲线；
• 候选项：有 2 阶拐点的奇数次曲线，简单选 3 次；
• 用 bic 的 Wmax 坐标算 3 次曲线系数。

cubic 长下面的样子：

cubic 只与绝对时间有关，不管 rtt 如何，只要 ack 虽迟但到，公平性就毫无问题。重跑 bic 的例子：

for n in range(1, len(times)):...if n % 5 == 0:wx[n] = wmax_x + G*(n - n_x - K_x)**3else:wx[n] = wx[n-1]if n % 10 == 0:wy[n] = wmax_y + G*(n - n_y - K_y)**3else:wy[n] = wy[n-1]...beta = 0.3if wx[n] + wy[n] > 1.5*C*R:if random.random() < 0.3:n_x = nwmax_x = wx[n]tmp = wmax_x*(1 - beta)/GK_x = math.pow(tmp, 1/3)wx[n] = (1 - beta)*wx[n]if random.random() < 0.3:n_y = nwmax_y = wy[n]tmp = wmax_y*(1 - beta)/GK_y = math.pow(tmp, 1/3)wy[n] = (1 - beta)*wy[n]if wx[n] + wy[n] > 2*C*R:if random.random() < 0.5:...

同样 4 倍 rtt 的关系，如下：

长肥管道同样比 reno 效率高：

然而在短瘦管道却不如 reno，理由很简单，cubic 曲线形状唯一由参数 C 确定，短瘦管道中 cubic 曲线片段更加矮胖，不如长肥管道中瘦高，以至于它矮胖到斜率还没有 reno 大：

实际的结果如下：

换句话说，cubic 在短瘦管道对 bic 折线拟合得不好，于是引入 tcp_friendliness，即在短瘦管道中至少保持与 reno 相图的性能，处理方式很简单：

for n in range(1, len(times)):...if n % 1 == 0:wx[n] = wmax_x + G*(n - n_x - K_x)**3tmp = wx[n-1] + Iif tmp > wx[n]:wx[n] = tmpelse:wx[n] = wx[n-1]if n % 1 == 0:wy[n] = wy[n-1] + Ielse:wy[n] = wy[n-1]

效果如下：

差不多就这些东西。至少经理还有皮鞋。

浙江温州皮鞋湿，下雨进水不会胖。