0%

WebRTC研究:Trendline滤波器-TrendlineEstimator

前面文章WebRTC研究:包组时间差计算-InterArrival讲到了相关包组时间差计算,输出包组发送时间差,到达时间差等参数。本篇文章主要介绍下这些参数在判断网络拥塞情况方面的应用。

到达时间模型

在WebRTC研究:包组时间差计算-InterArrival说到了到达时间模型,主要包含几个包组时间差计算的概念:

  • 到达时间差:t(i) - t(i-1)
  • 发送时间差:T(i) - T(i-1)
  • 延迟变化:d(i) = t(i) - t(i-1) - (T(i) - T(i-1))

这个延迟变化用于评估延迟增长趋势,判断网络拥塞状况。在[1]中,这个延迟变化叫做单向延迟梯度(one way delay gradient)。那这个延迟梯度为什么可以判断网络拥塞情况呢?

延迟梯度计算

首先我们通过一张图看下延迟梯度的计算:
trendline

延迟梯度:
d(i) = t(i) - t(i-1) - (T(i) - T(i-1))

判断依据

网络无拥塞,正常情况下:
trendline

网络拥塞情况下:
trendline

第一张图是没有任何拥塞下的网络传输,延迟梯度:t2 - t1-(T2 - T1) = 0。第二张图是存在拥塞时的网络传输,当包在t2时刻到达时,因为网络发生拥塞,不能一下子处理这么多资源,经过router节点时经历排队等待,导致到达时间比原本要晚,延迟梯度:t2 - t1-(T2 - T1) > 0,表示当前网络正处在拥塞状态。

线性回归

WebRTC用到了线性回归这个数学方法进行延迟梯度趋势预测。通过最小二乘法求得拟合直线斜率,根据斜率判断增长趋势。
trendline

对于一堆样本点(x,y),拟合直线方程y=bx+a的斜率b按如下公式计算:
trendline

网络状态

在WebRTC中,定义了三种网络状态:normaloveruseunderuse,用于表示当前带宽的使用情况,具体含义跟单词本身含义一样。

例如如果是overuse状态,表示带宽使用过载了,从而判断网络发生拥塞,如果是underuse状态,表示当前带宽未充分利用。后面会介绍如何根据延迟梯度增长趋势得到当前的网络状态。

源码导读

相关源码位于src\modules\congestion_controller\goog_cc\trendline_estimator.cc中,主要由TrendlineEstimator类实现。主要接口就一个:UpdateTrendline。传入包组时间差,时间,包组大小等参数,判断当前网络状态。

1
2
3
4
5
void UpdateTrendline(double recv_delta_ms,
double send_delta_ms,
int64_t send_time_ms,
int64_t arrival_time_ms,
size_t packet_size);

说下输入的各个参数的含义:

  • recv_delta_ms:包组接受时间差
  • send_delta_ms:包组发送时间差
  • send_time_ms:包组发送时间
  • arrival_time_ms:包到达时间
  • packet_size:包组大小
    内部相关函数调用如下:
    1
    2
    3
    4
    5
    6
    7
    TrendlineEstimator::UpdateTrendline

    LinearFitSlope

    TrendlineEstimator::Detect

    TrendlineEstimator::UpdateThreshold

下面结合代码说下UpdateTrendline函数内部计算过程。
1)计算延迟变化累积值:

1
2
3
4
5
6
7
8
// 延迟变化:接收时间 - 发送时间
const double delta_ms = recv_delta_ms - send_delta_ms;
++num_of_deltas_;
num_of_deltas_ = std::min(num_of_deltas_, kDeltaCounterMax);
if (first_arrival_time_ms_ == -1)
first_arrival_time_ms_ = arrival_time_ms;
// 累加延迟变化
accumulated_delay_ += delta_ms;

2)根据1)中的延迟累积值计算得到平滑延迟:

1
2
smoothed_delay_ = smoothing_coef_ * smoothed_delay_ +
(1 - smoothing_coef_) * accumulated_delay_;

3)将从第一个包发送到当前包组到达的经历时间,平滑延迟值存到双端队列delay_hist_中:

1
2
3
delay_hist_.push_back(std::make_pair(
static_cast<double>(arrival_time_ms - first_arrival_time_ms_),
smoothed_delay_));

4)当队列delay_hist_大小等于设定的窗口大小时,开始进行延迟变化趋势计算,得到直线斜率:

1
2
3
4
5
6
if (delay_hist_.size() == window_size_) {
// 0 < trend < 1 -> 延迟梯度增加
// trend == 0 -> 延迟梯度不变
// trend < 0 -> 延迟梯度减小
trend = LinearFitSlope(delay_hist_).value_or(trend);
}

5)通过计算计算得到的延迟变化趋势直线斜率以及发送时间差,到达时间判断网络状态:

1
Detect(trend, send_delta_ms, arrival_time_ms);

LinearFitSlope函数

使用最小二乘法求解线性回归,得到延迟变化增长趋势的拟合直线斜率。

