TCP拥塞控制之Hybla

Published at 2021-10-08 | Last Update 2021-10-08

Hybla是为了改善大RTT的连接的传输性能所设计出的拥塞控制算法。

经典拥塞控制算法与RTT的关系

经典的拥塞控制算法包含慢启动(Slow Start)和拥塞避免(Congestion Avoidance)两个阶段。两个阶段更新拥塞窗口时采用不同的规则：

$$W_{i+1} = \begin{cases} W_i + 1& \text{SS}\\\\ W_i + \frac{1}{W_i}& \text{CA} \end{cases}$$

上式中$W_i$表示收到第$i$个ACK后的拥塞窗口大小。如果将该公式转换到时间尺度上的话，可以看出：在SS阶段，拥塞窗口呈指数增长，而在CA阶段，拥塞窗口呈线性增长。

$$W(t) = \begin{cases} 2^{ \frac{t}{RTT}}& {0 \leq t \leq t_\gamma }\\\\ \frac{t-t_\gamma}{RTT} + \gamma & t \geq t_\gamma \end{cases}$$

上式中其中$W(t)$表示在时刻t的拥塞窗口大小，$t_\gamma$表达到达慢启动阈值$\gamma$的时间，$t_\gamma = RTT\log_2\gamma$。可以看出，$RTT$越大，拥塞窗口增加地越慢，到达慢启动阈值的时间也越长。

有了 $W(t)$ ,我们可以计算出报文的瞬时传输速率

$$B(t) = \frac{W(t)}{RTT}$$

对其进行定积分，就可以得到在这个过程中的数据传输总量：

$$T_d(t) = \int_0^t B(\tau)d\tau = \begin{cases} \frac{2^{ \frac{t}{RTT}}-1}{\ln2}& {0 \leq t \leq t_\gamma }\\\\ \frac{\gamma-1}{\ln2} +\frac{(t-t_\gamma)^2}{2*RTT^2} + \frac{\gamma*(t-t_\gamma)}{RTT} & t \geq t_\gamma \end{cases}$$

可以看出$T_d(t)$与$RTT$呈负相关关系，也就是$RTT$越大，拥塞控制时传输的总数据量越小。

Hybla拥塞控制算法

Hybla拥塞控制算法的目标就是为了解决连接的传输延时很大时，传输性能太低的问题。举个栗子，假设一条高延时(high latency)连接与低延时(low latency)连接竞争网络容量，当出现拥塞丢包时，由上面的公式，低延时连接能比高延时连接更快地恢复拥塞窗口$W$，最终抢占更多的网络传输资源。

Hybla定义一个了往返时间为$RTT0$的参考链路(reference link)，用p表示真实链路与参考链路的往返时间之比：

$$\rho = \frac{RTT}{RTT_0}$$

从数学角度，Hybla的终极目标是使得$T_d(t)$的表达式中不包含$RTT$，这要求其瞬时传输速率$B(t)$也不包含$RTT$，这要求$W(t)$能抵消掉分母的$RTT$，因此，Hybla将时域上拥塞窗口变化定义为

$$W^H(t) = \begin{cases} \rho2^{\rho{\frac{t}{RTT}}} = \rho2^{\frac{t}{RTT_0}} & {0 \leq t \leq t_\gamma }\\\\ \rho[ \rho\frac{t-t_\gamma}{RTT} + \gamma] = \rho[ \frac{t-t_\gamma}{RTT_0} + \gamma] & t \geq t_\gamma \end{cases}$$

其中上标$H$表示Hybla.这样一来，瞬时传输速率

$$B^H(t) = \frac{W^H(t)}{RTT_0} = \begin{cases} 2^ { \frac{1}{RTT_0}} & {0 \leq t \leq t_\gamma }\\\\ \frac{1}{RTT_0}[\frac{t-t_\gamma}{RTT_0} + \gamma] & t \geq t_\gamma \end{cases}$$

它与$RTT$就无关了，进而传输的总报文数量也就与$RTT$无关了

$$T^H_d(t) = \int_0^t B^H(\tau)d\tau = \begin{cases} \frac{2^{ \frac{t}{RTT_0}}-1}{\ln2}& {0 \leq t \leq t_\gamma }\\\\ \frac{\gamma-1}{\ln2} +\frac{(t-t_\gamma)^2}{2*RTT_0^2} + \frac{\gamma*(t-t_\gamma)}{RTT_0} & t \geq t_\gamma \end{cases}$$

反过来，为了得到这样的$W^H(t)$, 我们需要修改拥塞窗口的更新规则

$$W^H_{i+1} = \begin{cases} W^H_i +2^{\rho}-1& \text{SS}\\\\ W^H_i + \frac{\rho^2}{W^H_i}& \text{CA} \end{cases}$$

也就是说，每当发送端收到按序到达的不重复的ACK时，在SS阶段，需要将拥塞窗口增大$2^{\rho}-1$个MSS，在CA阶段，增大$\frac{\rho^2}{W^H_i}$个MSS。

REF

TCP synchronisation effect in TCP New Reno and TCP Hybla TCP Hybla: a TCP enhancement for heterogeneous networks