首页 > WebRTC > WebRTC研究:Trendline滤波器-TrendlineEstimator
2019
11-29

WebRTC研究:Trendline滤波器-TrendlineEstimator

BACK TOP文章索引

前面文章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)。那这个延迟梯度为什么可以判断网络拥塞情况呢?

延迟梯度计算

首先我们通过一张图看下延迟梯度的计算:
WebRTC研究:Trendline滤波器-TrendlineEstimator - 第1张  | 剑痴乎
延迟梯度:
d(i) = t(i) - t(i-1) - (T(i) - T(i-1))

判断依据

网络无拥塞,正常情况下:
WebRTC研究:Trendline滤波器-TrendlineEstimator - 第2张  | 剑痴乎

网络拥塞情况下:
WebRTC研究:Trendline滤波器-TrendlineEstimator - 第3张  | 剑痴乎

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

线性回归

WebRTC用到了线性回归这个数学方法进行延迟梯度趋势预测。通过最小二乘法求得拟合直线斜率,根据斜率判断增长趋势。
WebRTC研究:Trendline滤波器-TrendlineEstimator - 第4张  | 剑痴乎
对于一堆样本点(x,y),拟合直线方程y=bx+a的斜率b按如下公式计算:
WebRTC研究:Trendline滤波器-TrendlineEstimator - 第5张  | 剑痴乎

网络状态

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

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

源码导读

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

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

  • recv_delta_ms:包组接受时间差
  • send_delta_ms:包组发送时间差
  • send_time_ms:包组发送时间
  • arrival_time_ms:包到达时间
  • packet_size:包组大小

内部相关函数调用如下:

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

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

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

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

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

LinearFitSlope函数

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

看下内部代码实现:

Detect函数

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

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

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

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

 
如下图所示,上下两条红色曲线表示动态阈值,蓝色曲线表示调整后的斜率值,阈值随时间动态变化,调整后的斜率值也动态变化,这样网络状态也动态变化。
WebRTC研究:Trendline滤波器-TrendlineEstimator - 第6张  | 剑痴乎
相关实现代码如下:

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

UpdateThreshold函数

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

这个阈值根据如下公式计算:
WebRTC研究:Trendline滤波器-TrendlineEstimator - 第7张  | 剑痴乎
每处理一个新包组信息,就会更新一次阈值,其中∆T表示距离上次阈值更新经历的时间,m(ti)是前面说到的调整后的斜率值modified_trend

kγ(ti)按如下定义:
WebRTC研究:Trendline滤波器-TrendlineEstimator - 第8张  | 剑痴乎
kdku分别决定阈值增加以及减小的速度。
具体实现代码如下:

总结

本文主要介绍了如何根据延迟梯度得到网络状态,判断网络拥塞状况,并结合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.

最后编辑:
作者:Jeff
Avatar
管理员——代码为剑,如痴如醉

One Response to WebRTC研究:Trendline滤波器-TrendlineEstimator

  1. Pingback: WebRTC研究:包组时间差计算-InterArrival | 剑痴乎

留下一个回复

你的email不会被公开。

This site uses Akismet to reduce spam. Learn how your comment data is processed.