基于機器學(xué)習(xí)的網(wǎng)絡(luò)擁塞控制研究

李 婧, 管毓瑤

(上海電力大學(xué) 計算機科學(xué)與技術(shù)學(xué)院, 上海 200090)

互聯(lián)網(wǎng)發(fā)展到今天的規(guī)模,人們的生活和工作越來越離不開計算機網(wǎng)絡(luò)。近年來,網(wǎng)絡(luò)流量的空前增長對互聯(lián)網(wǎng)的性能提出了更高的要求。許多新興應(yīng)用對吞吐量、可靠性和延遲性都提出了更高的要求。雖然強力部署更高容量的有線和無線鏈路的方法有助于緩解這個問題,但更可行的方法是重新考慮更高層協(xié)議的設(shè)計,以便更有效地利用增加的物理層鏈路容量。

擁塞控制問題是一個經(jīng)典的網(wǎng)絡(luò)課題,在互聯(lián)網(wǎng)的發(fā)展中,扮演著重要的角色。網(wǎng)絡(luò)擁塞控制主要用于調(diào)節(jié)和控制網(wǎng)絡(luò)數(shù)據(jù)傳輸需求和網(wǎng)絡(luò)傳輸/處理能力之間的不匹配引起的擁塞問題,確保用戶之間有效和公平地共享網(wǎng)絡(luò)資源。

網(wǎng)絡(luò)擁塞控制的一個重點問題是討論丟包與擁塞之間的關(guān)系,并根據(jù)感知到的擁塞來采取緩解擁塞的調(diào)控。TCP的擁塞控制經(jīng)過了多次的迭代和改進,每一次都經(jīng)過研究者的精心設(shè)計和大量實驗驗證,且方案的設(shè)計基于對來自網(wǎng)絡(luò)的特定反饋信號的預(yù)定義動作的硬連線映射。然而,隨著網(wǎng)絡(luò)變得更加復(fù)雜化和動態(tài)化,設(shè)計最佳“獎勵—行為”映射變得更加困難。

近年來,機器學(xué)習(xí)、深度學(xué)習(xí)和強化學(xué)習(xí)的興起,給擁塞控制提供了新的思路,利用強大的學(xué)習(xí)能力來學(xué)習(xí)網(wǎng)絡(luò)交互的行為引起了廣泛關(guān)注。因此,針對基于機器學(xué)習(xí)的網(wǎng)絡(luò)擁塞控制協(xié)議展開研究,對于優(yōu)化網(wǎng)絡(luò)性能具有重要的意義。

1 擁塞控制模型

現(xiàn)有的擁塞模型可分為兩種:在端系統(tǒng)上,網(wǎng)絡(luò)數(shù)據(jù)包的到達速度超過了位于接收端的緩存能力,導(dǎo)致數(shù)據(jù)包排隊甚至溢出,產(chǎn)生擁塞現(xiàn)象;在網(wǎng)絡(luò)中,設(shè)備(如交換機)的存儲轉(zhuǎn)發(fā)能力不及數(shù)據(jù)包的到達速度,從而引起了排隊甚至丟包,也產(chǎn)生了擁塞現(xiàn)象。

發(fā)生在端系統(tǒng)上的擁塞模型,可以通過協(xié)調(diào)接收窗口大小來解決,而經(jīng)常討論的擁塞控制問題都是針對發(fā)生在網(wǎng)絡(luò)設(shè)備上的擁塞模型。網(wǎng)絡(luò)中的擁塞問題更為復(fù)雜,對此產(chǎn)生了大量的經(jīng)典的擁塞控制方案,如Tahoe,Reno,New Reno,CUBIC,BBR等,包含了慢啟動、擁塞避免、快重傳和快恢復(fù)等機制。

2 國內(nèi)外研究現(xiàn)狀及發(fā)展動態(tài)

1986年10月,互聯(lián)網(wǎng)第一次出現(xiàn)了的“擁塞崩潰”事件。研究者在TCP協(xié)議中引入了慢啟動、雙向時變估計和AIMD(Additive Increase Multiplicative Decrease)控制規(guī)則等一系列機制[1]來應(yīng)對擁塞,實現(xiàn)了網(wǎng)絡(luò)的穩(wěn)定性和可用性。目前,國內(nèi)外的研究者針對TCP擁塞控制展開了深入的研究,取得了一系列的研究成果。從算法的原理進行分類,可以將有代表性的解決方案分為基于規(guī)則的解決方案、基于路由反饋的解決方案和智能解決方案3類。

