一種降低丟包率的主動隊列管理改進算法

張 潔，韓 波，盧 瓊

（商洛學院 數(shù)學與計算機應用學院，陜西商洛 726000）

擁塞控制一直是互聯(lián)網(wǎng)中最重要的問題之一。隨著越來越多的基于UDP的上層多媒體應用被部署，單純依賴TCP端到端的傳統(tǒng)擁塞控制算法不再可行[1]。在網(wǎng)絡中，尤其是網(wǎng)絡中的路由器，應該在資源分配方面承擔主要作用，這樣有利于有效的控制/阻止擁塞，這一類策略被稱為主動隊列管理（AQM）。在眾多AQM策略中，隨機早期檢測算法（簡稱RED）是目前研究的熱門。RED算法旨在解決全局同步問題和突發(fā)數(shù)據(jù)源受限問題。一些研究者提出，RED算法的性能相比普通的數(shù)據(jù)包丟棄策略沒有明顯的提升[2]。而更多的研究者[3]則認為，RED算法與普通的棄包策略相比有明顯的優(yōu)勢但仍然不完美，事實上，這種不完美則主要在于以下若干原因。

RED算法的性能極大的受影響于其參數(shù)的設置[4]。在RED算法中至少有4個參數(shù)，分別名為：最大閾值（maxth）、最小閾值（minth）、最大棄包概率（maxp）和加權因子（wq），這四個參數(shù)必須設置的非常恰當才能明顯提高RED算法的性能；RED算法的性能對于競爭數(shù)據(jù)源/數(shù)據(jù)流的數(shù)目比較敏感；RED算法的性能也受到數(shù)據(jù)包長度的影響；RED棄包概率函數(shù)是一個分段線性函數(shù)。它由一個三元組（minth,maxth,pmax）來定義。當某個數(shù)據(jù)包到達，如果隊列的平均長度qa小于minth，那么該數(shù)據(jù)包將被提交至隊列。否則，當隊列平均長度大于maxth則該數(shù)據(jù)包將被丟棄。如果qa介于minth和maxth之間，則對qa進行線性函數(shù)概率計算，隨機丟棄該數(shù)據(jù)包。但是，隊列的長度并不能有效的反映出網(wǎng)絡擁塞的真實狀況。發(fā)送過多的擁塞通知包會導致多余的數(shù)據(jù)包丟失，而過少則無法有效的組織擁塞形成。

在RED算法當中，當數(shù)據(jù)負載變化時容易發(fā)生惡性的隊列振蕩。結果，RED算法通過各種方法被進一步拓展和改進。近年來，國內外關于提高RED算法的穩(wěn)定性和魯棒性的研究主要集中在設計自適應地控制參數(shù)調整策略和采用其他更能反映網(wǎng)絡擁塞的丟棄概率函數(shù)兩個方面。這方面的改進算法有基于網(wǎng)絡流量變化的Adaptive RED[5]、根據(jù)比例微分控制器原理的PD-RED[6-7]。除了以上兩方面的研究，關于RED算法的研究還涉及到其他方面。比如，CHOKe算法最大的缺點是隨著網(wǎng)絡中流數(shù)目的增加，每個流在當前隊列緩存中的分組數(shù)也會減少，對非適應流的懲罰力度不夠，不能很好地實現(xiàn)帶寬的公平分配[8]。以及AFD(Approximate Fair Dropping)[9]算法巧妙利用了網(wǎng)絡流量的分布，是少數(shù)的“大”流占據(jù)絕大部分的帶寬，即重尾分布的特性。通過分組采樣記錄的流以較大的概率包含網(wǎng)絡中的“大”流。在網(wǎng)絡發(fā)生擁塞時，對這些“大”的分組實施丟棄，對于沒被記錄的流不丟棄分組。

1 風險均數(shù)算法

所謂的風險均數(shù)算法，就是在給定某個單元直到時間t無效的情況下，在時間t發(fā)生失效的條件密度函數(shù)。所以，用X表示隨機變量，用x表示自變量。

式(1)表明，指定一個風險算法可以完全確定累積分布函數(shù)，反之亦然。

威布爾分布的風險均數(shù)的計算公式為：

對于式(2)，當β=1時，威布爾風險均數(shù)是個常量。因為當β=1時，威布爾分布將為常值。當β＞1時，威布爾風險均數(shù)將從β開始增大并趨于無窮大。因此，對于那些由于負載過重或任務過量造成性能嚴重退化的系統(tǒng)或部件而言，威布爾風險均數(shù)是最合理的選擇。當β＜1時，威布爾風險均數(shù)將由β開始減小并趨于0。

相比之下，伽馬分布的風險均數(shù)也有γ和λ-兩個參數(shù)。同樣地，當γ=1時，風險均數(shù)將為常值。當γ＞1時，風險均數(shù)將遞增且當γ＜1時風險均數(shù)將遞減。但是，當γ＜1時，風險均數(shù)從小增大并趨近于λ，且當γ＜1時從大到小趨近于λ。所以，即使伽馬分布曲線與威布爾分布曲線看起來非常相似，并且兩種方法都能產(chǎn)生符合要求的數(shù)據(jù)樣本。但是他們在定義有效數(shù)據(jù)或可信數(shù)據(jù)方面有不同的特點。

