​WebRTC 拥塞控制 | 计算包组时间差 - InterArrival导读延迟梯度与包组Pre-filtering源码分析ComputeDeltas 函数PacketInOrder 函数BelongsToBurst 函数NewTimestampGroup 函数测试用例

作者：泰一

来源：

码神说公众号

• 导读
• 延迟梯度与包组
• Pre-filtering
• 源码分析
  • ComputeDeltas 函数
  • PacketInOrder 函数
  • BelongsToBurst 函数
  • NewTimestampGroup 函数
• 测试用例

GCC（Google Congestion Control）包含两种拥塞控制算法：一种是基于丢包的，一种是基于延迟的。GCC 最后综合这两种算法得到一个目标码率，基于延迟的拥塞控制算法相较于基于丢包的拥塞控制算法更为复杂。本篇是 WebRTC 拥塞控制算法讲解第一篇，主要介绍包组和延迟梯度等一些基本理论，并深入源码介绍包组间的时间差值的计算过程。

延迟梯度描述了从发送端到目的地的包所经历的端到端的延迟变化趋势。GCC 算法正是使用延迟梯度来推断网络拥塞，以动态的限制发送速率。在基于接收端的拥塞控制算法中，使用卡尔曼滤波器计算延迟梯度，而在基于发送端的拥塞控制算法中，则使用

Trendline

滤波器计算延迟梯度。下面是维基百科对于延迟 [1]（或称队列延迟、排队延迟）的描述：

这个术语最常用于路由器。当数据包到达路由器时，必须对它们进行处理和传输。路由器一次只能处理一个包。

如果数据包到达的速度比路由器处理它们的速度快（例如在突发数据传输中），路由器就会把它们放入队列（也称为网络缓冲区），直到路由器可以开始传输它们。

延迟也会因分组的不同而不同，因此在测量和评估排队延迟时通常会生成平均值和统计数据。

计算延迟梯度需要了解包组的概念，在 WebRTC 中，延迟不是一个个包来计算的，而是通过将包分组，然后计算这些包组之间的延迟，这样做可以减少计算次数，同时减少误差。包组根据包的发送时间的差值来划分。判断新包组的方法是：如果当前包的发送时间与当前包组的第一个包的发送时间的差值大于

5ms

，那么认为这个包属于新的包组。为什么是 5ms 呢？GCC 草案 [2] 里的一段话回答了这个问题：

The Pacer sends a group of packets to the network every burst_time interval. RECOMMENDED value for burst_time is 5 ms.

接下来，再引出两个概念：包组间的发送时间差

inter-departure

与到达时间差

inter-arrival

。

单向延迟梯度测量

如上图所示，

video frame i-1

与

video frame i

代表相邻的两个包组，

T(i)

代表包组 i 最后一个包的发送时间，

t(i)

代表包组的最后一个包的到达时间，那么有：

inter-depature = T(i) - T(i-1)
inter-arrival = t(i) - t(i-1)
inter-group delay variation =
  d(i) = inter-arrival - inter-depature           

inter-group delay variation

是两个包组之间的延迟变化，显然，如果这个值很大，那么网络很可能发生了拥塞。WebRTC Trendline 滤波器会对这个值进行最小二乘法线性回归得到最终的延迟梯度值，并与动态的阈值进行比较，从而进行拥塞控制，下一篇将会介绍这个过程。

在计算包组间的时间差值的时候，并不是简单的将包组两两之间的 inter-arrival delta time 和 inter-depature delta time 计算出来就了事。这个过程还需要对包进行过滤，比如对突发数据的处理、对包的发送时间乱序的处理、对包的到达时间乱序或者跳变的处理，这些处理过程称为预过滤。

注意，GCC 草案对于预过滤的定义是：旨在处理因为网络信道中断等非网络拥塞原因被排队滞留在网络缓冲区的数据包在网络恢复后以突发的方式进行发送的场景，也就是说，预过滤的目的是处理突发的数据包。GCC 草案的详细描述如下，其中，对于突发数据包的判断在下文会提到。