2.1 基于規(guī)則的解決方案

網(wǎng)絡(luò)擁塞問題出現(xiàn)以來,研究者們設(shè)計了許多基于規(guī)則的算法,根據(jù)規(guī)則可以將這些算法分為3類:基于丟包的算法、基于時延的算法以及基于丟包和時延的算法。

基于丟包的算法包括Tahoe,Reno,NewReno,BIC-TCP,TCP-CUBIC等算法,適合早期簡單的網(wǎng)絡(luò)環(huán)境,但存在在未檢測到丟包時,不斷增大發(fā)送窗口探測網(wǎng)絡(luò)帶寬,過度占用路由器緩沖區(qū)的缺點。

JACOBSON V等人[1]設(shè)計了Reno算法,引入了一系列機制(即慢啟動、擁塞避免、快速重傳和快速恢復(fù))。Reno算法對擁塞窗口(Congestion Window,CWnd)的控制如圖1所示。它是由更原始的Tahoe算法改進而來。這些機制已經(jīng)成為許多擁塞算法方案的基石。Reno算法的缺點在于:Reno算法是以數(shù)據(jù)包的丟失作為擁塞的信號,當(dāng)檢測到丟包時,就會重傳所有丟失與檢測到所丟包事件的所有的包[2]。NewReno是基于Reno的改進算法,利用一個確認(rèn)字符(ACKnowledge Character,ACK)來確定部分發(fā)送窗口,立即重傳余下的數(shù)據(jù)包,避免了Reno在快速恢復(fù)階段的許多重傳超時,提高了網(wǎng)絡(luò)性能。但是NewReno算法的缺點是在高速網(wǎng)絡(luò)中不能有效利用帶寬。

圖1 Reno算法對擁塞窗口的控制

高速網(wǎng)絡(luò)中,對于單個丟包,經(jīng)典的AIMD算法需要經(jīng)過多輪往返時間(Round-Trip Time,RTT)才能恢復(fù)到擁塞窗口,然后再進行乘法約簡,導(dǎo)致信道利用率較低。BIC-TCP算法把擁塞控制視為一個搜索問題,利用二分查找算法來調(diào)整擁塞窗口[3]。BIC的缺點是每進行一次二分查找,需要一個RTT的時間,因此不同RTT數(shù)據(jù)流查找的頻率不一樣,即RTT小的數(shù)據(jù)流更易獲得較高的帶寬。

TCP-CUBIC算法是BIC-TCP的升級版本,利用一個包含凹、凸兩部分的三次函數(shù)代替BIC-TCP的凹和凸窗口增長部分,既模擬了BIC-TCP的窗口調(diào)整算法,又解決了RTT的不公平問題,因為其擁塞窗口的增加依賴于兩個連續(xù)擁塞事件之間的時間[4]。

上述Tahoe算法、Reno算法、NewReno算法、BIC-TCP算法和CUBIC算法都是以數(shù)據(jù)包的丟失作為擁塞信號來做出調(diào)整以應(yīng)對擁塞,適合早期簡單的網(wǎng)絡(luò)環(huán)境。在未檢測到丟包時,不斷增大發(fā)送窗口去探測網(wǎng)絡(luò)的帶寬,而當(dāng)檢測到丟包時,便認(rèn)為鏈路擁塞,并減小發(fā)送窗口。

基于時延的算法通過對連接的RTT的監(jiān)測來確定擁塞窗口的調(diào)整,對鏈路擁塞的響應(yīng)比基于丟包的算法更早,其中包括TCP-Vegas,TCP-Westwood,FAST TCP等算法。但僅將時延作為擁塞信號是片面的,時延變大不一定是由于網(wǎng)絡(luò)擁塞。

