实时通讯中拥塞控制算法

拥塞控制算法分类

基于丢包(loss rate)的拥塞控制算法
例如TCP中早期的拥塞控制算法Reno，会带来较高的时延
基于双向时延(rtt)的拥塞控制算法
TCP中较新的cubic, 还有BBR算法基于瓶颈带宽和rtt, 考量的是双向时延，带宽利用率不够高，且对时延的控制不够精确。
基于单向时延(one way delay)的拥塞控制算法
典型的是webrtc中的GCC算法，是目前实时通讯场景的一个较优选择。

实时通讯领域的拥塞控制

实时通讯的需求不断增长，低延时的拥塞控制就显得由为重要。这样就有一个组织叫RMCAT专门来负责制定用于实时通讯的拥塞控制的标准。
目前RMCAT下共有三个大的拥塞算法：GCC, SCReAM, NADA。这三个算法由三个不同公司开发，各有优劣。
GCC有两个版本的算法：REMB-GCC , TFB-GCC，原理几乎是一样的。

三大标准算法对比

从学术界给出评测数据表明： GCC的公平性更好，能较好的对抗丢包链路，但收敛的较慢，较长时间达到稳定带宽； SCReAM时延更小，但带宽利用较低，吞吐量小一些； NADA的公平性差一些，收敛较快。

GCC: 基于单向时延（one way delay)的变化来预测数据包在网络队列中的排队情况, 进而调节发送带宽。原理见下一节。
SCReAM: 基于单向队列时延(one way queue delay)的变化在预测数据包在网络队列中的排队情况，进而调节拥塞窗口。算法如下：

scream.png

NADA: 基于单向时延(one way delay）的变化和丢包时延补偿来预测数据包在网络队列中的排队情况，进而调节发送带宽。原理如下：

nada.png

xn(ti) = ˜d(ti) （即one way delay) + Dloss (丢包预计时延） · ploss(ti) （丢包率）

REMB-GCC vs TFB-GCC

REMB-GCC : 拥塞判断基于数据包的时延变化，收端做拥塞估计，通过REMB报文反馈给发端做拥塞调节。在webrtc的M55版本之前的版本支持。
TFB-GCC : 拥塞判断基于数据包的时延变化，收端通过Transport Feedback反馈收包时间给发端，发端做拥塞估计和拥塞调节。在webrtc的M55版本之后支持。
TFB-GCC 在工程调试上较REMB-GCC方便，因为所有算法计算都在一端。在效果上，差别不太大。

TFB-GCC算法的原理

拥塞控制的流程如下：

tcc-flow.png

同REMB-GCC的两个主要区别：

反馈包文件不一样，这里是Transport feedback,携带的收包时间等信息，而REMB-GCC是REMB携带估算带宽等信息。
TrendlineFilter取代了卡尔曼滤波。

同REMB-GCC一样，基于数据包的单向时延变化

one_way_delay.png

delay(i) = (G(i).recvTime - G(i-1).recvTime) - (G(i).sendTiem - G(i-1).sendTime)

略有不同的是，不是计算每个包P(i)的时延，而对包进行分组，每5s间隔内的包为一组， G(i).sendTime即第i组包的第一个包的发送时间， G(i-1).recvTime即这一组时间内最后收到的那个包的时间，以sendTime分组。这样做主要为了减少发端的时延来来的干扰，发端pacer时间分片5ms，可近似认为5ms的数据是均匀。

可以简单这么理解：
delay(i) > 0 -- > overuse 网络拥塞了；
delay(i) < 0 --> underuse 网络变好了；
delay(i) == 0 -- > normal 网络较平稳；

Trendline Filter计算

将delay做累加和平滑：

smoothDelay.png

smoothingCoef是个经验值，在webrtc trendline_estimator.cc中取0.9。

另外还有一个相对接收时间recvTime = recvTime(i) - firstRecvTime;
接着将recvTime, accumulatedDelay和smoothedDelay保存到一个固定窗口大小的队列HistoryQueue中，

然后按以下公式计算线性斜率：

slope.png

为了限制slope不让它跑偏了，
在HistoryQueue中取前80%的包中最小的accumlatedDelay(k), 以及这个包对应的recvTime(k),
在HistoryQueue中取后80%的包中最大的accumlatedDelay(m), 以及这个包对应的recvTime(k)

slopemax.png

slope不能大于slope(max)。

当链路排列列队减少时，slope的值也会减少，因此slope值反映了网络带宽变化趋势。

trendline.png

slope值即GCC论文中的蓝色线m。
动态门限值threshold（线色线）的计算，同REMB-GCC：

threshold.png

当slope > threshold时， overuse
当slope < -threshold时， underuse
其他情况时， normal.

有了以上三种网络状态后，就可以对带宽进行调节：

stat_machine_gcc.png

简单来说就是：如果是Decrease, 在接收带宽基础上倍数下降，如果是Increase, 在上一时刻估计的带宽基础上递增，其他情况则保持不变。即AIMD算法。

AIMD.png

有了时延估算的带宽，收端带宽，再加上丢包率，就可以综合评估出当前带宽了：

loss_bitrate.png

TrendlineFilter: goog_cc/trendline_estimator.cc slope计算 -- UpdateTrendline方法， threshold计算： UpdateThreshold
OveruseDetector: goog_cc/trendline_estimator.cc Detect方法
AIMD : remote_bitrate_estimator/aimd_rate_control.cc
Delay base estimator: goog_cc/delay_based_bwe.cc