WebRTC 拥塞控制 | AIMD 码率控制

2021-10-17 10:35:32

作者：泰一
来源：码神说公众号

导读
指数移动均值、方差、标准差、归一化
AIMD 码率控制概述
- 状态切换
- 控制算法
源码分析
- Update 函数
- ChangeBitrate 函数
- ChangeState 函数
- AdditiveRateIncrease 函数
- GetNearMaxIncreaseRateBps 函数
- MultiplicativeRateIncrease 函数
- UpdateMaxThroughputEstimate 函数
- 再谈 ChangeBitrate 函数
测试用例

导读

上一篇介绍了网络带宽的检测过程以及在该过程中产生的三种信号：overuse、normal、underuse。

本篇将介绍这三种信号如何驱动码率控制器工作，这个过程涉及到：三种码率控制状态（increase、decrease、hold）的切换、增加码率的算法（加性增大与乘性增大）、减少码率的算法（指数回退，即乘性减小）、最大码率方差的计算。

指数移动均值、方差、标准差、归一化

在介绍 WebRTC 码率控制算法之前，先来了解几个与统计学相关的概念。

方差（Variance）
统计中的方差是每个样本值与样本均值之差的平方值的平均数。
标准差（Standard Deviation）
标准差是方差的算术平方根，反映一个数据集的离散程度。
归一化（Normalize）
把数据经过处理后使之限定在一定的范围内。
指数平滑移动均值（Exponential Moving Average）
EMA 是以指数式递减加权的移动平均，它是一种趋向类指标，其原理是一阶滞后滤波法。EMA 可以降低周期的性干扰，在波动频率较高的场景中有很好的效果。

在 WebRTC 拥塞控制 | Trendline 滤波器 [1] 一文中，较为详细的介绍了指数平滑法，可移步阅读。

AIMD 码率控制概述

AIMD 是 TCP 拥塞控制中码率调节的概念。在计算机网络 [2] 一书中，对 AIMD 算法做了如下描述：

在拥塞避免阶段，拥塞窗口是按照线性规律增大的，这常称为加法增大 AI（Additive Increase）。而一旦出现超时或 3 个重复的确认，就要把门限值设置为当前拥塞窗口值的一半，并大大减小拥塞窗口的数值。这常称为乘法减小 MD（Multiplicative Decrease）。二者合在一起就是所谓的 AIMD 算法。

状态切换

GCC 草案 [3] 定义了三种码率控制状态：

The rate control subsystem has 3 states: Increase, Decrease and Hold. "Increase" is the state when no congestion is detected; "Decrease" is the state where congestion is detected, and "Hold" is a state that waits until built-up queues have drained before going to "increase" state.

三种状态在 WebRTC 中表示如下：

enum RateControlState {
  kRcHold, kRcIncrease, kRcDecrease
};

码率控制状态之间的切换，如下图所示：

状态切换

收到 overuse 信号，码率控制器总是进入 decrease 状态。
收到 underuse 信号，码率控制器总是进入 hold 状态。
收到 normal 信号，码率控制器提升当前状态。

当前在 hold 状态，提升到 increase 状态。
当前在 decrease 状态，提升到 hold 状态。

关于码率控制状态切换，有两点个人理解：

收到过载信号，将码率降低，这很好理解，但是收到低载信号，为何进入码率保持状态？

我的理解是，收到 underuse 信号，说明网络上传输的流量很少，网络链路容量完全可以承载当前发送码率，不需要做任何改变，保持该码率即可。

收到正常信号，hold 状态提升到 increase 状态很好理解，但是 decrease 状态为何要提升到 hold 状态？

我的理解是，在网络正常的情况下，原来的码率处于 decrease 状态，说明码率已经降低到适应当前网络状况了，所以转向 hold 状态。

控制算法

WebRTC 借鉴 AIMD 这种码率调节思想，设计了一套自己的算法：

注意，上面的码率调节算法最初用于 Receive-side BWE，在 WebRTC 最新的 Send-side BWE 中复用了该算法。

结合三种码率状态之间的切换与调节算法，下面的图应该不难理解，具体的码率调节过程下文会详细介绍。

码率控制状态机

源码分析

基于 WebRTC M71 版本

码率控制在 AimdRateControl 类中实现，该类的重要的成员函数如下：

