本文是 WebRTC 擁塞控制
第 1 篇
- 導讀
- 延遲梯度與包組
- 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:
1. A sequence of packets which are sent within a burst_time interval constitute a group.
2. 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 版本。
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
函數整體計算流程如下:
- 如果是首個包,存儲包組資訊,傳回 false
- 如果包不是有序發送,丢棄,傳回 false。
- 如果是目前包組的包,更新包組資訊,傳回 false。
- 如果是突發資料,認為是目前包組的包,更新包組資訊,傳回 false。
- 如果是新的包組到來,根據目前包組和上一個包組的資訊計算時間內插補點,傳回 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;
由上面代碼可知,滿足以下條件,認為是突發資料包:
- 延遲梯度 < 0
- 到達時間間隔 <= kBurstDeltaThresholdMs(5ms)
- 與目前包組的首包到達時間的內插補點 < 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;
}
}
由上面代碼可知,滿足以下條件,認為是新的包組:
- 不是首包
- 不是突發資料包
- 新包的發送時間與目前包組的第一個包的發送時間的內插補點 > kTimestampGroupLengthTicks(5ms)
隻有當新的包組到來且在這之前已經有了兩個包組,才會(對這兩個包組)進行時間內插補點的計算。
測試用例
為了能夠更好地掌握包組時間內插補點的計算過程,我對 WebRTC 的
inter_arrival_unittest.cc
測試檔案進行了修改,并加入了一些關鍵日志幫助了解。下圖是其中一個測試函數的輸出:
該測試函數對正常累加的包組、突發資料包、到達時間亂序的包這三種場景進行了測試。
一共測試了 10 個包組:前 3 個包組正常到達,在收到第 3 個包組時,對前面 2 個包組進行時間差計算;在第 4 個包組發送前,使其到達時間減少 1000ms,之後,第 4 個包組檢測為突發資料包,認為是目前包組的包;第 5~7 個包被檢測為到達時間亂序包,并被重置;經過前面的重置,最後 3 個包恢複了正常的計算邏輯。
測試函數的源碼以及完整的測試用例,在我的 github 倉庫 中。
至此,本文結束,喜歡的朋友可以通過更多途徑找到我。
我的個人網站:Linux 程式員
我的微信公衆号:
碼神說。
參考資料
[1] 隊列延遲: https://en.wikipedia.org/wiki/Queuing_delay
[2] 谷歌擁塞控制算法草案: https://tools.ietf.org/html/draft-ietf-rmcat-gcc-02