WebRTC 拥塞控制 | Trendline 滤波器

2022-05-09 10:31:32

导读
指数平滑
- 一次指数平滑法（Single Exponential Smoothing）
- 指数平滑系数（Smoothing Coeff）
最小二乘法求解线性回归
- 线性回归（Linear Regression）
- 最小二乘法（Least Square）
源码分析
- Trendline 滤波器参数
- LinearFitSlope 函数
- Update 函数
测试用例

导读

上一篇介绍了包组时间差的相关概念与计算过程，在 ComputeDeltas 函数中，我们最终得到了包组的发送时间差 send_delta_ms 和到达时间差 arrival_delta_ms。

本篇将介绍 WebRTC 的 Trendline 滤波器如何根据计算出来的发送时间差与到达时间差去评估最终的延迟梯度的趋势值，在此之前，需要了解指数平滑与线性回归的相关概念。

指数平滑

一次指数平滑法（Single Exponential Smoothing）
指数平滑法（Exponential Smoothing）是在移动平均法基础上发展起来的一种时间序列分析预测法，它是通过计算指数平滑值，配合一定的时间序列预测模型对现象的未来进行预测。其原理是任一期的指数平滑值都是本期实际观察值与前一期指数平滑值的加权平均，因此也是一种特殊的加权平均法。一次指数平滑法预测公式如下：

再来看百度百科对指数平滑法 [1] 的一段描述：

简单的全期平均法是对时间数列的过去数据一个不漏地全部加以同等利用；移动平均法则不考虑较远期的数据，并在加权移动平均法中给予近期数据更大的权重；而指数平滑法则兼容了全期平均和移动平均所长，不舍弃过去的数据，但是仅给予逐渐减弱的影响程度，即随着数据的远离，赋予逐渐收敛为零的权数。

为了加深对上面这段话的理解，我们把一次指数平滑公式进行变形：公式 (1) 中，最后的表示如下：

将公式 (2) 代入公式 (1)，整理得：

同理，可以将的表示代入公式 (3)，最后得到的通用公式如下：

观察公式 (4)，可知：

指数平滑系数（Smoothing Coeff）

指数平滑系数的选择的原则如下：

如果时间序列波动不大，比较平稳，则平滑系数应取小一点，以减少修正幅度，使预测模型能包含较长时间序列的信息。
如果时间序列具有迅速且明显的变动倾向，则平滑系数应取大一点，以使预测模型灵敏度高些，以便迅速跟上数据的变化。

在 WebRTC 发送端基于延迟的拥塞控制中，累计延迟梯度的指数平滑系数为 0.9。

最小二乘法求解线性回归

线性回归（Linear Regression）

如果预测的变量是连续的，我们称其为回归。回归分析中，如果只包括一个自变量和一个因变量，且二者的关系可用一条直线近似表示，这种回归分析称为一元线性回归或者简单线性回归。线性回归过程主要解决的就是如何通过样本来获取最佳的拟合线。

最小二乘法（Least Square）

也称最小平方法 [2]，是一种数学优化技术。它通过最小化误差的平方和寻找数据的最佳函数匹配。

简单线性回归最常用的方法便是最小二乘法，其数学推导过程如下：

源码分析

基于 WebRTC M71 版本。

Trendline 滤波器参数

Trendline 滤波器的三个重要参数分别是：窗口大小、平滑系数、延迟梯度趋势的增益。

窗口大小决定收到多少包组之后开始计算延迟梯度趋势；平滑系数用于累计延迟梯度的一次指数平滑计算；对累计延迟梯度平滑值进行最小二乘法线性回归之后求得延迟梯度趋势，会乘以增益并和阈值作比较，以检测带宽使用状态。下面是 WebRTC 中这三个参数的默认值。

constexprsize_t
  kDefaultTrendlineWindowSize = 20;
constexprdouble
  kDefaultTrendlineSmoothingCoeff = 0.9;
constexprdouble
  kDefaultTrendlineThresholdGain = 4.0;

LinearFitSlope 函数

该函数使用最小二乘法求解线性回归，输入 window_size_ 个样本点（arrival_time_ms, smoothed_delay），输出延迟梯度变化趋势的拟合直线斜率 trendline_slope。

absl::optional<double> LinearFitSlope(
  const std::deque<std::pair<double, double>>& points);

求解过程完全参照公式 (7)。

Update 函数

该函数输入包组间到达时间差与发送时间差以及包组的到达时间，并估计延迟梯度的趋势。

class TrendlineEstimator {
public:
  void Update(
    double recv_delta_ms,
    double send_delta_ms,
    int64_t arrival_time_ms);
};

该函数是 Trendline 滤波器的核心实现，包括：

