【转载】GCC 拥塞控制算法

原文：《GCC 拥塞控制算法》

谷歌使用GCC (Google Congestion Control ) 在 WebRTC中的拥塞控制算法，包含2个部分，一个是基于丢包的用拥塞控制，一个是基于延迟的拥塞控制。
最终基于丢包的码率估计值和基于延迟的码率估计值做比较，使用最小的码率估计值作为最终发送码率。

早期实现中2部分分别在发送端和接收端实现，接收端实现延迟梯度算法计算出估计带宽，反馈给发送端，发送端再根据2个算法结果确定最终发送码率。最近的WebRTC中的GCC都在发送端来实现，所以需要接收端在RTCP中反馈包达到时间用来计算延迟。

基于丢包的带宽估计

思想是基于丢包多少来判断网络拥塞程度，丢包少提高发送码率，丢包多降低码率。

接收端通过在RTCP协议中的fraction lost字段反馈给发送端丢包率， WebRTC通过以下公式估算发送码率，式中 $A_s(t_k)$ 即为 $t_k$ 时刻的带宽估计值，$f_l(t_k)$即为 $t_k$ 时刻的丢包率：

$A_s(t_k)=\left\{ \begin{aligned} &A_s(t_{k-1})(1-0.5f_l(t_k))&\quad&f_l(t_k)>0.1\\ &1.05(A_s(t_{k-1}))& &f_l(t_k)<0.02\\ &A_s(t_{k-1})& &otherwise \end{aligned} \right.$

• $f_l > 10\%$: 有拥塞，根据丢包率降低带宽
• $f_l < 2\%$ : 网络良好， As + 5% 提高带宽来探测真实可用带宽
• $2\%< f_l < 10\%$: 正常，保持当前码率不变，避免因波动丢包等误判导致降低码率

基于延迟梯度的带宽估计

接收端在RTCP中增加transport-cc-feedback字段反馈所有媒体包到达的时间，发送端根据接受延迟和发送间隔计算出延迟梯度，从而估计带宽。

步骤有3个：

• 到达时间滤波器

• 过载检测器

• 速率控制器

到达滤波器根据包的到达时延和发送间隔，计算延迟变化，用卡尔曼滤波器平滑处理消除网络噪音。 延迟变化作为过载检测器的输入，判断出当前网络状态underuse/overuse/normal。 速率控制器根据网络状态和带宽公式计算出带宽。

到达时间滤波器

用两个包到达时间间隔减去发送时间间隔，得到一个延迟的变化，公式如下：

$d_m(t_i)=(t_i-t_{i-1})-(T_i-T_{i-1})$

理想情况下，每个包的到达时间间隔和发送间隔是一样的，所以延迟梯度为0。如果某一个包因为拥塞导致排队，那么延迟梯度就不为0。为了计算精确，计算策略如下：

• 由于测量粒度很小，为了避免网络噪音的误差，使用卡尔曼滤波来平滑延迟梯度的结果
• 实现中是按照数据组来计算整体延迟梯度，不是按单个包计算。发送时间间隔小于5ms位一个组。

过载检测器

将延迟梯度和某个阈值比较，高于阈值则为拥塞，低于阈值则为良好，阈值是动态调整的。

$m(t_i)$表示计算出的延迟梯度

$\gamma(t_i)$表示判断阈值：

• $m(t_i)>\gamma(t_i)$：过载状态
• $m(t_i)<-\gamma(t_i)$：欠载状态
• $|m(t_i)|<\gamma(t_i)$：正常状态

$\gamma(t_i)=\gamma(t_{i-1})+\Delta T\cdot k_{\gamma}(t_i)\left(|m(t_i)|-\gamma(t_{i-1})\right)$

上面为阈值自适应算法，当梯度减小时，阈值会以更慢的速率减小。梯度增加时，阈值会以更慢的速率增加。阈值的减小速度要小于增加速度，因为最终目的还是要探测更多可用的网络带宽。

速率控制器

根据过载探测器输出的信号，驱动速率控制状态机，估算出当前网络速率。

• 当收到overuse，进入decrease状态
• 当收到normal，进入increase状态
• 当收到underuse， 进入hold状态

这个状态机输出的是带宽估计值。

• 当前处于降低带宽值状态，发现带宽低载或者正常，就不再下降，如果依然过载，继续降
• 当前处于平衡状态，发现带宽正常，则尝试增加带宽估计值，寻求达到低载状态，争夺多一点的带宽资源
• 当前处于增加带宽值状态，发现带宽正常，继续增加，发现过载，降低带宽估计值，发现低载，目的达到了，保持当前状态

$A_r(t_i)= \left\{ \begin{aligned} &\eta A_r(t_{i-1})&\quad&\sigma=increase\\ &\alpha R_r(t_i)&&\sigma=decrease\\ &A_r(t_{i-1})&&\sigma=hold \end{aligned} \right.$

其中$\eta=1.05$，$\alpha=0.85$。 当increase时，以上一次估计码率乘1.05作为当前码率。 当decrease时以当前估算的接受端码率 乘0.85作为当前码率，hold状态不变。

最终基于丢包的码率估计值和基于延迟的码率估计值做比较，使用最小的码率估计值作为最终发送码率。