實(shí)時(shí)通訊中擁塞控制算法

擁塞控制算法分類

基于丟包(loss rate)的擁塞控制算法
例如TCP中早期的擁塞控制算法Reno，會(huì)帶來較高的時(shí)延
基于雙向時(shí)延(rtt)的擁塞控制算法
TCP中較新的cubic, 還有BBR算法基于瓶頸帶寬和rtt, 考量的是雙向時(shí)延硅则，帶寬利用率不夠高，且對時(shí)延的控制不夠精確翩剪。
基于單向時(shí)延(one way delay)的擁塞控制算法
典型的是webrtc中的GCC算法腕柜，是目前實(shí)時(shí)通訊場景的一個(gè)較優(yōu)選擇膀篮。

實(shí)時(shí)通訊領(lǐng)域的擁塞控制

實(shí)時(shí)通訊的需求不斷增長毯焕，低延時(shí)的擁塞控制就顯得由為重要衍腥。這樣就有一個(gè)組織叫RMCAT專門來負(fù)責(zé)制定用于實(shí)時(shí)通訊的擁塞控制的標(biāo)準(zhǔn)。
目前RMCAT下共有三個(gè)大的擁塞算法：GCC, SCReAM, NADA纳猫。這三個(gè)算法由三個(gè)不同公司開發(fā)婆咸，各有優(yōu)劣。
GCC有兩個(gè)版本的算法：REMB-GCC , TFB-GCC芜辕，原理幾乎是一樣的尚骄。

三大標(biāo)準(zhǔn)算法對比

從學(xué)術(shù)界給出評測數(shù)據(jù)表明： GCC的公平性更好，能較好的對抗丟包鏈路侵续，但收斂的較慢乖仇，較長時(shí)間達(dá)到穩(wěn)定帶寬； SCReAM時(shí)延更小询兴，但帶寬利用較低，吞吐量小一些起趾； NADA的公平性差一些诗舰，收斂較快。

GCC: 基于單向時(shí)延（one way delay)的變化來預(yù)測數(shù)據(jù)包在網(wǎng)絡(luò)隊(duì)列中的排隊(duì)情況, 進(jìn)而調(diào)節(jié)發(fā)送帶寬训裆。原理見下一節(jié)眶根。
SCReAM: 基于單向隊(duì)列時(shí)延(one way queue delay)的變化在預(yù)測數(shù)據(jù)包在網(wǎng)絡(luò)隊(duì)列中的排隊(duì)情況，進(jìn)而調(diào)節(jié)擁塞窗口边琉。算法如下：

scream.png

NADA: 基于單向時(shí)延(one way delay）的變化和丟包時(shí)延補(bǔ)償來預(yù)測數(shù)據(jù)包在網(wǎng)絡(luò)隊(duì)列中的排隊(duì)情況属百，進(jìn)而調(diào)節(jié)發(fā)送帶寬。原理如下：

nada.png

xn(ti) = ?d(ti) （即one way delay) + Dloss (丟包預(yù)計(jì)時(shí)延） · ploss(ti) （丟包率）

REMB-GCC vs TFB-GCC

REMB-GCC : 擁塞判斷基于數(shù)據(jù)包的時(shí)延變化变姨，收端做擁塞估計(jì)族扰，通過REMB報(bào)文反饋給發(fā)端做擁塞調(diào)節(jié)。在webrtc的M55版本之前的版本支持定欧。
TFB-GCC : 擁塞判斷基于數(shù)據(jù)包的時(shí)延變化渔呵，收端通過Transport Feedback反饋收包時(shí)間給發(fā)端，發(fā)端做擁塞估計(jì)和擁塞調(diào)節(jié)砍鸠。在webrtc的M55版本之后支持扩氢。
TFB-GCC 在工程調(diào)試上較REMB-GCC方便，因?yàn)樗兴惴ㄓ?jì)算都在一端爷辱。在效果上录豺，差別不太大朦肘。

TFB-GCC算法的原理

擁塞控制的流程如下：

tcc-flow.png

同REMB-GCC的兩個(gè)主要區(qū)別：