class AimdRateControl {
public:
  uint32_t Update(
    const RateControlInput* input,
    int64_t now_ms);
  int GetNearMaxIncreaseRateBps() const;
private:
  void ChangeState(
    const RateControlInput& input,
    int64_t now_ms);
  uint32_t ChangeBitrate(
    uint32_t current_bitrate,
    const RateControlInput& input,
    int64_t now_ms);
  uint32_t MultiplicativeRateIncrease(
    int64_t now_ms,
    int64_t last_ms,
    uint32_t current_bitrate_bps) const;
  uint32_t AdditiveRateIncrease(
    int64_t now_ms,
    int64_t last_ms) const;
  void UpdateMaxThroughputEstimate(
    float estimated_throughput_kbps);
};

Update 函数

该函数为驱动 AimdRateControl 工作的外部接口函数，其内部调用私有成员函数 ChangeBitrate。

ChangeBitrate 函数

该函数为整个码率控制算法的核心实现函数，主要流程包括：

根据输入的带宽检测信号，更新码率控制状态，在 ChangeState 函数中实现。
根据新的码率控制状态和最大码率的标准差，进行相应的码率控制，计算新的码率。
- 如果码率控制状态为 hold，码率保持不变。
- 如果码率控制状态为 increase，根据当前码率是否接近网络链路容量对其进行加性增大或者乘性增大。
- 如果码率控制状态为 decrease，对码率进行乘性减小，并更新当前网络链路容量估计值的方差，即最大码率的方差。
控制新的码率值在一定范围内。

当码率控制算法计算出的新的码率值过大，超过发送端的发送能力，则需要将新的码率值限制到一定区间内，这也避免了发送端码率增长过快。

关于 2 中详细的码率控制过程，在源码分析的最后会继续介绍。

ChangeState 函数

该函数输入带宽检测信号，从而对码率控制状态进行切换。

switch (input.bw_state) {
  case BandwidthUsage::kBwNormal:
    if (rate_control_state_ == kRcHold) {
      rate_control_state_ = kRcIncrease;
    }
    break;
  case BandwidthUsage::kBwOverusing:
    if (rate_control_state_ != kRcDecrease) {
      rate_control_state_ = kRcDecrease;
    }
    break;
  case BandwidthUsage::kBwUnderusing:
    rate_control_state_ = kRcHold;
    break;
}

关于状态切换，有一点 WebRTC 源码并未体现：当收到 normal 信号时，如果当前状态是 decrease，应该提升到 hold 状态。

除此之外，码率控制状态的切换过程与上文描述的一致。

AdditiveRateIncrease 函数

该函数执行加性增大算法，输入当前时间和上次码率被更新的时间，返回增加的码率大小。

returnstatic_cast<uint32_t>(
  (now_ms - last_ms) *
  GetNearMaxIncreaseRateBps() / 1000);

根据源码可知：加性增大的码率大小 = 距上次码率更新所经历的时间 (秒) * 每秒应该增加的码率大小。所以，真正的加性增大算法在 GetNearMaxIncreaseRateBps 函数中实现。

注意，GetNearMaxIncreaseRateBps 函数名告诉我们，在码率接近网络链路容量时，进行加性增大。

GetNearMaxIncreaseRateBps 函数

该函数会计算在当前码率下执行加性增大算法后增加的码率值。

计算当前码率下每帧的大小，假设帧率为 30fps。

double bits_per_frame =
  static_cast<double>(current_bitrate_bps_) / 30.0;

计算每帧的包数，假设每包大小为 1200B。

double packets_per_frame =
  std::ceil(bits_per_frame / (8.0 * 1200.0));

注意，每帧的包数向上取整，至少为 1，也就是说，如果每帧大小小于单个包大小 1200 bytes，也会认为每帧含有一个包。

计算当前码率下每个包实际的大小。

double avg_packet_size_bits =
  bits_per_frame / packets_per_frame;

计算 response_time，其大小为 rtt 加上 100 ms 的发送端 BWE 延迟，rtt 默认值为 200ms。

constint64_t response_time = in_experiment_ ?
    (rtt_ + 100) * 2 : rtt_ + 100;

加性增大的原则应该是：每一个 response_time 增加一个包的大小。

那么，每秒包含（1000 /response_time）个 response_time interval，则每秒应该增加（1000 /response_time）个包的大小，于是，加性增大的码率值就计算出来了。

constexprdouble kMinIncreaseRateBps = 4000;
returnstatic_cast<int>(std::max(
  kMinIncreaseRateBps,
  (avg_packet_size_bits * 1000) / response_time));

有两点需要注意：

