一種面向網絡擁塞的AQM算法研究

吉曉香

關鍵詞： 網絡擁塞; 控制方法; 數據驅動方式; AQM; 控制系統設計; 仿真測試

中圖分類號： TN915?34; TP393 ? ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）14?0074?04

Research on AQM algorithm dealing with network congestion

JI Xiaoxiang

（Nanjing Normal University Taizhou College， Taizhou 225300， China）

Abstract： The AQM algorithm combining with the control theory usually has the deficiencies of complex calculation and long feedback period. Therefore， a calculation process control method of the AQM separation algorithm is proposed in this paper by adopting the database and data?driven mode， and combining the interface design of the MySQL database and NS2. Taking the RED algorithm as an example， the simulation test for the above control method was carried out with the NS2 software. It is found that the data?driven mode can effectively reduce the time delay and packet loss rate of the RED algorithm， which indicates that the data?driven mode used in this paper is feasible and effective for AQM algorithm implementation， and can provide a new idea for the network congestion algorithm.

Keywords： network congestion; control method; data?driven mode; AQM; control system design; simulation test

隨著網絡和信息社會的不斷發展，人們對網絡的依賴性日益提高，網絡用戶和服務（如物聯網、云計算、云存儲等）的規模也日益龐大，給網絡的速度和性能提出了較大的挑戰[1?2]。如何有效配置和優化網絡資源，避免網絡擁塞的發生成為當前網絡研究的重要問題[3]。目前，控制網絡擁塞的兩大有效機制為主動隊列管理AQM算法和TCP協議[4?5]。其中，AQM算法結合控制理論在網絡性能的改善方面能夠發揮重要的作用;然而，結合控制理論的AQM算法存在計算復雜、反饋周期（在線計算時間）長等缺陷，嚴重影響了算法的性能，不利于網絡擁塞的有效控制[6]。因此，本文針對這一問題，基于數據庫和數據驅動方式，結合MySQL數據庫與NS2的接口設計，提出一種AQM算法的控制方法。該方法借助離線計算的數據驅動方式，將算法的輸入數據和離線計算獲得的輸出數據存儲在數據庫的表格中，從而避免了NS2仿真軟件中的在線計算過程。在分離算法計算過程的同時，有效提高了算法的運行速度和效率。

1 ?理論基礎

1.1 ?主動隊列管理AQM算法

AQM算法主要運行于路由器等網絡設備中，用于實時檢測網絡的擁塞狀況（隊列長度）。在隊列溢出前丟包，并產生相應的反饋信息，調整發送端的傳輸速率，使網絡具備較高的穩定性和魯棒性、較快的響應性、較小的延遲、較低的丟棄概率以及較高的鏈路利用率。目前，已經提出了眾多種經典的AQM算法（如REM算法、PI算法、RED算法等），但大多存在算法復雜、在線計算周期長、實時控制網絡能力差等缺陷[7?9]。

1.2 ?數據驅動設計思想

數據驅動的設計思想是基于已有的輸入輸出I/O數據（受控對象）對控制器進行設計，從而完成被控系統的功能期望（包括優化、決策等）[10]。其中，數據包括了在線和離線數據，系統的在線數據會隨系統的控制方法、結構參數或者其他擾動的變化而實時變化，因此利用實時數據和反饋機制可以使數據驅動的控制器具備較強的抗干擾、適應和鎮定能力;而系統的離線數據包含了系統較多的歷史運行信息，利用離線數據可以提高控制器的穩定性。本文采用閉環控制方式對數據驅動設計思想下的AQM算法進行設計，其運行過程可描述為：首先，對網絡系統的擁塞進行實時監控和檢測;其次，發送擁塞相關信息給擁塞控制點;最后，控制反饋的擁塞信息并對擁塞進行消除。

1.3 ?NS2仿真軟件

作為一款使用廣泛的網絡模擬仿真軟件，NS2仿真軟件實際上是以離散事件為基礎驅動的模擬器。該模擬器配備了網絡技術的多種模塊，能夠利用Otcl和C++語言實現各類網絡協議（如TCP，FTP等）、路由隊列管理機制（PID，RED等）及路由算法（靜態和動態路由）、組播SRM和MAC子層等仿真實驗，具有擴展性強、速度快、效率高、源代碼開源等優勢[11]。按照實驗模塊是否需要添加或修改，可以單獨借助Otcl腳本的編寫或同時借助C++與Otcl類的創建及Otcl腳本的編寫來完成仿真實驗。其一般的仿真步驟（已完成實驗模塊的添加工作）依次為：對網絡拓撲進行設計，并完成Otcl實驗腳本的編寫;添加協議;配置模型參數（根據實驗要求）、設置網絡對象（產生trace文件，用于全程事件的記錄）;編寫畫圖等輔助程序;運行腳本以開始實驗;畫出仿真結果。

