劉明昊
(廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,廣州 510006)
DCCP 作為一種適用于實(shí)時(shí)多媒體流的傳輸協(xié)議,擁有UDP 不可靠傳輸特性和TCP的擁塞控制機(jī)制的特點(diǎn),它作為一種通用的底層協(xié)議,避免了在應(yīng)用層上進(jìn)行擁塞控制算法設(shè)計(jì)與實(shí)現(xiàn).圍繞DCCP的研究包括了提高多媒體流傳輸?shù)膶?shí)時(shí)性,優(yōu)化傳輸速率穩(wěn)定性等方面.關(guān)鍵的優(yōu)化點(diǎn)圍繞DCCP中的AIMD 機(jī)制展開,文獻(xiàn)[1]基于卡爾曼濾波對(duì)CCID2 算法[2]進(jìn)行改進(jìn),但這種算法的復(fù)雜度可能給網(wǎng)絡(luò)資源帶來過多的消耗.文獻(xiàn)[3]考慮了誤碼丟包,使用信道繁忙比來檢測(cè)網(wǎng)絡(luò)擁塞的方法對(duì)CCID2 進(jìn)行優(yōu)化,適用于特殊的Ad hoc 網(wǎng)絡(luò),但是這種優(yōu)化并沒有改變算法AIMD的本質(zhì),無法使算法在獲得高吞吐量的同時(shí)保持低延遲.由于丟包作為這類算法的唯一輸入信號(hào),算法的正常運(yùn)行對(duì)鏈路的丟包率有一定的要求,在丟包率較高的長(zhǎng)肥管道環(huán)境下,其發(fā)送窗口會(huì)收斂到很小的值[4].隨著網(wǎng)絡(luò)中間設(shè)備的隊(duì)列深度擴(kuò)增,基于丟包的擁塞控制算法已經(jīng)不再適合如今的網(wǎng)絡(luò)環(huán)境,這類算法的擁塞避免階段會(huì)逐漸加大發(fā)送窗口直至填滿瓶頸隊(duì)列,正是這種機(jī)制本身導(dǎo)致了鏈路擁塞,造成了網(wǎng)絡(luò)延時(shí)的波動(dòng).在鏈路瓶頸處保持最大帶寬和最小延時(shí)的狀態(tài)是擁塞控制的目標(biāo),但這個(gè)狀態(tài)曾被證明不可能由分布式算法收斂[5].最近谷歌提出一種基于延時(shí)帶寬積的算法BBR (Bottleneck Bandwidth and RTT)[6],使用了交替測(cè)試鏈路的最大帶寬與最小的RTT的方法,通過估計(jì)鏈路BDP的思路解決了這個(gè)問題.BBR算法致力于收斂到最佳的擁塞控制點(diǎn),因此適合DCCP這種對(duì)于延時(shí)和帶寬敏感的流媒體傳輸協(xié)議,本文在DCCP中引入BBR 算法,考慮到DCCP與TCP 傳輸模型的差異,對(duì)鏈路瓶頸帶寬的計(jì)算方法進(jìn)行適配,為了增加算法抵抗丟包的能力,此外,本文在BBR的基礎(chǔ)上加入動(dòng)態(tài)測(cè)量丟包率的機(jī)制,優(yōu)化BBR在固定增益系數(shù)下存在的失速問題.經(jīng)過仿真實(shí)驗(yàn)驗(yàn)證,改進(jìn)后的算法可以在高吞吐量的狀態(tài)下保持低延時(shí),提高了在高丟包率的網(wǎng)絡(luò)環(huán)境下連接的吞吐量.
CCID2是一種類TCP的擁塞控制算法,并不保證數(shù)據(jù)可靠性,它使用AIMD 機(jī)制計(jì)算擁塞窗口限制發(fā)送速率以適應(yīng)不同的網(wǎng)絡(luò)環(huán)境.CCID2 應(yīng)用在DCCP上,其擁塞窗口的單位與TCP 不同,在TCP 上單位為字節(jié),而在DCCP 上單位為數(shù)據(jù)報(bào)數(shù)量,傳輸?shù)膯挝粸閿?shù)據(jù)包.CCID2 使用類似TCP-SACK 方法來實(shí)現(xiàn)擁塞控制機(jī)制,然而,作為一種Loss-Base的擁塞控制算法,它存在以下缺點(diǎn):
1)帶寬利用率低,CCID2 本質(zhì)上屬于丟包事件驅(qū)動(dòng)的擁塞控制算法,當(dāng)鏈路的丟包率上升至1%以上的時(shí),算法基本上無法正常工作.
2)緩沖區(qū)膨脹問題(bufferbloat)[7,8],CCID2 算法在擁塞避免階段會(huì)線性探測(cè)鏈路最大帶寬,逐步增加其發(fā)包速率直至隊(duì)列滿載,如圖1的(1)階段.隨后由于隊(duì)列滿導(dǎo)致的丟包事件會(huì)反饋回發(fā)送端,發(fā)送端降低一半的發(fā)送窗口,希望排空隊(duì)列的數(shù)據(jù)包,如圖1的(2)階段.由于目前網(wǎng)絡(luò)中間設(shè)備的隊(duì)列大小都已經(jīng)大幅提高,這種擁塞控制模型已經(jīng)很難適應(yīng)現(xiàn)在的網(wǎng)絡(luò)環(huán)境,減半窗口的做法不一定可以排空隊(duì)列的數(shù)據(jù)包,實(shí)際上并沒有完全緩解網(wǎng)絡(luò)的擁塞壓力.算法在減窗后馬上又開始進(jìn)行(1)階段,導(dǎo)致了鏈路上一直處于高負(fù)載的狀態(tài),不僅造成了鏈路RTT 增加而且限制了基于延時(shí)的算法的使用[9],如VEGAS[10]和FAST[11].實(shí)際上,當(dāng)網(wǎng)絡(luò)中間設(shè)備當(dāng)隊(duì)列開始積累數(shù)據(jù)包當(dāng)時(shí)候,網(wǎng)絡(luò)當(dāng)擁塞就已經(jīng)發(fā)生,由于丟包作為該擁塞控制的唯一反饋信號(hào),這種模型無法獲取除了丟包外的任何信息,對(duì)擁塞狀態(tài)的判斷存在延后的情況.為了解決以上問題,常用的做法是在中間設(shè)備上引入主動(dòng)隊(duì)列管理AQM[12],使用簡(jiǎn)單的RED[13]算法,根據(jù)路由緩沖隊(duì)列的負(fù)載程度進(jìn)行隨機(jī)丟包,作為給予連接降窗的信號(hào),文獻(xiàn)[14]中指出這種做法在中間設(shè)備引入了AQM 配置復(fù)雜度,增加了維護(hù)成本.總體上,緩沖區(qū)膨脹并不是隊(duì)列本身的問題,而是由終端擁塞控制算法導(dǎo)致的,在終端進(jìn)行優(yōu)化是首要的選擇.
圖1 Loss-Base 擁塞控制算法事件循環(huán)
BBR 算法與基于丟包的擁塞控制算法不同,在BBR 算法的模型中,定義了鏈路的最大負(fù)載為鏈路的時(shí)延RTT與鏈路帶寬的乘積(Bandwidth Delay Product,BDP),如果發(fā)送端往網(wǎng)絡(luò)注入數(shù)據(jù)包的速度超過了BDP,中間設(shè)備也無法轉(zhuǎn)發(fā)更多的數(shù)據(jù)包,后續(xù)加入數(shù)據(jù)包會(huì)開始排隊(duì)導(dǎo)致鏈路延時(shí)開始增加.在BBR中鏈路的RTT 由(1)式計(jì)算:
其中,RTProp的值為鏈路延遲,由鏈路物理長(zhǎng)度決定,而 ηt值為ACK 延時(shí)機(jī)制,數(shù)據(jù)包協(xié)議棧處理所消耗的時(shí)間,兩者之和為算法的測(cè)量值,RTProp′的下限為鏈路物理時(shí)延.對(duì)于帶寬的計(jì)算,BBR 采用了Delivery-Rate的最大值作為瓶頸帶寬BTLBW,該值的上限為鏈路的物理帶寬,通過兩者乘積可以估計(jì)出鏈路的BDP,從而控制發(fā)送的速率,避免對(duì)中間設(shè)備造成排隊(duì)的壓力.
BBR 算法模型如圖2所示.
圖2 BBR 算法事件循環(huán)
算法在(1)階段會(huì)探測(cè)鏈路的最大帶寬,該階段鏈路會(huì)出現(xiàn)排隊(duì)的情況,隨后在(2)階段按同樣的比例排空發(fā)送過多的數(shù)據(jù)包,隨后進(jìn)入穩(wěn)定的(3)階段,PROPBW會(huì)周期性探測(cè)鏈路的帶寬.在(3-1)的探測(cè)階段內(nèi),算法會(huì)少量增加發(fā)送數(shù)量以探測(cè)鏈路空閑帶寬,隨后在(3-2)階段會(huì)按相應(yīng)的比例降低發(fā)送數(shù)量,BBR 避免了Loss-Base 算法一直填滿緩沖隊(duì)列的做法,因此可以同時(shí)保持高帶寬利用率和較低的延遲.實(shí)際上,鏈路最低延時(shí)與最大帶寬無法同時(shí)測(cè)量,要測(cè)量帶寬必須往鏈路發(fā)送過量的數(shù)據(jù)以計(jì)算獲得最大的實(shí)際帶寬,此時(shí)由于大量數(shù)據(jù)包排隊(duì),必然會(huì)導(dǎo)致延時(shí)的增加.另一方面,要測(cè)量鏈路延時(shí),必須保證連接本身沒有對(duì)中間設(shè)備進(jìn)行排隊(duì),這時(shí)需要減少數(shù)據(jù)的發(fā)送量.BBR 使用交替測(cè)試RTT與鏈路帶寬的做法解決了上述問題.盡管如此,BBR 仍然存在以下的缺陷:
1)BBR 算法在STARTUP 過程中,為了適應(yīng)不同鏈路的帶寬情況,使用二分搜索的方法探測(cè)鏈路的BDP,具體計(jì)算過程如下(下面使用G代替PACING_GAIN):
① 定義STARTUP 過程的發(fā)送速率SendingRate為RTT 時(shí)間的函數(shù)(其中α為常系數(shù)):
② 為得到PACING_GAIN,令當(dāng)前時(shí)間為t?2,對(duì)于[t?2,t?1]區(qū)間有:
③ 由于PACING_GAIN與當(dāng)前SendingRate的積定義了下一個(gè)周期的SendingRate,從而有:
④ 對(duì)RTT 歸一化處理后,計(jì)算出增益系數(shù)的值:
使用該系數(shù)可以使探測(cè)算法在l og2BDP個(gè)RTT 內(nèi)收斂到瓶頸帶寬BTLBW,但會(huì)對(duì)瓶頸鏈路緩沖區(qū)造成過多壓力[15],考慮到實(shí)時(shí)應(yīng)用容易受鏈路帶寬變化和緩沖區(qū)膨脹問題的影響,因此可以適當(dāng)降低STARTUP的PACING_GAIN.
2)文獻(xiàn)[16]指出,BBR 算法在丟包率過高的環(huán)境下并不能一直保持有效的吞吐量,丟包率主要由PACING_GAIN的正系數(shù)保證,在丟包率波動(dòng)很大的環(huán)境下,若網(wǎng)絡(luò)的丟包率超過固定的增益參數(shù)可以調(diào)整的范圍,會(huì)導(dǎo)致發(fā)送速率逐步收斂到低值.
DCCP-BBR 算法引入了帶寬,丟包率和動(dòng)態(tài)增益系數(shù)計(jì)算的模型.
對(duì)于ACK的計(jì)算,沿用原有的ACK-Ratio 機(jī)制,默認(rèn)值為2,此外,算法使用兩個(gè)事件更新的帶寬信息:
1)onSend()事件
該事件發(fā)生在每一個(gè)數(shù)據(jù)包進(jìn)行發(fā)送的時(shí)刻,需要記錄數(shù)據(jù)包的元信息用于后續(xù)的帶寬估計(jì):
① 記錄發(fā)送的時(shí)間:
② 記錄發(fā)送時(shí)刻的送達(dá)數(shù)據(jù)量delivered_size值:
③ 記錄發(fā)送數(shù)據(jù)包的大小:
2)onAck()事件:
該事件在每收到一個(gè)ACK 時(shí)觸發(fā),需要計(jì)算帶寬與延時(shí)的測(cè)量值,計(jì)算偽代碼如圖3所示.
圖3 onAck 事件偽代碼示意圖
具體的計(jì)算流程如下:
Myth will continue to evolve in the process of word of mouth. In this paper, the interaction between the narrator and the audience is analyzed, and the influence and significance of the narrator and the audience on the myth transmission are discussed.
① 累計(jì)當(dāng)前數(shù)據(jù)包的大小至delivered_size中,該變量記錄連接收到ACK 確認(rèn)的總量.
② 計(jì)算數(shù)據(jù)包發(fā)送到接受完畢時(shí)候所傳輸?shù)臄?shù)據(jù)量delivered.
③ 計(jì)算數(shù)據(jù)包送達(dá)的時(shí)間RTT,對(duì)于接收到多個(gè)ACK的Vector,取ACK 包發(fā)送時(shí)間的最小送達(dá)所完成的時(shí)間RTT.
④ 計(jì)算實(shí)時(shí)帶寬的估計(jì)值bw.
至此,結(jié)合bw值與PACING_GAIN增益系數(shù)的乘積即可導(dǎo)出發(fā)送窗口的值.
連接的丟包率可以在發(fā)送端也可以在接收端計(jì)算.考慮延遲ACK的影響,在發(fā)送計(jì)算時(shí)如果出現(xiàn)接收端ACK 丟失的問題,會(huì)導(dǎo)致計(jì)算的Loss-Rate偏大.為了更準(zhǔn)確地估計(jì)鏈路的丟包率,本實(shí)現(xiàn)選擇在接收端進(jìn)行丟包率計(jì)算,然后反饋在ACK 報(bào)文中.計(jì)算流程如下:
1)協(xié)議保證每一個(gè)數(shù)據(jù)報(bào)序號(hào)總是單調(diào)遞增的.
2)對(duì)于每一個(gè)接收到的數(shù)據(jù)包,判斷數(shù)據(jù)包是否在10 s有效窗口內(nèi),記錄在窗口時(shí)間內(nèi)接收到的數(shù)據(jù)總量W_ALL,丟包率在全局窗口內(nèi)計(jì)算.
3)若出現(xiàn)亂序到達(dá)的情況,按照規(guī)則2)對(duì)丟包率進(jìn)行補(bǔ)償.在每一個(gè)窗口內(nèi),記錄實(shí)際收包總量P_NUMS.最終的丟包率由式(6)計(jì)算:
BBR 算法在絕大多數(shù)時(shí)間內(nèi)處于ProbeBW 狀態(tài),其主要工作為探測(cè)鏈路是否有未利用的帶寬資源,算法引入了使用了8個(gè)階段的Gain Cycle 狀態(tài),分別為1.25,0.75,1,1,1,1,1,1.增益系數(shù)在上述數(shù)組中循環(huán)取值,算法在每一個(gè)階段持續(xù)時(shí)間約為RTprop.BBR首先使用1.25 系數(shù)增加發(fā)包數(shù)量,如果實(shí)際反饋計(jì)算的帶寬增加,意味著BBR 可以占據(jù)鏈路空余的帶寬.但由于1.25 增益階段可能導(dǎo)致的鏈路瓶頸隊(duì)列排隊(duì),算法設(shè)置了0.75 增益階段用于排空瓶頸隊(duì)列.隨后,算法的平穩(wěn)階段采用1 作為增益參數(shù),按照反饋帶寬進(jìn)行發(fā)包,以此保證連接的公平性.BBR 增益系數(shù)輪轉(zhuǎn)機(jī)制的參數(shù)確定主要源于以下幾個(gè)方面的考慮:
1)平穩(wěn)階段的長(zhǎng)度決定了BBR 探測(cè)帶寬的間隔,短的間隔提升了探測(cè)過程的搶占速度,長(zhǎng)的間隔用于保證公平性,兩者并不能同時(shí)兼顧.
2)較大的增益系數(shù)可以增加算法競(jìng)爭(zhēng)性,在鏈路有空閑資源的時(shí)候可以更快收斂到新的BDP,但也會(huì)對(duì)鏈路延遲產(chǎn)生較大的波動(dòng).
3)較小的增益系數(shù)一定程度上減少了競(jìng)爭(zhēng)性,同時(shí)也意味著每一個(gè)ProbeBW階段的收益會(huì)降低,收斂到新BDP需要更長(zhǎng)的時(shí)間.
如果增益系數(shù)過小,正增益的效果會(huì)完全被丟包副作用抵消,從而導(dǎo)致發(fā)送速率持續(xù)下降.由于BBR算法增益系數(shù)是固定的,1.25 增益系數(shù)只能保證在20%丟包率以下工作,DCCP-BBR 采用動(dòng)態(tài)計(jì)算增益系數(shù)的方法.引入丟包率(Loss-Rate)參數(shù),使用丟包率導(dǎo)出實(shí)時(shí)的增益系數(shù),對(duì)于每一個(gè)反饋的Loss-Rate,發(fā)送端在每一個(gè)新的ProbeBW周期,需要調(diào)整PACING_GAIN系數(shù).具體調(diào)整公式如下:
對(duì)于估算的BTLBW值,其增益系數(shù)需要滿足式(7)(下面使用BW代替BTLBW):
上式保證正增益后的值大于當(dāng)前的瓶頸帶寬,否則最大BW的估計(jì)值會(huì)不斷地出現(xiàn)負(fù)反饋的情況,引入丟包率后,需要保證:
考慮到PACING_GAIN過大會(huì)對(duì)鏈路造成壓力,取1.5為上限值,最終的系數(shù)計(jì)算如下(其中LR為丟包率):
算法使用了Hashmap 跟蹤發(fā)送窗口數(shù)據(jù)包狀態(tài),對(duì)于發(fā)送方,RTT與BW的計(jì)算需要獲取對(duì)應(yīng)數(shù)據(jù)包的發(fā)送的時(shí)間packet_send_time,發(fā)送時(shí)刻的已送達(dá)數(shù)據(jù)量delivered_size與數(shù)據(jù)包的大小packet_size,三者可共享一個(gè)哈希表,每一條記錄需要約20 字節(jié),計(jì)算過程可在O(1)時(shí)間完成.哈希表所需空間為發(fā)送窗口/數(shù)據(jù)包大小(發(fā)送窗口上限為鏈路BDP).對(duì)數(shù)據(jù)包按MTU大小估計(jì),記錄所需的空間約為:
由于接收方不需要維護(hù)數(shù)據(jù)包的元信息(meta data),只需要保留10 s 窗口的歷史記錄,如圖4所示.
圖4 丟包率計(jì)算示意圖
窗口內(nèi)需要標(biāo)記入口序列號(hào)entry_no,當(dāng)前序列號(hào)current_no與窗口內(nèi)接收到數(shù)據(jù)包的數(shù)量nums.并根據(jù)下式導(dǎo)出窗口內(nèi)的丟包率:
丟包率反饋過程計(jì)算復(fù)雜度為O(1),不需要額外空間.
為了驗(yàn)證基于BBR 改進(jìn)后的DCCP 協(xié)議的性能,本實(shí)驗(yàn)使用網(wǎng)絡(luò)模擬器MININET[17]模擬網(wǎng)絡(luò)環(huán)境.在兩臺(tái)主機(jī)上面進(jìn)行帶寬測(cè)試,在不同丟包率環(huán)境下(0~0.4),分別與CCID2,原BBR 算法的實(shí)現(xiàn)進(jìn)行對(duì)比.測(cè)試環(huán)境的網(wǎng)絡(luò)拓?fù)淙鐖D5所示.
圖5 仿真實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)?/p>
圖5中路由器r1與r2 之間為測(cè)試的瓶頸鏈路,s1–s3為發(fā)送端,d1–d3為接收端,所有發(fā)送端與r1 連接,接收端與r2 連接.瓶頸鏈路的帶寬設(shè)置為100 Mb/s,其余所有鏈路的帶寬均為1 GB/s,路由器與客戶端連接不附加往返延遲,路由器r1與r2 之間l2的往返延遲設(shè)置為100 ms,路由隊(duì)列長(zhǎng)度max_queue_size設(shè)置為4 k,隊(duì)列控制算法使用Drop-Tail.
為了給鏈路加上負(fù)載,使用s2–s3 兩個(gè)發(fā)送端分別向d2–d3 建立TCP 連接,并且使用Vegas 算法進(jìn)行不限速數(shù)據(jù)發(fā)送,目的是將路由器r1–r2 之間的負(fù)載填充至瓶頸值,但保持路由器緩沖區(qū)的空閑.隨后在s1 分別使用DCCP-BBR,DCCP-CCID2與d1 進(jìn)行鏈路延時(shí)的測(cè)試.
圖6描述了兩種算法在傳輸時(shí)間為15 s 窗口內(nèi)的網(wǎng)絡(luò)延時(shí),顯示了從連接啟動(dòng)到平穩(wěn)狀態(tài)時(shí)候的性能.其中使用CCID2的連接進(jìn)入后迅速增大了鏈路的延遲,進(jìn)入平穩(wěn)狀態(tài)后達(dá)到高吞吐量后無法維持低RTT,這是因?yàn)镃CID2 會(huì)一直耗盡鏈路的緩沖隊(duì)列直到出現(xiàn)Drop-Tail 丟包.BBR-DCCP 則獲得比較均衡的結(jié)果,表現(xiàn)出較低的侵略性,僅在STARTUP 階段探測(cè)鏈路最大帶寬的時(shí)候主動(dòng)往緩沖隊(duì)列排隊(duì),導(dǎo)致鏈路的延時(shí)暫時(shí)的上升,當(dāng)其檢測(cè)到增大發(fā)送速率不再增加有效帶寬的時(shí)候即退出啟動(dòng)階段,隨后進(jìn)入的平穩(wěn)階段會(huì)周期性地探測(cè)帶寬,導(dǎo)致鏈路延時(shí)小幅度波動(dòng),總體上,在保證高吞吐量的同時(shí)仍可以維持低的鏈路RTT,平均鏈路延時(shí)相比CCID2 降低了20%.
圖6 延時(shí)對(duì)比測(cè)試結(jié)果
本單元測(cè)試單連接的吞吐量,使用同樣的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),使用s1 發(fā)送端與d1 進(jìn)行連接,剩余節(jié)點(diǎn)均為關(guān)閉狀態(tài),其他鏈路參數(shù)保持不變.對(duì)l2 鏈路設(shè)定不同的丟包率分別進(jìn)行測(cè)試.
圖7描述了3 種算法獨(dú)立在網(wǎng)絡(luò)中進(jìn)行數(shù)據(jù)傳輸時(shí),吞吐量隨丟包率變化的表現(xiàn).橫坐標(biāo)為鏈路丟包率,由0 逐漸增大至0.4.縱坐標(biāo)為連接在對(duì)應(yīng)丟包率下的平均吞吐量.對(duì)于CCID2 算法,在丟包率高于1%的時(shí)候就處于不可用狀態(tài),原因?yàn)閬G包對(duì)算法的窗口計(jì)算造成持續(xù)的負(fù)反饋,每一次丟包窗口將減少一半,一直收斂到接近于0.另一方面,BBR在丟包率高于20%的時(shí)候其增益系數(shù)無法平衡掉高丟包率帶來的副作用,出現(xiàn)吞吐量急劇下降.改進(jìn)后的BBR-DCCP 由于其增益參數(shù)由實(shí)時(shí)丟包率計(jì)算導(dǎo)出,動(dòng)態(tài)調(diào)整為與鏈路擁塞狀態(tài)匹配的值,避免了持續(xù)的負(fù)系數(shù)反饋.與BBR相比,BBR-DCCP 抵抗丟包的能力提高了10%.
圖7 不同丟包率下吞吐量測(cè)試結(jié)果
針對(duì)傳統(tǒng)擁塞控制算法CCID2 存在緩沖區(qū)膨脹的問題,本文提出了基于BBR 改進(jìn)的數(shù)據(jù)報(bào)擁塞控制協(xié)議算法,在原有BBR 算法基礎(chǔ)上增加了丟包率估計(jì)模型,解決了在高丟包率的網(wǎng)絡(luò)環(huán)境下連接失速的問題.實(shí)驗(yàn)結(jié)果表明,本算法可以在高帶寬利用率的同時(shí)保持相對(duì)較低的延遲,此外,通過丟包率模型動(dòng)態(tài)地調(diào)整增益系數(shù),算法在丟包率較高的環(huán)境下也能保持良好的吞吐量.