加性增大的码率值至少为 4Kbps，比如在低码率场景下，加性增大的码率值可能小于 4Kbps。
GCC 草案规定每一个 response_time interval，码率增加至多半个包的大小，而非 WebRTC 源码中一个包的大小。

MultiplicativeRateIncrease 函数

该函数执行乘性增大算法，输入当前时间和上次码率被更新的时间，返回增加的码率大小。

double alpha = 1.08;
if (last_ms > -1) {
  auto time_since_last_update_ms =
    rtc::SafeMin<int64_t>(now_ms - last_ms, 1000);
  alpha = pow(alpha, time_since_last_update_ms / 1000.0);
}
uint32_t multiplicative_increase_bps =
  std::max(current_bitrate_bps * (alpha - 1.0), 1000.0);

将距上次码率更新所经过的时间作为指数，计算增长系数 alpha。alpha 初值取 1.08，最大值也为 1.08，也就是说，乘性增大的码率值最大不会超过当前码率的 8%。

UpdateMaxThroughputEstimate 函数

该函数输入网络带宽过载状态下的码率估计值 estimated_throughput_kbps，计算网络链路容量的方差。

注意，该函数只有在收到过载信号降低码率时才会被调用，这是因为：一旦检测到过载并准备降低码率时，说明当前网络链路已经达到了最大吞吐量（带宽），此时的码率估计值才能代表网络链路容量，从而作为样本并计算其方差。

可以认为，网络链路容量 link capacity 代表了网络吞吐量 throughput，也即带宽 bandwidth。

也可以认为，过载状态下的码率估计值 estimated_throughput_kbps 即为最大码率，计算网络链路容量的方差就是计算最大码率的方差。

一次指数平滑法计算最大码率的指数移动均值

estimated_throughput_kbps 为接近 link capacity 的最大码率估计值，即样本值。

avg_max_bitrate_kbps_ 为最大码率的估计值 estimated_throughput_kbps 的均值，即样本均值。

constfloat alpha = 0.05f;
avg_max_bitrate_kbps_ =
  (1 - alpha) * avg_max_bitrate_kbps_ +
  alpha *estimated_throughput_kbps;

一次指数平滑法计算最大码率的方差
这里求最大码率的方差并不是进行简单平均，而是也采用了指数移动平均求取方差，并使用最大码率均值对方差进行归一化。

constfloat norm =
  std::max(avg_max_bitrate_kbps_, 1.0f);
var_max_bitrate_kbps_ =
  (1 - alpha) * var_max_bitrate_kbps_ +
  alpha *
  (avg_max_bitrate_kbps_ -
  estimated_throughput_kbps) *
  (avg_max_bitrate_kbps_ -
  estimated_throughput_kbps) / norm;

对于求取最大码率均值与方差时的指数平滑系数，GCC 草案的建议值为 0.95。

将归一化后的方差控制到 [0.4, 2.5] 区间范围之内。

// 0.4 ~= 14 kbit/s at 500 kbit/s
if (var_max_bitrate_kbps_ < 0.4f) {
  var_max_bitrate_kbps_ = 0.4f;
}
// 2.5f ~= 35 kbit/s at 500 kbit/s
if (var_max_bitrate_kbps_ > 2.5f) {
  var_max_bitrate_kbps_ = 2.5f;
}

再谈 ChangeBitrate 函数

在了解了码率控制状态如何切换、加性增大与乘性增大算法以及如何计算最大码率方差之后，我们再来看一下码率增加或者减少的详细过程。

计算最大码率标准差

UpdateMaxThroughputEstimate 函数计算出了最大码率的方差，只需要对其开根号，就可以得到标准差。

constfloat std_max_bit_rate =
  sqrt(var_max_bitrate_kbps_ *
       avg_max_bitrate_kbps_);

注意，因为这个方差使用了最大码率均值进行归一化，所以开根号之前要乘以最大码率均值，还原真正的方差值。

最大码率标准差表征了链路容量 link capacity 的估计值相对于均值的波动程度。

增加码率

关于码率增加是选择加性增大还是乘性增大，GCC 草案规定如下：

The system does a multiplicative increase if the current bandwidth estimate appears to be far from convergence, while it does an additive increase if it appears to be closer to convergence. "Close" is defined as three standard deviations around this average.

如果 rate_control_region_ == kRcNearMax，即当前码率接近 link capacity，此时增长需放慢，选择加性增大。

如果 rate_control_region_ == kRcMaxUnknown，即当前码率远未达到 link capacity，此时可放手增大，选择乘性增大。