看下内部代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
absl::optional<double> LinearFitSlope(
const std::deque<std::pair<double, double>>& points) {
RTC_DCHECK(points.size() >= 2);
// 所有节点(x,y),x,y值分别求和
double sum_x = 0;
double sum_y = 0;
for (const auto& point : points) {
sum_x += point.first;
sum_y += point.second;
}
// 求平均值
double x_avg = sum_x / points.size();
double y_avg = sum_y / points.size();
// 根据公式:斜率 k = sum (x_i-x_avg)(y_i-y_avg) / sum (x_i-x_avg)^2
double numerator = 0;
double denominator = 0;
for (const auto& point : points) {
numerator += (point.first - x_avg) * (point.second - y_avg);
denominator += (point.first - x_avg) * (point.first - x_avg);
}
if (denominator == 0)
return absl::nullopt;
return numerator / denominator;
}

Detect函数

该函数主要根据延迟变化增长趋势计算当前网络状态,在WebRTC接收端基于延迟的带宽预测代码中,这部分属于过载检测器的内容,代码位于src\modules\remote_bitrate_estimator\overuse_detector.cc中,跟在卡尔曼滤波后面,我们不做讨论,我们讨论的全部是最新代码,全部在发送端进行带宽预测。

在Detect函数内部,会根据前面计算得到的斜率得到一个调整后的斜率值:modified_trend

1
2
const double modified_trend =
std::min(num_of_deltas_, kMinNumDeltas) * trend * threshold_gain_;

然后与一个动态阈值threshold_作对比,从而得到网络状态

  • modified_trend > threshold_,表示overuse状态
  • modified_trend < -threshold_,表示underuse状态
  • -threshold_ <= modified_trend <= threshold_,表示normal状态

如下图所示,上下两条红色曲线表示动态阈值,蓝色曲线表示调整后的斜率值,阈值随时间动态变化,调整后的斜率值也动态变化,这样网络状态也动态变化。

trendline

相关实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
if (modified_trend > threshold_) {
if (time_over_using_ == -1) {
time_over_using_ = ts_delta / 2;
} else {
time_over_using_ += ts_delta;
}
overuse_counter_++;
if (time_over_using_ > overusing_time_threshold_ && overuse_counter_ > 1) {
if (trend >= prev_trend_) {
time_over_using_ = 0;
overuse_counter_ = 0;
hypothesis_ = BandwidthUsage::kBwOverusing;
}
}
} else if (modified_trend < -threshold_) {
time_over_using_ = -1;
overuse_counter_ = 0;
hypothesis_ = BandwidthUsage::kBwUnderusing;
} else {
time_over_using_ = -1;
overuse_counter_ = 0;
hypothesis_ = BandwidthUsage::kBwNormal;
}

这个阈值threshold_是动态调整的,代码实现在UpdateThreshold函数中。

UpdateThreshold函数

阈值自适应调整为了改变算法对延迟梯度的敏感度。根据[1]主要有以下两方面原因:
1)延迟梯度是变化的,有时很大,有时很小,如果阈值是固定的,对于延迟梯度来说可能太多或者太小,这样就会出现不够敏感,无法检测到网络拥塞,或者过于敏感,导致一直检测为网络拥塞;
2)固定的阈值会导致与TCP(采用基于丢包的拥塞控制)的竞争中被饿死。

这个阈值根据如下公式计算:
trendline

每处理一个新包组信息,就会更新一次阈值,其中∆T表示距离上次阈值更新经历的时间,m(ti)是前面说到的调整后的斜率值modified_trend

kγ(ti)按如下定义:
trendline

kdku分别决定阈值增加以及减小的速度。
具体实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
void TrendlineEstimator::UpdateThreshold(double modified_trend,
int64_t now_ms) {
// kγ(ti)值:kd,ku
const double k = fabs(modified_trend) < threshold_ ? k_down_ : k_up_;
const int64_t kMaxTimeDeltaMs = 100;
// 距离上一次阈值更新经过的时间∆T
int64_t time_delta_ms = std::min(now_ms - last_update_ms_, kMaxTimeDeltaMs);
threshold_ += k * (fabs(modified_trend) - threshold_) * time_delta_ms;
threshold_ = rtc::SafeClamp(threshold_, 6.f, 600.f);
last_update_ms_ = now_ms;
}

总结

本文主要介绍了如何根据延迟梯度得到网络状态,判断网络拥塞状况,并结合WebRTC相关源码进行分析。当我们得到当前网络拥塞状况后,就要对发送码率进行调节,以适应当前网络。后续文章我们将研究如何根据网络状态进行相应码率调整。

参考

[1] Analysis and Design of the Google Congestion Control for Web Real-time Communication (WebRTC).
[2] A Google Congestion Control Algorithm for Real-Time Communication draft-ietf-rmcat-gcc-02.https://tools.ietf.org/html/draft-ietf-rmcat-gcc-02.