基于特征分析方法消解RED冗余參數*

吳 斌，馬繼濤，鄔 平，譚 鵬

(云南省科學技術情報研究院，云南 昆明 650051)

基于特征分析方法消解RED冗余參數*

吳 斌，馬繼濤，鄔 平，譚 鵬

(云南省科學技術情報研究院，云南 昆明 650051)

RED算法是網絡擁塞控制的基礎算法，加載算法需要設置隊列平均長度、隊列丟包上下限閾值、數據包平均尺寸等多項參數，且參數設置沒有明確的規則限制和理論依據，不合理的參數值會削弱算法的擁塞控制效果。在網絡擁塞特征分析的基礎上，挖掘數據包達到速率和數據包處理速度兩個擁塞控制指標之間的關系，建立指標與RED算法參數的映射，消解多余參數并確定參數值域范圍，改善算法在網絡環境中的擁塞控制效果，提高算法的實用性。

隨機早期偵測；特征方程；擁塞控制；線性映射

1 引言

隨機早期偵測RED(Random Early Detection)是網絡擁塞控制經典算法，其主要設計思路是在平均隊列長度和網絡擁塞程度之間建立分段函數，通過概率方法控制隊列數據包的丟棄行為，將平均隊列長期穩定于擁塞控制范圍，最終達到擁塞控制的目的[1]。RED算法在實際應用中面臨的難點是參數的動態控制與調整以適應網絡狀態，其原因在于幾個具有耦合關系的參數對不同網絡狀態很敏感，若參數設置不當將削弱算法網絡擁塞控制能力，降低網絡整體性能[2～5]。

近年來，眾多學者針對這一難點提出了許多新的理論方法。文獻[2]利用非線性滑?？刂品椒ń鉀Q線性方法不能準確跟蹤網絡動態變化問題，避開系統輸入受限問題，存在緩沖區溢出的可能性。文獻[3]基于TCP自同步特性改進RED算法，獲得比原有算法更寬松的參數設置范圍，但沒有對參數取值合理性進行分析，參數對網絡狀態敏感問題仍舊存在。文獻[4]利用數學期望分析TCP/RED擁塞控制機制離散模型穩定狀態行為，推導網絡穩定狀態期望值與參數解析關系式、算法配置及應用難度較大。文獻[5]利用二次圓函數計算丟包概率，減少算法中最大丟棄概率maxp與隊列qmax兩項參數，沒有綜合考慮其參數的耦合性。為此，本文將利用特征分析方法建立網絡狀態特征方程，基于工程經驗消解冗余參數。

2 網絡擁塞特征分析

2.1 擁塞分析

網絡擁塞通常發生于寬帶鏈路與窄帶鏈路的連接點，由于節點處數據包處理能力有限，當鏈路數據包到達速率大于節點處數據包處理速率，隊列緩存出現累積效應；若單位時間內數據到達速率遠遠大于節點處數據包處理速率，可能發生Floyd S等人[6]于1999年所論述的擁塞崩潰現象。

若要在時間t內避免擁塞崩潰，網絡節點處數據包到達率(dμ(t)/dt)減數據包離開率(dυ(t)/dt)與數據隊列緩存長度(dl(t)/dt)之和應小于或等于物理緩存長度L：

(1)

2.2 網絡數據包到達及處理分析

(1)網絡數據包到達分布。

由于網絡數據包具有突發特性，且在單位時間內到達的數據包與起始時間無關，只與時間長度有關，數據包到達數量呈非線性單調增加，滿足泊松流分布特性[7]。根據泊松流定義網絡數據包到達分布：

(2)

網絡節點處數據包到達率為λe-λt，在t時間內平均到達數據包個數mi的期望值：

(3)

(2)網絡節點數據包處理時間分布。

網絡節點數據包處理時長與數據包到達時間分布無關，即到達過程與處理過程相互獨立。為方便量化處理過程，我們將網絡節點視同為黑盒[8]，單位時間內離開數據包速率作為衡量數據包處理性能指標。由于節點數據包處理速度為常量，數據包處理時間滿足均勻分布[9]：

(4)

在t時間內平均離開的數據包個數ni的期望：

(5)

(3)隊列緩存長度時間分布。

隊列緩存長度時間分布與網絡數據包到達分布、網絡節點數據包的處理時間分布具有相關聯系。設節點處緩存容限無限大(L→∞)，以網絡節點數據包處理時間為單位時間(t)，則n個單位時間長度(T=nt)范圍內三者關系如式(6)所示：