最終，把威布爾分布函數(shù)的風險均數(shù)算法簡化為 h（x）=cac-1，見圖1。

圖1 威布爾分布的風險均數(shù)函數(shù)

2 HERED算法

與目前大多數(shù)改進的RED算法不同的是，本文提出的改進思路將RED算法中的棄包策略更換為風險評估算法，其余部分依然保持原有的RED策略不變，將這種策略稱之為HERED。也就是說，利用這種非線性包丟棄方法，能夠根據(jù)數(shù)據(jù)負荷的實際情況，在負載較輕時減少棄包，在負載較重時加速棄包，從而有效提高傳輸效率和算法性能。所以，當負載較輕時，HERED能夠動態(tài)的調整操作隊列長度。當負載很重或隊列平均長度接近最大閾值maxth時，隊列長度指示器會很快失去控制，HERED算法允許快速將大量的數(shù)據(jù)包快速丟棄。通過仿真可以證明，HERED算法能夠達到比RED算法更高更穩(wěn)定的吞吐率。因為HERED能夠完全兼容RED算法，可以很容易將RED算法升級或更新至HERED算法。

對RED算法進行了一些大的改變，并且稱之為HERED算法。HERED算法的一個最重要的優(yōu)勢是，它通過使用風險均數(shù)函數(shù)來改變棄包概率值。在這里，用T和qlen分別來標記目標值和隊列長度。為了在高擁塞水平下穩(wěn)定隊列長度，設置風險均數(shù)函數(shù)中的c=3，c=2，再c=3來分別對應 minth

對每一個到達的數(shù)據(jù)包

用風險均數(shù)函數(shù)

h(x)=cxc-1

計算新的棄包概率p：

如果qlen

c=0

不丟棄

或者，如果 minth≤qlen＜T

c=3

計算Pa概率：

對于Pa概率：

或者，如果 T≤qlen＜maxth

c=2

計算Pa概率：

對于Pa概率：

標記到達的數(shù)據(jù)包

或者，如果 maxth≤qlen＜2*maxth

c=3

計算Pa概率：

對于Pa概率：

標記到達的數(shù)據(jù)包

或者，如果 qlen≥2*maxth

標記到達的數(shù)據(jù)包

3 仿真結果

將HERED算法與現(xiàn)有的隊列管理策略REM和RED進行仿真結果比較。

所有的仿真結果均使用NS-2模擬器來實現(xiàn)。在所有仿真中，使用圖2所示的網(wǎng)絡拓撲結構，該拓撲結構包括N個發(fā)送方和一個sink節(jié)點，通過路由器N連接在一起，然后采用某種隊列管理算法。Sn代表TCP流的源。通過改變每個源Sn的數(shù)據(jù)流數(shù)目來產(chǎn)生不同級別的負載輕重，從而仿真瓶頸鏈路的不同級別的網(wǎng)絡擁塞。其中，N具有50個數(shù)據(jù)包長度的緩沖區(qū)隊列。

仿真使用的參數(shù)見表1。

表1 仿真參數(shù)

在這些仿真中，從所有（S1，S2）中的節(jié)點到目的節(jié)點d1,d2，有10到200個TCP源運行了100 s。圖3說明了RED、REM和HERED算法的數(shù)據(jù)表丟失率。很明顯，HERED算法丟失的數(shù)據(jù)包最少。

圖2 仿真拓撲結構

圖3 RED、REM和HERED算法的丟包率

4 結論

針對RED中使用的風險率評估包丟棄方法，分析不同復雜算法的主動隊列管理策略，進而根據(jù)負載情況動態(tài)調整棄包策略，在輕負載時減緩棄包，在重負載情況下加速棄包，由此給出一種基于威布爾分布失效函數(shù)的主動隊列管理算法，仿真結果表明，所給算法具有較低的數(shù)據(jù)包丟棄率，性能優(yōu)于已有的主動隊列管理算法。

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

[2]Fan X,Zhang J,Guan L.QBLUE:A New Congestion Control Algorithm based on Queuing Theory,HPCC-2012,25-27 June,2012:1253-1257.

[3]Zhang J,Fan X.An Improvement Algorithm of AQM to Reduce the Packet Loss Rate,2012 Third International Conference on E-Business,11-13 May,Shanghai,China,2012:3294-3297.

[4]Fan X,Wang J,Guan L.Heuristic Active Queue Management with Hazard Rate Function,ICNC'11-FSKD'11,26-28 July,Shanghai,China,2011:281-2285.

[5]Floyd S,Gummadi R,Shenker S.Adaptive RED:An Algorithm for Increasing the Robustness of RED's Active Queue Management[R].Berkeley,CA,2001.

[6]Sun J,Ko K,Chen G,et al.PD-RED:to improve the performance of RED[J].IEEE Communication Letters,2003,7(8):406-408.

[7]魏 濤,張順頤.一種模糊自調整的PD-RED算法[J].計算機工程與應用,2007,43(5):124-126.

[8]高文宇,王建新，陳松喬．PFED:一種基于預測的公平的主動隊列管理算法[J].計算機研究與發(fā)展,2006,43(2)：204-210．

[9]鄒雪蘭,劉偉彥,孫雁飛.一種基于速率的公平隊列管理算法[J].計算機工程,2009,35(6):29-31,34．