TCP-Vegas[5]用于測算在RTT上期待的吞吐量和實際吞吐量的差值δ。當(dāng)δ小于低閾值,認(rèn)為該路徑并不擁擠,因此提高了發(fā)送速率。當(dāng)δ大于高閾值,這是一個強烈擁擠的信號,TCP-Vegas重新降低發(fā)送速率;否則,TCP-Vegas將保持當(dāng)前的發(fā)送速率。通過將當(dāng)前擁塞窗口除以最小RTT來計算預(yù)期吞吐量,該最小RTT通常包含路徑不擁塞時的延遲。對于每個往返時間,TCP-Vegas通過將發(fā)送的數(shù)據(jù)包數(shù)量除以采樣的RTT來計算實際吞吐量。

TCP-Westwood[6]通過計算返回ACK的速率來估計端到端可用帶寬,對于包丟失,不像TCP盲目地將擁塞窗口減少到原來的一半,而是將慢啟動設(shè)置為一個估計數(shù)。這種機制是有效的,特別是在無線鏈路上,頻繁的信道損失被錯誤地解釋為擁塞損失,因此TCP錯誤地減少了擁塞窗口。

FAST TCP[7]根據(jù)一個路徑上的往返延遲和包丟失來確定當(dāng)前擁塞窗口的大小。通過快速更新發(fā)送速率來實現(xiàn)對網(wǎng)絡(luò)擁塞的控制。該算法利用RTT估計路徑的排隊時延。當(dāng)時延遠低于閾值時,算法會大幅增加窗口;當(dāng)時延越接近閾值時,算法會緩慢降低增加速度;當(dāng)延遲超過閾值時,先緩慢地降低窗口,然后急劇地降低窗口。當(dāng)包丟失時,快速地將擁塞窗口減半,并像TCP一樣進入丟失恢復(fù)。

基于丟包和時延的算法采用協(xié)同的方式,將基于丟包的方法與基于時延的方法結(jié)合起來進行擁塞控制,代表算法有TCP-Veno,TCP-Illinois,Compound等。這種兼顧丟包和時延的方法有利于發(fā)送端感知鏈路的擁塞情況,因此后來的擁塞控制算法的思路大多沿用了這個擁塞信號。這類算法依然建立在一些基本假設(shè)之上的;當(dāng)網(wǎng)絡(luò)環(huán)境變得更加復(fù)雜時,這些規(guī)則將不再適用。

TCP-Veno[8]確定的擁塞窗口大小非常類似于TCP-NewReno,但它使用TCP-Vegas的延遲信息來區(qū)分非擁塞損失。當(dāng)包丟失發(fā)生時,如果延遲增加所推斷的隊列大小在一定的閾值內(nèi),這是隨機丟失的強指示,TCP-Veno將擁塞窗口減少20%,而不是50%。

TCP-Illinois[9]采用排隊延遲的方法,在窗口增量階段實時確定增加因子α和乘減因子β。準(zhǔn)確地說,TCP-Illinois在平均延遲d值很小時,設(shè)置一個較大的α值和一個較小的β值,用來表示擁塞不是迫在眉睫;而當(dāng)d值很大時,考慮到即將到來的擁堵而設(shè)置了一個較小的α值和一個較大的β值。通過動態(tài)調(diào)整α和β值實現(xiàn)更好的對帶寬的探索。

Compound[10]是Windows操作系統(tǒng)中的速率控制算法。當(dāng)鏈路未充分利用時,它的擁塞窗口會急劇增加。Compound的關(guān)鍵思想是在標(biāo)準(zhǔn)TCP中添加一個可伸縮的基于延遲的組件。這個基于延遲的組件有一個可伸縮的窗口增長規(guī)則,不僅可以有效地使用鏈接容量,還可以通過感知RTT中的變化及早響應(yīng)擁塞。如果檢測到瓶頸隊列,則基于延遲的組件可以優(yōu)雅地降低發(fā)送速率。

2016年,由Google提出的BBR[11]算法在擁塞信號中完全無視了丟包,第一次指出了傳統(tǒng)擁塞控制算法的問題所在。BBR算法收斂點分析如圖2所示。

圖2 BBR算法收斂點分析

圖2中,傳統(tǒng)的基于丟包信號的Reno和CUBIC等算法基本等網(wǎng)絡(luò)狀態(tài)已經(jīng)達到B點才開始采取措施解決擁塞問題,然而傳輸速率早在A點就不再增加,A點到B點這段時間的數(shù)據(jù)包的發(fā)送是徒勞的,BBR算法實現(xiàn)了在A點處收斂,在擁塞即將發(fā)生的“隱患”時期及時降低了網(wǎng)絡(luò)發(fā)生擁塞的可能性。