反饋包文件不一樣，這里是Transport feedback,攜帶的收包時(shí)間等信息双饥，而REMB-GCC是REMB攜帶估算帶寬等信息媒抠。
TrendlineFilter取代了卡爾曼濾波。

同REMB-GCC一樣兢哭，基于數(shù)據(jù)包的單向時(shí)延變化

one_way_delay.png

delay(i) = (G(i).recvTime - G(i-1).recvTime) - (G(i).sendTiem - G(i-1).sendTime)

略有不同的是领舰，不是計(jì)算每個(gè)包P(i)的時(shí)延，而對包進(jìn)行分組迟螺，每5s間隔內(nèi)的包為一組冲秽， G(i).sendTime即第i組包的第一個(gè)包的發(fā)送時(shí)間， G(i-1).recvTime即這一組時(shí)間內(nèi)最后收到的那個(gè)包的時(shí)間矩父，以sendTime分組锉桑。這樣做主要為了減少發(fā)端的時(shí)延來來的干擾，發(fā)端pacer時(shí)間分片5ms窍株，可近似認(rèn)為5ms的數(shù)據(jù)是均勻民轴。

可以簡單這么理解：
delay(i) > 0 -- > overuse 網(wǎng)絡(luò)擁塞了；
delay(i) < 0 --> underuse 網(wǎng)絡(luò)變好了球订；
delay(i) == 0 -- > normal 網(wǎng)絡(luò)較平穩(wěn)后裸；

Trendline Filter計(jì)算

將delay做累加和平滑：

smoothDelay.png

smoothingCoef是個(gè)經(jīng)驗(yàn)值，在webrtc trendline_estimator.cc中取0.9冒滩。

另外還有一個(gè)相對接收時(shí)間recvTime = recvTime(i) - firstRecvTime;
接著將recvTime, accumulatedDelay和smoothedDelay保存到一個(gè)固定窗口大小的隊(duì)列HistoryQueue中微驶，

然后按以下公式計(jì)算線性斜率：

slope.png

為了限制slope不讓它跑偏了，
在HistoryQueue中取前80%的包中最小的accumlatedDelay(k), 以及這個(gè)包對應(yīng)的recvTime(k),
在HistoryQueue中取后80%的包中最大的accumlatedDelay(m), 以及這個(gè)包對應(yīng)的recvTime(k)

slopemax.png

slope不能大于slope(max)开睡。

當(dāng)鏈路排列列隊(duì)減少時(shí)因苹，slope的值也會(huì)減少，因此slope值反映了網(wǎng)絡(luò)帶寬變化趨勢篇恒。

trendline.png

slope值即GCC論文中的藍(lán)色線m扶檐。
動(dòng)態(tài)門限值threshold（線色線）的計(jì)算，同REMB-GCC：

threshold.png

當(dāng)slope > threshold時(shí)胁艰， overuse
當(dāng)slope < -threshold時(shí)款筑， underuse
其他情況時(shí)， normal.

有了以上三種網(wǎng)絡(luò)狀態(tài)后腾么，就可以對帶寬進(jìn)行調(diào)節(jié)：

stat_machine_gcc.png

簡單來說就是：如果是Decrease, 在接收帶寬基礎(chǔ)上倍數(shù)下降醋虏，如果是Increase, 在上一時(shí)刻估計(jì)的帶寬基礎(chǔ)上遞增，其他情況則保持不變哮翘。即AIMD算法颈嚼。

AIMD.png

有了時(shí)延估算的帶寬，收端帶寬饭寺，再加上丟包率阻课，就可以綜合評估出當(dāng)前帶寬了：

loss_bitrate.png

TrendlineFilter: goog_cc/trendline_estimator.cc slope計(jì)算 -- UpdateTrendline方法叫挟， threshold計(jì)算： UpdateThreshold
OveruseDetector: goog_cc/trendline_estimator.cc Detect方法
AIMD : remote_bitrate_estimator/aimd_rate_control.cc
Delay base estimator: goog_cc/delay_based_bwe.cc