(6)

3 RED冗余參數消解

3.1 參數說明

網絡節點加載RED擁塞算法需要設置隊列平均長度、隊列丟包上下限閾值、數據包平均尺寸等多項參數[10]，參數說明見表1。

Table 1 Arguments of the algorithm表1 算法參數說明表

隊列中設置數據包下限閾值(min)和上限閾值(max)，旨在界定一個合理范圍，使網絡在不同擁塞程度有不同的丟棄概率，丟棄概率與擁塞程度成線性關系。

3.2 參數說明

RED算法將擁塞程度(D)與隊列平均長度相關聯[11]，我們認為擁塞程度與網絡發生擁塞的可能成正比，因此采用分段表示擁塞程度：

(7)

首先，根據式(7)的定義，當隊列占滿時到達數據包將被全部丟棄，此刻丟棄概率為1，而隊列為空時丟棄概率為0。若將min與max直接與平均隊列長度映射會使算法在無擁塞情況下也產生丟包行為。為保證算法可用性，借鑒前人實驗結果[12]，當平均隊列大于75%時網絡節點有擁塞發生的可能，將可用隊列緩存長度與擁塞發生區間進行線性映射，消解min、max和probability三個參數。

其次，網絡節點數據包處理能力有限，數據包平均處理時長等于節點數據包處理速度與網絡平均封包之商。根據工程經驗[13]，節點數據包處理速度在隊列緩沖區飽和情況下趨近于節點上行網絡速率，這意味著在網絡擁塞可能發生的情況下，可將節點數據包平均處理速度與節點數據包離開速度等同處理。

第三，網絡隊列長度取值太大則增加網絡延遲，太小又容易增加數據包的丟棄數量[14]。Internet數據包傳輸容忍延遲為300 ms[15]，緩存隊列長度取值根據節點網絡接口數據包發送速率、數據包傳輸容忍延遲以及數據包平均尺寸計算，消解參數limit。

最后，為減少數據丟棄概率計算的頻率，算法采用burst參數對每輪計算的隊列平均長度進行調整。我們假定網絡處理數據單位時間內丟棄概率不變時，平均隊列長度進入max與min區域，基于二分法消解burst。

消解步驟具體如下：

步驟1消解緩存隊列長度參數，計算式：limit=bandwidth×0.3/(avpkt×8)；

步驟2消解隊列上下限閾值參數，計算式：max=limit以及min=limit×75%；

步驟3消解突發數據包參數，計算式：burst=limit/2(max-min) ×bandwidth/avpkt；

冗余參數消解后，加載RED擁塞控制算法只需要取值實際物理網絡接口的連接速率以及網絡數據包平均尺寸，降低了RED應用的難度。

4 參數驗證

4.1 驗證方法

為了驗證算法消解后的參數能否對不同網絡出現的擁塞現象進行有效控制，我們在Opnet仿真環境中模擬網絡路由節點兩端不同寬/窄帶寬鏈路，包括小型企業接入(100M局域網-2MADSL租用線路)、組織機構接入(100M局域網-10M光纖租用線路)和大中型企業接入(100M局域網-100M光纖租用線路)三種常見環境，人為制造網絡擁塞現象(設置ecn為0值，即發生擁塞時節點不通知遠程主機發包速率過快)。從網絡延遲、丟包率兩個方面來驗證bandwidth和avpkt兩個參數的RED算法在發生擁塞時網絡響應能保持一個可容忍的范圍，具體配置見表2。

Table 2 Simulation configuration forarguments test of the algorithm表2 算法參數驗證仿真配置

利用參數消解計算的數值與前人經驗設置范圍趨同[17, 18]，參數消解方法對于不同網絡具有較好的適應性。

4.2 實驗結果分析

為能實際反映算法對于三種不同網絡連接時擁塞參數的控制效果，選擇節點窄帶鏈路的網絡延遲、RED平均隊列、鏈路利用率、數據包接收速率和數據包丟棄速率進行測量。

(1)100 M Ethernet-2 M ADSL(見圖1)。

仿真測試環境數據發送時間長度為150 s，2分鐘網絡延遲增加到300 ms左右；RED平均隊列長度達到76，與max參數設置趨同；鏈路利用率為100%，網絡發生擁塞，數據包丟棄率為40包/s，接收率為250包/s，丟棄率為40/(250+40)?13%，300 ms延遲為數據包傳輸容忍延遲，說明網絡發生擁塞時，網絡仍能保持通信，算法參數的取值較好地適應了網絡環境，沒有引起取值不當導致網絡擁塞現象發生[19]。

