目錄：

• 導讀
• 延遲梯度與包組
• 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 濾波器會對這個值進行最小二乘法線性回歸得到最終的延遲梯度值，並與動態的閾值進行比較，從而進行擁塞控制，下一篇將會介紹這個過程。

Pre-filtering

在計算包組間的時間差值的時候，並不是簡單的將包組兩兩之間的 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.

C++音視頻開發學習資料：點擊領取→音視頻開發（資料文檔+視頻教程+面試題）（FFmpeg+WebRTC+RTMP+RTSP+HLS+RTP）

源碼分析

基於 WebRTC M71 版本。

ComputeDeltas 函數

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。

下面詳細介紹步驟 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();
  return false;
}

• 包在 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();
  }
  return false;
} else {
  num_consecutive_reordered_packets_ = 0;
}

至此，新包組到來時計算包組時間差值的過程就講述完畢了。

關於步驟 2、4、5 中，如何判斷包發送有序？如何判斷突發數據？如何判斷到來的包是否屬於新的包組？下面將依次解答。

PacketInOrder 函數

該函數用來判斷包是否有序發送。根據包的發送時間與當前包組第一個包的發送時間的差值，即時間戳是否增長來判斷是否是亂序包。

// 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 文件中。

另外，需要注意的是：比較的基準時間是當前包組的首包的發送時間，如果一組包的發送時間降序，但都大於首包的發送時間，那麼也認為是有序的，並會用於包組時間差的計算：更新當前包組的到達時間以及最新的發送時間而不是最後一個包的發送時間。

BelongsToBurst 函數

該函數用於判斷是否是突發數據。

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)
  return true;

由上面代碼可知，滿足以下條件，認為是突發數據包：

1. 延遲梯度 < 0
2. 到達時間間隔 <= kBurstDeltaThresholdMs(5ms)
3. 與當前包組的首包到達時間的差值 < kMaxBurstDurationMs(100ms)

突發數據包將被歸為當前的包組。

NewTimestampGroup 函數

該函數用於判斷是否屬於新的包組。

bool InterArrival::NewTimestampGroup(
  int64_t arrival_time_ms,
  uint32_t timestamp) const {
  if (current_timestamp_group_.IsFirstPacket()) {
    return false;
  } else if (BelongsToBurst(arrival_time_ms, timestamp)) {
    return false;
  } 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 個包恢復了正常的計算邏輯。