2.2 基于路由反饋的解決方案

基于路由反饋的解決方案涉及到擁塞控制過程中的交換機或路由器。引入顯式擁塞通知(ECN)作為擁塞信號的損失替代[12]。在主動隊列管理(AQM)方案中,例如RED和CoDel等,路由器在初始擁塞時標(biāo)記或丟棄數(shù)據(jù)包。

RED是部署在分組交換網(wǎng)絡(luò)中的網(wǎng)關(guān),用于避免擁塞。網(wǎng)關(guān)通過計算平均隊列大小來檢測初始的擁塞。網(wǎng)關(guān)可以通過丟棄到達網(wǎng)關(guān)的數(shù)據(jù)包或在數(shù)據(jù)包報頭中設(shè)置1 bit來通知網(wǎng)絡(luò)連接擁塞[13]。

CoDel用于解決Internet中的緩沖區(qū)膨脹問題[14]。CoDel的工作方式是在每個包接收和排隊時向其添加一個時間戳。當(dāng)數(shù)據(jù)包到達隊列頭部時,計算在隊列中花費的時間;它是對單個值的簡單計算,不需要鎖定,因此速度很快。如果一個包在隊列中花費的時間高于一個定義的閾值,該算法設(shè)置一個定時器在dequeue中丟棄一個包。只有當(dāng)時間窗口內(nèi)的排隊延遲超過閾值且隊列至少持有一個MTU的字節(jié)數(shù)時,才會執(zhí)行此刪除操作。

這些方法需要修改路由器和中間設(shè)備,在實際應(yīng)用中會比較困難,無法擴展到大量TCP流。

2.3 智能解決方案

隨著人工智能的蓬勃發(fā)展,基于機器學(xué)習(xí)的解決方案已經(jīng)成為一種針對所有問題的篩選,擁塞控制也不例外。

Remy將機器學(xué)習(xí)的思路第一次用在擁塞控制的速率決策問題上[15]。Remy的核心思想是通過一個目標(biāo)函數(shù)定量判定算法的優(yōu)劣程度。在生成算法的過程中,針對于不同的網(wǎng)絡(luò)狀態(tài)采取不同的方式調(diào)節(jié)發(fā)送窗口,反復(fù)修改調(diào)節(jié)方式,直到目標(biāo)函數(shù)最優(yōu)。最終會生成一個網(wǎng)絡(luò)狀態(tài)到調(diào)節(jié)方式的Map。在真實網(wǎng)絡(luò)中,可以根據(jù)Table和網(wǎng)絡(luò)狀態(tài),直接選取調(diào)節(jié)發(fā)送窗口大小的方法。但是,Remy最大的問題就是過分依賴訓(xùn)練數(shù)據(jù),當(dāng)真實網(wǎng)絡(luò)情況有所差異時,性能會大幅下降。

PCC是一種面向性能的擁塞控制,每個發(fā)送方不斷地觀察其行為和經(jīng)驗的性能之間的聯(lián)系,使其能夠始終如一地采取導(dǎo)致高性能的行為[16]。PCC設(shè)定了一個目標(biāo)函數(shù),公式為

ui(xi)=Ti·Sigmoid(Li-0.05)-xiLi

(1)

式中:Ti——第i個發(fā)送端的吞吐量;

Sigmoid( )——神經(jīng)網(wǎng)絡(luò)里的激活函數(shù);

Li——第i個發(fā)送端的丟包率;

xi——第i個發(fā)送端的發(fā)送率。

根據(jù)這個目標(biāo)函數(shù),PCC算法不斷嘗試新的發(fā)送率,直到目標(biāo)函數(shù)值達到最優(yōu)。PCC是一種在線學(xué)習(xí)的算法,優(yōu)點在于在線調(diào)整發(fā)送速率以適應(yīng)當(dāng)前網(wǎng)絡(luò)狀態(tài),缺點是拋棄了過去學(xué)到的經(jīng)驗,收斂速率慢。