Figure 1 100 M-2 M congestion control test圖1 100 M-2 M 擁塞控制測試

(2)100 M Ethernet-10 M Ethernet(見圖2)。

在數據源發送速率不變的情況下，鏈路利用率只有25%，此時網絡處于不飽和狀態，因此算法沒有以概率方式丟棄數據包，避免了網絡鏈路不飽和時算法強制丟包的現象，此時網絡延遲為6 ms。算法運行于節點中，增加了節點數據包處理的負荷，傳輸延遲較網絡空閑時略有增加。

Figure 2 100 M-10 M congestion control test圖2 100 M-10 M 擁塞控制測試

(3)100 M Ethernet-100 M Ethernet(見圖3)。

當數據源發送速率不變且節點兩端均為100 M連接時，鏈路利用率幾乎為零，鏈路帶寬處于空閑狀態，RED平均隊列為0，說明到達數據包被立即處理，無丟包現象發生，此時網絡傳輸延遲為4 ms，RED算法不干預傳輸過程。

Figure 3 100 M-100 M congestion control test圖3 100 M-100 M 擁塞控制測試

5 結束語

通過特征分析擁塞控制指標與參數之間關系，通過映射方法消解RED算法中隊列緩存長度、隊列丟棄上/下限閾值、數據包丟棄概率及突發傳輸的數據包五個需專家經驗才能配置的復雜參數項。算法僅需配置網絡數據包平均尺寸和節點處的網絡接口連接速率兩個參數，降低了RED算法在傳統應用中的人工干預，提高了算法的適用性。實驗表明，進行參數消解后的算法能夠適應不同網絡環境需要，在保障RED算法擁塞控制效果的同時降低了算法應用難度。

[1] Wu Ping, Wu Bin. Research on the adaptability model of RED queue’s control measurements[J]. Computer Systems & Applications, 2008,17 (11):25-28.(in Chinese)

[2] Wang Hong-wei,Yu Chi,Jing Yuan-wei.Global sliding mode control for nonlinear network systems with input restriction[J]. Journal of Northeastern University(Natural Science), 2010, 31(3):326-329.(in Chinese)

[3] Chen Xiao-long, Tian Yi-qiang, Zhang Yun. Stability analysis of improved TCP/RED model[J]. Computer Engineering, 2010, 36(10):19-21.(in Chinese)

[4] Hu Xiao-qing. Analysis and parameter setting for TCP/RED discrete model [J]. Computer Engineering, 2011, 37(17):75-77.(in Chinese)

[5] Jiang Wen-gang, Sun Jin-sheng, Wang Zhi-quan. New revised queue management algorithm of RED: RED-r[J]. Application Research of Computers, 2012, 29(7):2632-2634.(in Chinese)

[6] Floyd S, Fall K. Promoting the use of end-to-end congestion control in the Internet[J]. IEEE/ACM Transactions on Networking, 1999, 7(4): 458-472.

[7] Ge Yu-bo. Probability and mathematical statistics [M]. Beijing: Tsinghua University Press, 2005.(in Chinese)

[8] Yang Jin-tao, Guo He-qing. Study of the test case base of black box testing[J]. Computer Engineering & Science, 2006，28(5):130-132.(in Chinese)

[9] Casella G,Berger R.Statistical inference [M].2nd Edition. Florence: Thomson- Brooks/Cole, 2008.

[10] Kuznetsov A, Makarenko A, Salim J H. Tc-red(8)-Linux man page[EB/OL].[2002-12-01]. http://linux.die.net/man/8/tc-red.

[11] Chen Zuo, Li Ren-Fa, Xu Cheng, et al. Steady state error analysis of RED queue[J]. Journal of Computer Research and Development, 2004,41(11):1874-1878.(in Chinese)

[12] Huang Yan-qin. An improved active RED queue scheduling algorithm[J]. Digital Technology and Application, 2010(3):105-106.(in Chinese)

[13] Wu Ping, Wu Bin. Optimizing process performance of network traffic management model using regression analysis[J]. Computer Engineering and Applications, 2012, 48(4):104-106.(in Chinese)

[14] Zhao Yi, Wang Xiang-ting. Use of variable length of queue AQM improvement and research[J]. Shanxi Electronic Technology, 2009(1):85-86.(in Chinese)

[15] Bi Jing-ping, Wu Qi, Li Zhong-cheng. Measurement and analysis of Internet delay bottlenecks[J]. Chinese Journal of Computers, 2003,26(4):406-416.(in Chinese)