The pre-filtering aims at handling delay transients caused by channel outages.

During an outage, packets being queued in network buffers, for reasons unrelated to congestion, are delivered in a burst when the outage ends.

The pre-filtering merges together groups of packets that arrive in a burst. Packets are merged in the same group if one of these two conditions holds:

A sequence of packets which are sent within a burst_time interval constitute a group.

A Packet which has an inter-arrival time less than burst_time and an inter-group delay variation d(i) less than 0 is considered being part of the current group of packets.

基于 WebRTC M71 版本。

WebRTC 的

InterArrival

类实现了包组的时间差值计算，其对外接口为

ComputeDeltas

。输入每个包的发送时间、到达时间、系统时间、包大小，输出包组的发送时间间隔、到达时间间隔、包组大小差值，供

Trendline

滤波器计算延迟梯度。整个时间差值计算的子过程包括：包的有序性判断、新包组的判断、突发数据的判断。这些函数的声明如下所示：

class InterArrival {
 public:
  bool ComputeDeltas(
    uint32_t timestamp,
    int64_t arrival_time_ms,
    int64_t system_time_ms,
    size_t packet_size,
    uint32_t* timestamp_delta,
    int64_t* arrival_time_delta_ms,
    int* packet_size_delta);
 private:
  bool PacketInOrder(
    uint32_t timestamp);
  bool NewTimestampGroup(
    int64_t arrival_time_ms,
    uint32_t timestamp) const;
  bool BelongsToBurst(
    int64_t arrival_time_ms,
    uint32_t timestamp) const;
};           

ComputeDeltas

函数整体计算流程如下：

1. 如果是首个包，存储包组信息，返回 false
2. 如果包不是有序发送，丢弃，返回 false。
3. 如果是当前包组的包，更新包组信息，返回 false。
4. 如果是突发数据，认为是当前包组的包，更新包组信息，返回 false。
5. 如果是新的包组到来，根据当前包组和上一个包组的信息计算时间差值，返回 true。
6. 下面详细介绍步骤 5 的计算过程：当到来的数据包属于新的包组时，开始计算之前的两个包组的发送时间差与到达时间差。

注意，发送时间差和到达时间差都是根据包组的最后一个包的发送时间和到达时间进行计算，核心代码如下：

*timestamp_delta =
  current_timestamp_group_.timestamp -
  prev_timestamp_group_.timestamp;
*arrival_time_delta_ms =
  current_timestamp_group_.complete_time_ms -
  prev_timestamp_group_.complete_time_ms;
之后，要对计算出来的到达时间间隔进行异常处理，我称之为预过滤。           

• 到达时间与系统时钟的偏差是否存在不成比例的跳变？正常情况下，二者基本一致。若偏差 > kArrivalTimeOffsetThresholdMs (3000ms)，重置。

int64_t system_time_delta_ms =
  current_timestamp_group_.last_system_time_ms -
  prev_timestamp_group_.last_system_time_ms;
if (*arrival_time_delta_ms - system_time_delta_ms >=
    kArrivalTimeOffsetThresholdMs) {
  Reset();
  returnfalse;
}           

• 包在 socket 接收到 BWE 这段路径中是否被重新排序？如果 inter-arrival time delta <0，说明包组在收到本地到达时间戳后被重新排序（可能是乱序到达的包被重新排序），连续超过 kReorderedResetThreshold (3) 次，重置。

if (*arrival_time_delta_ms < 0) {
  ++num_consecutive_reordered_packets_;
  if (num_consecutive_reordered_packets_ >=
    kReorderedResetThreshold) {
    Reset();
  }
  returnfalse;
} else {
  num_consecutive_reordered_packets_ = 0;
}           

至此，新包组到来时计算包组时间差值的过程就讲述完毕了。

关于步骤 2、4、5 中，如何判断包发送有序？如何判断突发数据？如何判断到来的包是否属于新的包组？下面将依次解答。