2 ?AQM控制系統的設計

2.1 ?控制系統結構設計

根據數據驅動設計思想，AQM算法的控制系統可根據圖1所示進行設計，具體的運行過程可描述為：

1） 對算法丟包率P進行離線計算，之后將I/O數據（包含控制策略）存儲至數據庫，并將AQM算法相關參數與上述數據進行綁定;

2） 在算法中編寫相關的接口程序以完成接口的設計編譯工作，編寫連接程序（建立在NS2底層中）以實現與數據庫的數據交換;

3） 借助Otcl語言查詢并調用數據庫中存儲的丟包率及其他數據，以執行相應的丟包操作。

2.2 ?數據庫與接口設計

針對本文AQM算法所需控制器只需將I/O數據存放至數據庫的特點，文中選用容量較小、操作簡單、成本較低的MySQL作為數據庫[12]。因此，數據庫與軟件接口的設計可以借助MySQL數據庫的API函數（C語言連接）和NS2仿真軟件的TclClass機制來實現，即構建編譯接口類Class TclMySQL。具體而言，在進行仿真實驗時，NS2軟件的各類模塊會借助全局變量TclMySQL的實例化來完成與數據庫的連接，從而進行數據庫中的數據讀取操作。接口設計的示意框圖如圖2所示。

3 ?AQM控制系統的實現

本文以RED控制器為例，對文中AQM控制系統的實現和仿真結果進行說明。RED算法主要借助參數（wq，maxp，minth，maxth）關系的確定來判斷網絡擁塞的程度，并計算丟失概率且進行丟包，從而避免或者緩解網絡擁塞。RED算法中的平均排隊長度avg計算公式為：

[avg←（1-wq）·avg+wq·q] （1）

式中，[wq]∈[0，1]為權重系數，q代表的是瞬時隊列長度（采樣測量）。

若avg