[16] Werner W A, Salim J H, Kuznetsov A. Differentiated services on Linux[C]∥Proc of Global Telecommunications Conference, 1999:831-836.

[17] Kalinowski S. Traffic shaping fur open WRT[EB/OL].[2006-12-01]. http://svenkalinowski.de/linux-wiki/TSHAPER.

[18] Leonardo B. RED queuing discipline[EB/OL].[2012-12-01]. http://www.softwareopal.com/qos/default.php.

[19] Ziegler T, Fdida S, Brandauer C. Stability criteria for RED with bulk-data TCP traffic[C]∥Proc of IFIP ATM&IP Working Conference, 2000:1-13.

附中文參考文獻：

[1] 鄔平，吳斌. 隨機早期偵測隊列控制測度自適應性模型研究[J]. 計算機系統應用, 2008, 17(11):25-28.

[2] 王宏偉，于馳，井元偉. 輸入受限的非線性網絡系統全局滑模控制[J]. 東北大學學報 (自然科學版), 2010, 31(3):326-329.

[3] 陳曉龍，田義強，章云. 改進的TCP/RED模型的穩定性分析[J]. 計算機工程, 2010, 36(10):19-21.

[4] 胡小青. TCP/RED離散模型分析及參數設置[J]. 計算機工程, 2011, 37(17):75-77.

[5] 姜文剛，孫金生，王執銓. 改進的RED隊列管理算法: RED-r[J]. 計算機應用研究, 2012, 29(7):2632-2634.

[7] 葛余博. 概率論與數理統計[M]. 北京：清華大學出版社, 2005.

[8] 楊勁濤，郭荷清. 黑盒測試用例基的研究[J]. 計算機工程與科學, 2006,28(5):130-132.

[11] 陳佐，李仁發，徐成, 等. RED隊列穩態誤差分析[J]. 計算機研究與發展, 2004,41(11):1874-1878.

[12] 黃燕琴. 一種改進的主動隊列調度RED算法[J]. 數字技術與應用, 2010(3):105-106.

[13] 鄔平，吳斌. 采用回歸方法優化網絡流量管理模型處理性能[J]. 計算機工程與應用, 2012,48(4):104-106.

[14] 趙憶，王香婷. 利用可變隊列長度的AMQ改進與研究[J]. 山西電子技術, 2009(1):85-86.

[15] 畢經平，吳起，李忠誠. Internet延遲瓶頸的測量與分析[J]. 計算機學報, 2003,26(4):406-416.

WUBin,born in 1977,MS,senior engineer,his research interest includes network management and scheduling.

馬繼濤(1974-),男,云南昆明人，碩士，高級工程師，研究方向為網絡管理。E-mail:mjt@ynst.net.cn

MAJi-tao,born in 1974,MS,senior engineer,his research interest includes network management.

鄔平(1967-),男,云南昆明人，高級工程師，研究方向為軟件工程。E-mail:wuping@ynst.net.cn

WUPing,born in 1967,senior engineer,his research interest includes software engineering.

EliminatingredundantargumentsofREDbyfeatureanalysis

WU Bin，MA Ji-tao，WU Ping，TAN Peng

(Yunnan Academy of Scientific & Technical Information,Kunming 650051,China)

The RED algorithm is the basis of network congestion control.By using this algorithm, more than one parameter,such as queue average length,limit value of dropping packets,average size of packets,need to be loaded. What’s more,arguments’values are set without clear rules and the theoretical basis and unreasonable values weak the effect of the congestion control algorithm. The relationship of two system performance indicators of arrival rate of packets and the capability of data processing are analyzed by the way of feature analysis and build up a map relation between indicators and arguments of RED.Furthermore,excess parameters are combined and the ranges of values are confirmed by using the linear relation among parameters.The congestion control effect of the algorithm is improved in the network environment and increase the practicality of RED.

random early detection;characteristic equation;congestion control;liner mapping

1007-130X(2014)08-1519-05

2013-01-03;

：2013-03-26

TP393.072

：A

10.3969/j.issn.1007-130X.2014.08.016

吳斌(1977-),男，云南昆明人，碩士，高級工程師，研究方向為網絡管理與調度。E-mail:star_amethyst@qq.com

通信地址：650051 云南省昆明市云南省科學技術情報研究院

Address:Yunnan Academy of Scientific & Technical Information,Kunming 650051,Yunan,P.R.China