该函数用来判断包是否有序发送。根据包的发送时间与当前包组第一个包的发送时间的差值，即时间戳是否增长来判断是否是乱序包。

// Assume that a diff which is
// bigger than half the timestamp
// interval (32 bits) must be due to
// reordering.
uint32_t timestamp_diff = timestamp -
  current_timestamp_group_.first_timestamp;
return timestamp_diff < 0x80000000;           

解释一下差值为什么要和 0x80000000 进行比较：时间戳变量的类型都是

uin32_t

，而无符号数小减大会得到一个特别大的数字，这个数字比 0x80000000 大得多。当包的发送时间戳降序，timestamp_diff < 0x80000000 自然不成立，函数返回 false。这里涉及到 WebRTC 中判断最新的包序号和时间戳的算法，实现在

`

module_common_types_public.h` 文件中。

另外，需要注意的是：比较的基准时间是当前包组的首包的发送时间，如果一组包的发送时间降序，但都大于首包的发送时间，那么也认为是有序的，并会用于包组时间差的计算：更新当前包组的到达时间以及最新的发送时间而不是最后一个包的发送时间。

该函数用于判断是否是突发数据。

int propagation_delta_ms =
  arrival_time_delta_ms -
  ts_delta_ms;
if (propagation_delta_ms < 0 &&
    arrival_time_delta_ms <=
      kBurstDeltaThresholdMs &&
    arrival_time_ms -
      current_timestamp_group_.first_arrival_ms <
      kMaxBurstDurationMs)
  returntrue;           

由上面代码可知，满足以下条件，认为是突发数据包：

1. 延迟梯度 < 0
2. 到达时间间隔 <= kBurstDeltaThresholdMs (5ms)
3. 与当前包组的首包到达时间的差值 <kMaxBurstDurationMs (100ms)
4. 突发数据包将被归为当前的包组。

该函数用于判断是否属于新的包组。

bool InterArrival::NewTimestampGroup(
  int64_t arrival_time_ms,
  uint32_t timestamp) const {
  if (current_timestamp_group_.IsFirstPacket()) {
    returnfalse;
  } elseif (BelongsToBurst(arrival_time_ms, timestamp)) {
    returnfalse;
  } else {
    uint32_t timestamp_diff = timestamp -
      current_timestamp_group_.first_timestamp;
    return timestamp_diff >
      kTimestampGroupLengthTicks;
  }
}           

由上面代码可知，满足以下条件，认为是新的包组：

1. 不是首包
2. 不是突发数据包
3. 新包的发送时间与当前包组的第一个包的发送时间的差值 > kTimestampGroupLengthTicks (5ms)

只有当新的包组到来且在这之前已经有了两个包组，才会（对这两个包组）进行时间差值的计算。

为了能够更好地掌握包组时间差值的计算过程，我对 WebRTC 的

inter_arrival_unittest.cc

测试文件进行了修改，并加入了一些关键日志帮助理解。下图是其中一个测试函数的输出：

测试输出

该测试函数对正常累加、突发数据、到达时间乱序这三种收包场景进行了测试。

一共测试了 10 个包组：前 3 个包组正常到达，在收到第 3 个包组时，对前面 2 个包组进行时间差计算；在第 4 个包组发送前，使其到达时间减少 1000ms，之后，第 4 个包组检测为突发数据包，认为是当前包组的包；第 5~7 个包被检测为到达时间乱序包，并被重置；经过前面的重置，最后 3 个包恢复了正常的计算逻辑。

测试函数的源码以及完整的测试用例，在我的 github 仓库中。

源码地址：

https://github.com/yujitai/WebRTC-Research

您也可以访问我的知乎或者个人网站，找到这篇文章直接跳转到源码地址。

下一篇，将介绍 WebRTC 的 Trendline 滤波器。本文至此结束，感谢收看。

参考资料

[1]队列延迟:

https://en.wikipedia.org/wiki/Queuing_delay

[2]谷歌拥塞控制算法草案:

https://tools.ietf.org/html/draft-ietf-rmcat-gcc-02

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