PCC Vivace[17]是PCC的升級版,PCC Vivace在目標(biāo)函數(shù)中結(jié)合了時延，公式為

(2)

00

相比于PCC,PCC Vivace有更好的TCP友好性,收斂速度更快。

上述算法都是以基本機器學(xué)習(xí)思路解決擁塞控制問題。近年來,一些研究者嘗試用深度學(xué)習(xí)和強化學(xué)習(xí)[18]解決網(wǎng)絡(luò)擁塞問題。

QTCP[19]是一種基于Q-learning的TCP擁塞控制協(xié)議。在線觀察周圍網(wǎng)絡(luò)環(huán)境的情況下,該協(xié)議能夠自動識別最優(yōu)CWnd的變化策略。為了加快學(xué)習(xí)過程,該算法使用了函數(shù)逼近——Kanerva算法。這是一種有效的方法,可以減少使用抽象狀態(tài)來表示搜索和探索所需狀態(tài)空間的大小。Kanerva在編碼時考慮了整個狀態(tài)空間由一個精心選擇的狀態(tài)空間子集表示,根據(jù)這個子集存儲訓(xùn)練值并評估派生策略,從而顯著降低了訓(xùn)練的內(nèi)存消耗和計算復(fù)雜度。

TCP-Drinc[20]是一個基于DRL(深度強化學(xué)習(xí))的代理,在發(fā)送端執(zhí)行。這里結(jié)合的是知名的DQN[21]算法。在DQN算法中,將強化學(xué)習(xí)中的狀態(tài)和動作的歷史轉(zhuǎn)換存儲在經(jīng)驗池中,然后引入一個附加的目標(biāo)網(wǎng)絡(luò)來計算目標(biāo)值。此協(xié)議認(rèn)為,TCP擁塞控制的一般問題應(yīng)視為一個延遲的分布式?jīng)Q策問題,并且TCP擁塞控制是一個部分可見馬爾可夫決策過程。因此,考慮到了在深度強化學(xué)習(xí)中,一個動作at開始影響環(huán)境之前可能有個時延,agent收到rewardr(st,at)也有個時延。將此時延設(shè)計成了特征輸入到深度卷積神經(jīng)網(wǎng)絡(luò)(Deep Convolutional Neural Network,DCNN)中。

在TCP-Drinc的設(shè)計中,分為如下步驟:特征的選擇、reward的設(shè)置、狀態(tài)和動作的定義、經(jīng)驗池的形式、基于DCNN的agent的最終設(shè)計。TCP-Drinc所應(yīng)用到的DCNN結(jié)構(gòu)如圖3所示[20]。

圖3 DCNN結(jié)構(gòu)

ns3-gym是為強化學(xué)習(xí)應(yīng)用于網(wǎng)絡(luò)研究的第一個框架[22]。它是基于OpenAI開發(fā)的gym和ns3網(wǎng)絡(luò)模擬器開發(fā)的工具包。ns3-gym將ns3仿真表示為gym框架中的環(huán)境,實現(xiàn)來自仿真器的實體的狀態(tài)和agent的交互,以滿足agent的學(xué)習(xí)目的。

3 結(jié) 語

現(xiàn)有的基于規(guī)則的擁塞控制協(xié)議僅利用丟包、時延等信息作為擁塞信號,并不能很好地掌握網(wǎng)絡(luò)帶寬的利用情況,適應(yīng)日漸復(fù)雜的網(wǎng)絡(luò)環(huán)境。雖然目前已提出了不少基于機器學(xué)習(xí)算法的網(wǎng)絡(luò)擁塞控制協(xié)議,但由于網(wǎng)絡(luò)結(jié)點的反饋信息十分有限,發(fā)送端無法及時探知網(wǎng)絡(luò)真實環(huán)境的擁塞狀態(tài),該領(lǐng)域仍舊是個開放的課題。采用更合適的手段來描述網(wǎng)絡(luò)環(huán)境擁塞狀態(tài),更準(zhǔn)確地探索可用帶寬,從而更精確地調(diào)節(jié)CWnd,不僅可以保證網(wǎng)絡(luò)的穩(wěn)定和高效運行,同時也是保證各種其他互聯(lián)網(wǎng)服務(wù)質(zhì)量的基礎(chǔ)和前提。