计算延迟梯度
计算累计延迟梯度的一次指数平滑值
最小二乘法线性回归求延迟梯度趋势斜率
检测带宽使用状态，比如是否过载
更新延迟梯度趋势动态阈值

本篇介绍前 3 个实现过程。

计算延迟梯度

constdouble delta_ms =
  recv_delta_ms - send_delta_ms;

上一篇已经介绍过延迟梯度的计算公式：

d(i) = inter-arrival - inter-depature

那么延迟梯度为何能作为网络拥塞的标志呢？

当网络没有拥塞，延迟梯度：t2 - t1- (T2 - T1) = 0，如下图所示。

网络正常

当网络存在拥塞，数据包经过 router 节点时经历排队等待，导致到达时间比原本要晚，延迟梯度：t2 - t1- (T2 - T1) > 0，如下图所示。

网络拥塞

因此，延迟梯度可以作为网络拥塞的指示。把一段时间内的数据包组的延迟梯度累加、平滑、回归，最终得到延迟梯度的趋势，这就是 Trendline 滤波器要做的事情。

累计延迟梯度一次指数平滑

// Exponential backoff filter.
accumulated_delay_ += delta_ms;
smoothed_delay_ = smoothing_coef_ * smoothed_delay_ +
  (1 - smoothing_coef_) * accumulated_delay_;

注意，计算一次指数平滑值的公式为:

实际观测值前面的系数为:

而上述源码的计算公式的实际观测值 accumulated_delay_ 的平滑系数为:

形式不一，但本质不变。

smoothing_coef_ 取 0.9，那么 accumulated_delay_ 前的平滑系数为 0.1，这意味着新的延迟梯度观测值的变化对平滑值的影响较小，减少了修正幅度。

上面提到的指数平滑系数的选择的原则：当时间序列波动不大，比较平稳的时候会选择较小的系数。

最小二乘法线性回归求延迟梯度趋势斜率

累计延迟梯度平滑值 smoothed_delay_ 计算出来之后将作为 y 轴的数据与作为 x 轴数据的到达时间序列存入队列。当样本点的数量达到滤波器的窗口大小，开始使用最小二乘法求解线性回归，LinearFitSlope 函数实现了这个过程。

// Simple linear regression.
// Update trend_ if it is possible to fit a line to the data. The delay
// trend can be seen as an estimate of (send_rate - capacity)/capacity.
delay_hist_.push_back(std::make_pair(
  static_cast<double>(arrival_time_ms - first_arrival_time_ms_),
  smoothed_delay_));
trend = LinearFitSlope(delay_hist_).value_or(trend);

最终得到了线性回归的解：延迟梯度的变化趋势 trend，其实就是很多离散的样本点的拟合直线斜率。这个预测的斜率值 trend 可以表征网络的拥塞程度（网络缓冲区，即路由器数据包排队的消涨情况）：

0 < trend < 1，数据包延迟不断加大，路由器缓冲队列长度持续增加，直到网络缓冲区被填满。
trend == 0，数据包延迟恒定，路由器缓冲区队列长度不变。
trend < 0，数据包延迟不断减少，路由器缓冲区队列长度不断减少，直到队列为空。

测试用例

下面进行简单的测试，将 Trendline 滤波器窗口设置为 20，平滑系数设置为 0.9，增益设置为 1。按照 slope = 0.5 的期望延迟梯度趋势斜率构造了 41 个包组，测试输出如下：

测试输出.png

当样本点到达窗口大小 20 时，开始线性回归求解延迟梯度趋势斜率，x 代表包组到达时间与首个包组到达时间的差值，y 代表延迟梯度平滑值。可以看到，随着样本数量增多，斜率值逼近期望值 0.5。

为了有更直观的认识，我将测试数据导入 Minitab Express，进行一次指数平滑计算，如下图：

一次指数平滑

可以看到，一次指数平滑法进行预测，预测趋势与实际变动趋势一致，但预测值比实际值滞后，这是指数平滑法的一个缺点。一次指数平滑法优点在于它在计算中将所有的观察值考虑在内，对各期按时期的远近赋予不同的权重，使预测值更接近实际观察值。

继续对计算完成的延迟梯度的平滑值进行简单的线性回归，如下图：

简单线性回归

回归公式（Regression Equation）：C3 = − 27.641 + 0.416902C1，求得的拟合直线的斜率为 0.416902，加大样本的数据量，线性回归模型的预测会更加接近 0.5。

至此，延迟梯度趋势的计算过程介绍完毕，这个趋势值要与动态阈值进行比较，以检测网络带宽使用是否过载，下一篇会介绍这个过程，感谢阅读。

参考资料
[1]指数平滑法: https://baike.baidu.com/item/ 指数平滑法

[2]最小二乘法: https://baike.baidu.com/item/ 最小二乘法 / 2522346?fr=aladdin

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

码农公寓

导读