李 婧, 管毓瑤

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

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

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

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

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

1 擁塞控制模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 BBR算法收斂點分析

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

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

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

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

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

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

2.3 智能解決方案

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

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

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

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

(1)

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

Sigmoid( )——神經網絡里的激活函數;

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

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

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

PCC Vivace[17]是PCC的升級版,PCC Vivace在目標函數中結合了時延，公式為

(2)

00

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

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

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

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

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

圖3 DCNN結構

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

3 結 語

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