rate_control_region_ 初始化为 kRcMaxUnknown，也就是说，WebRTC 码率控制模块以增加码率（乘性增大）的状态启动。

case kRcIncrease:
  if (avg_max_bitrate_kbps_ >= 0 &&
    estimated_throughput_kbps >
      avg_max_bitrate_kbps_ +
      3 * std_max_bit_rate)
  {
      rate_control_region_ = kRcMaxUnknown;
      avg_max_bitrate_kbps_ = -1.0;
  }
  if (rate_control_region_ == kRcNearMax)
  {
    uint32_t additive_increase_bps =
      AdditiveRateIncrease(now_ms,
        time_last_bitrate_change_);

      new_bitrate_bps +=
        additive_increase_bps;
  } else
  {
    uint32_t multiplicative_increase_bps =
      MultiplicativeRateIncrease(now_ms,
        time_last_bitrate_change_,
        new_bitrate_bps);

      new_bitrate_bps +=
        multiplicative_increase_bps;
  }
  time_last_bitrate_change_ = now_ms;
  break;

如果当前网络吞吐量的评估值与最大码率均值的差大于最大码率标准差的 3 倍。认为最大码率均值不可靠，丢弃之前的码率评估数据，复位并重新计算。

同时，认为当前的 link capacity 是未知的，设置 rate_control_region_ 为 kRcMaxUnknown，乘性增大码率以探索 link capacity，即最大码率。

降低码率

根据公式 1，码率的降低以接收端反馈后的码率估计值 estimated_throughput_bps 为基准，而非当前码率，回退系数为 0.85。

如果回退后的码率大于当前发送码率（当 estimated_throughput_bps 出现较大波动时可能会出现这种情况），则以最大码率均值 avg_max_bitrate_kbps_ 为基准进行回退。

总之，码率降低的原则是：降低后的新的码率必须保证小于等于当前的发送码率。

码率降低后将 rate_control_region_ 设置为 kRcNearMax，说明此时码率已经接近 link capacity，之后如果收到 normal 信号需要增大码率，只能选择加性增大。

new_bitrate_bps =
  static_cast<uint32_t>(beta_ *
    estimated_throughput_bps + 0.5);

if (new_bitrate_bps > current_bitrate_bps_)
{
  if (rate_control_region_ != kRcMaxUnknown)
  {
    new_bitrate_bps =
      static_cast<uint32_t>(beta_ *
      avg_max_bitrate_kbps_ * 1000 + 0.5f);
  }
  new_bitrate_bps = std::min(
    new_bitrate_bps,
    current_bitrate_bps_);
}
rate_control_region_ = kRcNearMax;

下面要判断网络是否发生退化：即降低后的码率值是否小于当前码率与回退系数以及网络退化系数的乘积。其中，回退系数依然为 0.85，网络退化系数为 0.9。

如果码率降低的过多，那么这次降低的值 last_decrease_ 将视为无效，不会用于 BWE 周期的计算。

constexprfloat kDegradationFactor = 0.9f;
if (smoothing_experiment_ &&
    new_bitrate_bps <
    kDegradationFactor * beta_ *
    current_bitrate_bps_) {
  last_decrease_ = absl::nullopt;
} else {
  last_decrease_ =
    current_bitrate_bps_ - new_bitrate_bps;
}

接下来，判断本次最大码率评估值（样本值）相对于最大码率均值（样本均值）的离散程度是否在合理范围内。

如果差值小于 3 个标准差，认为最大码率均值不可靠，复位。

if (estimated_throughput_kbps <
    avg_max_bitrate_kbps_ -
    3 * std_max_bit_rate) {
  avg_max_bitrate_kbps_ = -1.0f;
}

接下来，更新最大码率均值与方差，将码率控制状态设置为 hold，直到网络链路缓冲区队列清空。

如果码率降低后，网络依然拥塞，那么会继续触发 overuse 信号降低码率。

UpdateMaxThroughputEstimate(
  estimated_throughput_kbps);
// Stay on hold until the pipes are cleared.
rate_control_state_ = kRcHold;
break;

最后，将新的码率控制到区间 [min_configured_bitratebps, 1.5f * estimated_throughput_bps + 10000] 之内。

最大限制码率是 estimated_throughput_bps 的线性函数，限制码率的原因上文已经做过解释，不再赘述。

测试用例

测试 1
为了更深刻的理解加性增大算法的计算过程，我对 GetNearMaxIncreaseRateBps 函数进行了测试，测试代码很简单：