[Pb=0， ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?avg

式中，maxp代表的是丟包概率（小于1）。

相應的丟棄概率P，則可按照式（3）進行計算：

[P←Pb（1-count·Pb）] （3）

式中，P隨count和avg的變化而變化，而count代表的是位于緩沖區中的包個數。

根據上述RED算法的式（2）和式（3）可得到RED控制器所需的輸入輸出數據，將其存為txt文件以備后續導入數據庫。其中，輸入數據為avg（設置為20～80包）和count（設置為0～30組），輸出數據則為P。相應的部分數據輸出程序如下：

void main（）{

double minth=20.0; double maxth=80.0;

double maxP=0.02;

double avg; double Pb; double P; double count;

for（avg=74;avg<=80;avg++）{

Pb=maxP*（（avg-minth）/（maxth-minth））;

for（count=0;count<=30;count++）

{

P=Pb/（1=count*Pb）;

count<

}}}

數據庫方面，將avg和count的數據類型設置為float，將P的數據類型設置為decimal（M，D）。其中，M和D分別代表根據需要留取的整數位及小數位的位數。

4 ?仿真結果分析

在仿真實驗之前，設置如下參數：仿真時間設為50 s;瓶頸鏈路（R1和R2路由器之間）的容量設為1.8 Mb/s，相應的時延為25 ms，隊列管理則選用AQM算法;其他鏈路的容量則設為2.5 Mb/s，相應的時延設置為15 ms，隊列管理選用DropTail;路由器中的隊列長度設置為120個封包大小;針對RED算法，選取經典參數wq=0.001 5，maxth=80，minth=20，maxP=0.02。相應的網絡拓撲結構如圖3所示。

分別選用不同的負載N（30和80）對本文結合數據驅動方式的RED算法（簡稱為DRED控制方法）與傳統的RED算法進行仿真測試及對比。負載較小（N=30）時的平均隊列長度、瞬時隊列長度和丟包率的變化曲線如圖4～圖6所示。從圖中可以發現，DRED控制方法和RED算法在平均隊列長度、瞬時隊列長度和丟包率上均具有相似的變化趨勢。由此表明，本文數據驅動設計在負載較低時具有較高的有效性和可行性。從圖4可以看到，DRED控制方法相比于傳統的RED算法具有更優的穩定性，其平均隊列抖動更小;從圖6可以發現，DRED控制方法相比于RED算法具有更小的丟包率。此外，從仿真實驗結果中還發現，DRED控制方法具有更小的延時，為0.180 357 s，小于RED的0.184 246 s。這相對于排隊延遲來講具有較大的意義，能夠有效減少丟包率。總體來看，在負載不大時DRED控制方法的性能略優于RED算法，表明結合了數據驅動設計思想和離線數據讀取方式下的AQM算法，對于緩解網絡擁塞具有較大的潛力。

負載較大（N=80）時的平均隊列長度、瞬時隊列長度和丟包率的變化曲線如圖7～圖9所示。從圖中可以發現，DRED控制方法和RED算法在平均隊列長度、瞬時隊列長度和丟包率上同樣具有相似的變化趨勢。表明本文數據驅動設計在負載較高時，同樣具有較高的有效性和可行性。從圖9中同樣可以看到，DRED控制方法相較于RED算法具有更低的丟包率。此外與低負載時類似，DRED控制方法在較高負載時同樣具有更小的時延，為0.220 134 s，小于RED的0.238 479 s，表明DRED控制方法在較大的負載情況下相較于RED算法具有更快的瓶頸鏈路處理速率，使時延（端到端）大幅降低，從而有效減小了丟包率。總體來看，在負載較大時DRED控制方法的性能優勢更為明顯，表明結合了數據驅動設計思想和離線數據讀取方式下的AQM算法，確實能夠有效緩解網絡擁塞。

5 ?結 ?語

結合控制理論的AQM算法通常存在計算復雜、在線計算時間長等缺陷，因此，基于數據庫和數據驅動方式，本文結合MySQL數據庫與NS2的接口設計，提出一種AQM算法的實現方法。該方法借助離線計算的數據驅動方式，分離算法的計算過程，從而達到提高算法運行速度和效率的目的。本文以RED算法為例，在該算法中引入數據驅動的設計思想，并在NS2仿真軟件中進行實現和測試。結果表明，結合數據驅動方式的RED算法相較于傳統的RED算法具有更小的時延與更低的丟包率，說明了本文使用數據驅動方式實現AQM算法，在網絡擁塞的緩解方面具有巨大的潛力。

參考文獻

[1] 陳金超，謝東亮.無線網絡TCP擁塞控制算法研究綜述[J].軟件，2015，36（1）：82?87.

CHEN Jinchao， XIE Dongliang. Survey on TCP optimization in wireless network [J]. Computer engineering & software， 2015， 36（1）： 82?87.

[2] 陳鴻俊，范太華，穆炯.基于多目標拆分優化思維的擁塞網絡數值調度方法[J].沈陽工業大學學報，2016，38（4）：440?444.

CHEN Hongjun， FAN Taihua， MU Jiong. Numerical scheduling method for network congestion based on multi?objective resolution optimization [J]. Journal of Shenyang University of Technology， 2016， 38（4）： 440?444.

[3] WELZL M. Network congestion control： managing Internet traffic [M]. New York： John Wiley & Sons， 2005.

[4] QUET P F， OZBAY H. On the design of AQM supporting TCP flows using robust control theory [J]. IEEE transactions on automatic control， 2004， 49（6）： 1031?1036.

[5] 羅成，謝維信.傳感器網絡擁塞避免與控制的模糊AQM算法[J].電子學報，2014，42（4）：679?684.

LUO Cheng， XIE Weixin. Fuzzy AQM for congestion avoidance and control in sensor networks [J]. Acta electronica sinica， 2014， 42（4）： 679?684.

[6] 劉雪梅.基于模糊控制理論的主動隊列管理算法研究[D].南京：南京理工大學，2013.

LIU Xuemei. Research on active queue management algorithms based on fuzzy control theory [D]. Nanjing： Nanjing University of Technology， 2013.

[7] 陳炳卿，牛玉剛.一種基于RBF網絡的參數自調整REM算法[J].華東理工大學學報（自然科學版），2010，36（3）：428?432.

CHEN Bingqing， NIU Yugang. Parameter self?regulation REM algorithm based on RBF neural network [J]. Journal of East China University of Science and Technology（Natural science edition）， 2010， 36（3）： 428?432.

[8] 施利利，盧先領.適用于WSNs的擁塞自適應多徑路由算法[J].傳感器與微系統，2014，33（8）：141?144.

SHI Lili， LU Xianling. Congestion adaptive multipath routing algorithm for WSNs [J]. Transducer and microsystem technologies， 2014， 33（8）： 141?144.

[9] 范紀松，武欣嶸，劉杰.一種改進RED算法穩定性研究[J].系統仿真學報，2010，22（7）：1711?1715.

FAN Jisong， WU Xinrong， LIU Jie. Modified RED stability research [J]. Journal of system simulation， 2010， 22（7）： 1711?1715.

[10] 哀微.基于隨機逼近的數據驅動控制方法研究[D].廣州：華南理工大學，2011.

AI Wei. Research on data?driven control method based on stochastic approximation [D]. Guangzhou： South China University of Technology， 2011.

[11] ISSARIYAKUL T， HOSSAIN E. Introduction to network simulator NS2 [M]. New York： Springer， 2012.

[12] WIDENIUS M， AXMARK D， DUBOIS P. MySQL reference manual [M]. Sebastopol： O′Reilly & Associates， Inc.， 2002.