constexprint kBitrate = 90000;
aimd_rate_control->SetEstimate(kBitrate,
  simulated_clock.TimeInMilliseconds());
aimd_rate_control->GetNearMaxIncreaseRateBps();

设置码率控制器初始码率为 90000bps，计算在该码率下，执行加性增大算法后增大的码率值（每秒）是多少，测试输出如下图所示：

测试输出_1

测试 2
为了进一步理解过载信号被触发后码率降低的流程，进行如下测试：

constexprint kInitialBitrate = 50000000;
aimd_rate_control->SetEstimate(
  kInitialBitrate,
  simulated_clock.TimeInMilliseconds());

constexprint kAckedBitrate =
  40000000 / kFractionAfterOveruse;
RateControlInput input(
  BandwidthUsage::kBwOverusing,
  kAckedBitrate);
aimd_rate_control->Update(&input,
  simulated_clock.TimeInMilliseconds());

设置码率控制器初始码率为 50Mbps，接下来输入过载信号以及发送端的码率估计值 kAckedBitrate（根据接收端反馈的 transport feedback 报文估计码率）。

测试输出如下图所示，可知，带宽过载后的新的码率值为 40 Mbps，在 kAckedBitrate 的基础上回退了 0.85 倍，与上一次的码率相比下降了 10Mbps。

测试输出_2

测试 3
最后，看一下在网络正常的情况下码率乘性增大的过程。

constexprint kAckedBitrate = 10000;
aimd_rate_control->SetEstimate(
  kAckedBitrate,
  simulated_clock.TimeInMilliseconds());

while (simulated_clock.TimeInMilliseconds() -
  kClockInitialTime < 20000) {
  RateControlInput input(
    BandwidthUsage::kBwNormal,
    kAckedBitrate);
  aimd_rate_control->Update(
    &input,
    simulated_clock.TimeInMilliseconds());
  simulated_clock.AdvanceTimeMilliseconds(1000);
}

设置码率控制器初始码率为 10000bps，每隔 1 秒进行一次 Update，每次的输入信号皆为 normal，每次的输入码率估计值均为 10000bps，观察 20 秒内的码率变化，测试输出如下：

测试输出_3

观察测试输出，可知：

在首次计算时，乘性增大系数 alpha 的时间指数为 0，因此 alpha 的值为 1 而非 1.08，理论上增加的码率值为 0，但是 WebRTC 规定了码率乘性增大的最小值 1000bps。
之后，由于我们每隔一秒 Update 一次，因此 alpha 的时间指数为 1，alpha 值为 1.08。从第四次计算开始，每次增加的码率超过了 1000bps。
因为每次输入的码率估计值为 10000 bps，因此可知码率最大值不能超过 1.5 * 10000 + 10000 = 25000bps。因此最终码率值增大到 25Kbps 后保持不变。

至此，WebRTC 的码率控制模块就讲完了，加上前面的三篇，大概脉络如下：

计算包组时间差
trendline 滤波器计算延迟梯度
过载检测
码率控制

那么问题来了，发送端是如何知道发送的报文到达接收端的时间的呢？这可是计算包组时间差必不可少的条件，更是发送端 BWE 的一切之源头。

其实这个源头的秘密就在于接收端会反馈 transport feedback rtcp 报文到发送端，下一篇会介绍这个特殊的 rtcp 报文，感谢阅读。

参考资料

[1]指数平滑法: https://mp.weixin.qq.com/s?__biz=MzU3MTUyNDUzMA==&mid=2247483869&idx=1&sn=3f2d15cafed26ce21bf440f3378749d1&chksm=fcdf9500cba81c1658a561dfc57bb9fb3f5e217cbcdebbc1300dc1b2d750849ef4a96bbf05fc&token=926771124&lang=zh_CN#rd

[2]AIMD 算法: 计算机网络第 7 版

[3]GCC 草案: https://tools.ietf.org/html/draft-ietf-rmcat-gcc-02#section-5.5

「视频云技术」你最值得关注的音视频技术公众号，每周推送来自阿里云一线的实践技术文章，在这里与音视频领域一流工程师交流切磋。

码农公寓

导读

指数移动均值、方差、标准差、归一化

AIMD 码率控制概述

状态切换

控制算法

源码分析

Update 函数

ChangeBitrate 函数

ChangeState 函数

AdditiveRateIncrease 函数

GetNearMaxIncreaseRateBps 函数

MultiplicativeRateIncrease 函数

UpdateMaxThroughputEstimate 函数

再谈 ChangeBitrate 函数

测试用例

参考资料

相关文章