帶有進出優(yōu)先級的RED改進算法

朱國暉

(西安郵電學(xué)院通信工程系, 陜西 西安 710061)

0 前 言

緩沖管理是對網(wǎng)絡(luò)傳輸節(jié)點中隊列緩沖資源的管理.在分組傳輸過程中，其流經(jīng)的網(wǎng)絡(luò)傳輸節(jié)點通常采用隊列緩存、延遲轉(zhuǎn)發(fā)的服務(wù)方式提高輸出鏈路的帶寬利用率.緩沖管理機制在分組到達隊列前端時依據(jù)一定的策略和信息決定是否允許該分組進入緩沖隊列.從另一個角度看，也就是做出是否丟棄帶分組的決策，因此也成為丟棄控制.緩沖管理在網(wǎng)絡(luò)傳輸控制中發(fā)揮著相當(dāng)大的作用，是網(wǎng)絡(luò)服務(wù)質(zhì)量(QoS)控制的核心技術(shù)之一，也是實現(xiàn)網(wǎng)絡(luò)擁塞控制的重要手段.

1 緩沖管理

1.1 緩沖管理的意義

就單個網(wǎng)絡(luò)傳輸節(jié)點而言，其控制目標(biāo)在于解決輸出鏈路的帶寬資源分配問題，把有限的資源公平而有效的分配給不同的服務(wù)類別(或用戶流等).而在眾多網(wǎng)絡(luò)傳輸節(jié)點構(gòu)成傳輸網(wǎng)的基礎(chǔ)上，網(wǎng)絡(luò)傳輸控制需要整合、規(guī)劃所有的網(wǎng)絡(luò)帶寬資源的使用，為用戶提供端到端的有服務(wù)質(zhì)量保障的網(wǎng)絡(luò)傳輸服務(wù)，這也就是QoS控制的目標(biāo).

帶寬資源的分配在網(wǎng)絡(luò)傳輸節(jié)點上主要是通過基于多個隊列的分組調(diào)度來實現(xiàn).雖然緩沖管理機制直接涉及到的是節(jié)點中的隊列緩沖資源，直接影響到的也只是分組丟失率性能，然而其對系統(tǒng)帶寬分配的性能有著不可忽視的影響：合理的系統(tǒng)隊列緩沖容量，對于平衡系統(tǒng)吞吐量和分組排隊延遲起著至關(guān)重要的作用；在多隊列情況下，緩沖資源在不同隊列之間的分配只有在與輸出帶寬的分配相互一致時才能獲得最佳的緩沖效果.

最早的擁塞控制機制出現(xiàn)在TCP協(xié)議中，并采用慢啟動和擁塞避免算法來調(diào)整自己的數(shù)據(jù)發(fā)送速率，緩解傳輸網(wǎng)絡(luò)的壓力.隨著顯示擁塞通告(ENC)和主動隊列管理(AQM)的思想的提出，擁塞控制不再只是網(wǎng)絡(luò)用戶的責(zé)任，在網(wǎng)絡(luò)的傳輸節(jié)點中也引入了擁塞控制的機制.如何有效配合網(wǎng)絡(luò)用戶采用的協(xié)議，盡量避免擁塞的出現(xiàn)；如何區(qū)分出不遵守擁塞控制范圍的用戶，并限制其不至于影響其它用戶和整個網(wǎng)絡(luò)的有效運行等，都成為網(wǎng)絡(luò)傳輸節(jié)點中的對列緩沖管理機制需要解決的關(guān)鍵問題.

1.2 緩沖管理的目標(biāo)

網(wǎng)絡(luò)傳輸控制中通常采用的隊列結(jié)構(gòu)模型是為了提高輸出鏈路的帶寬利用率而設(shè)置的.在沒有排隊的情況下，到達的分組或者被丟棄，或者立刻獲得服務(wù)，分組排隊延遲可以降到最低，然而這是以低系統(tǒng)吞吐量和高分組丟失率為代價的，當(dāng)大量的分組到達時將因為服務(wù)器忙而被丟棄，而在鏈路空閑時服務(wù)器又將因為沒有服務(wù)對象而閑置，造成系統(tǒng)資源的極大浪費.

隊列緩沖的設(shè)置使鏈路的帶寬利用率和系統(tǒng)的吞吐量得以改善，然而同時也增大了分組排隊的延遲，在對列緩沖空間的容量增大時情況尤為嚴重.隨著網(wǎng)絡(luò)時事應(yīng)用的發(fā)展，用戶對數(shù)據(jù)的傳輸延遲的要求越發(fā)苛刻，要求網(wǎng)絡(luò)傳輸業(yè)務(wù)能夠提供盡可能低的、穩(wěn)定的傳輸延遲.而分組在網(wǎng)絡(luò)中傳輸遭遇的延遲的最主要部分，也是最容易控制的部分，就來源于網(wǎng)絡(luò)傳輸節(jié)點的排隊延遲.因此，如何設(shè)置合適地隊列緩存空間容量，如何在網(wǎng)絡(luò)運行期間合理的控制隊列長度的動態(tài)變化，以平衡系統(tǒng)吞吐量和分組排隊延遲之間的矛盾，是緩沖管理乃至整個網(wǎng)絡(luò)QoS控制需要解決的重要問題[1].

2 緩沖管理的典型算法

2.1 RED及其衍生算法

(1)RED算法.把擁塞控制引入到網(wǎng)絡(luò)傳輸節(jié)點的控制機制中，提高網(wǎng)絡(luò)資源的利用率成為重點關(guān)注問題，F(xiàn)loyd和Jacobson正是由此而提出了影響相當(dāng)廣泛的隨機早期檢測(random early detection，RED)算法[3].RED算法基于平均隊列長度預(yù)測可能到來的網(wǎng)絡(luò)擁塞，同時由于RED算法隨機標(biāo)記到達的數(shù)據(jù)分組，使不同的TCP流的擁塞相應(yīng)異步化，因而解決了TCP流的全局同步問題.

RED算法存在的問題有：(a)對控制參數(shù)過于敏感，難以優(yōu)化參數(shù)設(shè)定.算法的性能對控制參數(shù)和網(wǎng)絡(luò)流量負載的變化非常敏感.在用戶流增大的情況下，RED算法的性能會急劇下降.(b)不支持服務(wù)區(qū)分，基于best-effort服務(wù)模型，沒有考慮不同等級服務(wù)之間、不同用戶之間的差別，無法提供有效的公平性保障.

(2)自適應(yīng)RED算法.RED算法通過有效地控制系統(tǒng)的平均隊列長度，可以同時獲得較高的系統(tǒng)吞吐量性能和較低的分組排隊延遲.然而在RED算法中，平均隊列長度受網(wǎng)絡(luò)擁塞程度和控制參數(shù)的設(shè)置的影響非常大，如果網(wǎng)絡(luò)負載較輕，或者最大標(biāo)記概率參數(shù)maxp設(shè)置的較大，則平均隊列長度將會趨于最小閾值minth；而如果網(wǎng)路負載較重或者maxp值設(shè)置的較大，則會導(dǎo)致平均隊列長度趨于甚至超過最大閾值maxth.這就破壞了平均隊列長度的穩(wěn)定性，進而使得系統(tǒng)派對造成的延遲無法預(yù)先估測，同時也降低了系統(tǒng)的有效吞吐量.

出于提高RED算法性能穩(wěn)定性的考慮，文獻[6,7]提出并改進了一種自適應(yīng)調(diào)整控制參數(shù)的自適應(yīng)RED(adaptive-RED)算法.自適應(yīng)RED算法的思路非常簡單.為了控制平均隊列長度穩(wěn)定地保持在最小、最大閾值之間，當(dāng)網(wǎng)絡(luò)擁塞程度較大時，相應(yīng)的增大標(biāo)記概率maxp，而當(dāng)網(wǎng)絡(luò)擁塞程度較小時，則減小標(biāo)記概率的數(shù)值，以達到保持平均隊列長度穩(wěn)定的目的.文獻[6]提出的改進算法如公式(1)所示：

每次分組到達到時，

(1)

在此基礎(chǔ)上，文獻[5]更嚴格地限定了平均隊列長度的允許變化范圍和標(biāo)記概率參數(shù)的調(diào)整范圍，同時把標(biāo)記概率參數(shù)的調(diào)整算法由乘法增大乘法減小(MIMD)改為加法增大乘法減小(AIMD).

自適應(yīng)RED算法把RED算法的控制參數(shù)動態(tài)化，提高了RED算法的魯棒性，使之更能適應(yīng)網(wǎng)絡(luò)流量的變化，獲得更加穩(wěn)定的性能.然而另外一方面，自適應(yīng)算法也增加了處理的復(fù)雜度，同時引入的調(diào)整參數(shù)的設(shè)置也是在實現(xiàn)中需要考慮的問題.

3 帶有進出優(yōu)先級的RED改進算法

3.1 新算法的描述

在RED算法的基礎(chǔ)之上，當(dāng)多隊列需要進入路由器時，對到達的分組在進入隊列與離開隊列時的次序進行調(diào)度，采用優(yōu)先級的方法對隊列進行選擇，讓最新到達的分組總是進入優(yōu)先級最高的分組，從而降低分組丟失率.將此算法稱為進出優(yōu)先級的RED改進算法.

3.2 具體實現(xiàn)步驟

算法的具體流程如下：

Set1：假設(shè)路由器在其緩沖池中有3個隊列q1，q2，q3，在分組到來之前假設(shè)：

(1)隊列的入優(yōu)先級分別是p1in，p2in，p3in，并且假設(shè)其優(yōu)先級的高低順序為p1in

(2)隊列的出優(yōu)先級分別是p1out，p2out，p3out,并且假設(shè)其優(yōu)先級的高低順序為p1out

(3)3個隊列的平均隊列長度分別為avg1，avg2，avg3.

Set2：每當(dāng)分組進入路由器時，平均隊列越長則該隊列在這一時刻包含分組數(shù)目越多，在入隊列處的優(yōu)先級按照公式(2)進行計算，其含義是分組入對列時的優(yōu)先級與平均隊列長度成反比，即平均隊列越短其優(yōu)先級越高，設(shè)一常數(shù)K

Piin=K/avgii=1, 2, 3，…，n

(2)

當(dāng)每次有新的分組到達隊列時，我們都重新對p1in，p2in，p3in進行排序，再按照排序出來的結(jié)果，我們總是把新到來的分組放在優(yōu)先級最高的隊列中，這樣就可保證總是把分組放入平均隊長最短的隊列中.

Set3：對于出隊列的優(yōu)先級可按照公式(3)進行計算，其含義是分組在出隊列時的優(yōu)先級與平均隊列長度成正比，即平均隊列越長則優(yōu)先級越高，設(shè)一常數(shù)F

Piout=Favgii=1, 2, 3，…，n

(3)

每當(dāng)有分組要出隊列時，重新對p1out，pout，p3out進行排序，按照從高優(yōu)先級到低優(yōu)先級順序讀出數(shù)據(jù)，這樣我們就可以保證總是讓平均隊列長度最長的分組優(yōu)先傳送出去.

Set4： 我們假設(shè)公式(2)所示的緩沖池為一個先到先服務(wù)的隊列管理系統(tǒng)，且緩沖池的容量有限，假設(shè)其總?cè)萘繛锽，服務(wù)的速度設(shè)為c，容量B和服務(wù)速度c都為固定的常數(shù). 在時刻t，qi表示在時間 (t-1，t)結(jié)束時業(yè)務(wù)源i的隊列長度，yi表示在時間(t，t+1)開始時的所到的新分組數(shù)，則緩沖池中第i類業(yè)務(wù)源的隊列長度的關(guān)系式為：

(4)

那么在每一個隊列中，所有的業(yè)務(wù)源所占據(jù)的隊列長度應(yīng)該表示為

(5)

即為分組的瞬時隊列長度.

Set5：在RED算法中，現(xiàn)在用分組的瞬時隊列長度來表示平均隊列長度avg，

當(dāng)q=0 時avg=(1-wq)×avg

當(dāng)q≠0時avg=(1-wq)×avg+wq×q

(6)

分組的丟棄概率pb按照下面的式子進行計算：

(7)

Set6：此時再按照自適應(yīng)RED算法自動調(diào)整maxp：

(8)

根據(jù)以上的算法，每當(dāng)平均隊列長度avg超過maxth時，則增加maxp;而當(dāng)平均隊列長度avg低于minth時則要減少maxp的大小，這樣可以保持平均對列長度在一個合理地范圍內(nèi)不至于有溢出或者空閑，更加合理地利用緩沖空間.

3.3 算法小結(jié)

與傳統(tǒng)RED算法以及自適應(yīng)ARED算法的比較： 傳統(tǒng)RED算法的丟包概率P不僅和平均對列avg有關(guān)，而且還和從上一次丟包開始到現(xiàn)在連續(xù)進入隊列的包的數(shù)量count有關(guān).隨著count的增加，下一個包被丟棄的可能性也在緩慢增加.這主要是為了在到來的包之間均勻間隔地丟包，避免連續(xù)丟包，以消除對突發(fā)流的偏見和產(chǎn)生全局同步現(xiàn)象.

自適應(yīng)ARED算法提出了一種自動配置機制，根據(jù)流量的變化來配置參數(shù)maxp.ARED的基本思想就是通過檢查平均隊長的變化來決定RED是應(yīng)更激進還是更保守，從而盡量保持平均隊長在minth和maxth之間.具體地說，如果平均隊長是在minth附近振蕩，說明擁塞控制太激進了，那么就減小maxp，maxp=maxp/α；如果在maxth附近振蕩，說明擁塞控制太保守了，那么就增大maxp，maxp=maxp*β,其中β>α>1.ARED是對RED改動很小的一種算法，它保留了RED的基本結(jié)構(gòu)，只需調(diào)節(jié)參數(shù)maxp，從而保持平均隊長在minth和maxth之間，消除了RED的隊列延時問題和參數(shù)敏感性問題.

4 結(jié)束語

本文提出的帶有進出優(yōu)先級的RED改進算法也是對傳統(tǒng)RED算法的一種改進算法，其首先考慮了進出對列的分組對于平均隊列長度的影響并且設(shè)定了優(yōu)先級，降低了分組丟失率，能夠適應(yīng)網(wǎng)絡(luò)的各種負載的變化，并適時調(diào)整各參數(shù)的變化，減少了在擁塞發(fā)生時不必要的丟失數(shù)據(jù)，優(yōu)化了網(wǎng)絡(luò)的進程，提高了系統(tǒng)的利用率，從而提高了整個系統(tǒng)的吞吐量.此算法不僅考慮分組到達時對平均隊列長度的影響，還考慮分組的離去對平均隊列長度的影響，maxp可以隨網(wǎng)絡(luò)負載的變化而動態(tài)的變化，因此該算法能更準確反映網(wǎng)絡(luò)的擁塞程度.

參考文獻

[1] Altintas O. Uregncy-based round robin:a new scheduling discipline for packet switching networks[J]. IEEE Globecom，1997,2(1):1 119-1 183.

[2] Goyal P , Vin H M，Cheng H .Start-time fair queueing:a scheduling algorithm for integrated services packet switched networks[J]. IEEE Trans on Networking,1997,5:690-740.

[3] Parekh A K，Gallager R G. A generalized processor sharing approach to flow in integrated services: the sing-node case[J]. IEEE/ACM Trans Network,1993,1(3):344-357.

[4] Jacobson V. Cngestion avoidance and coutrol[J]. ACM Computer Communications Review,1998,18(4):314-329.

[5] Armitage G, 隆克平等譯.IP網(wǎng)路服務(wù)質(zhì)量[M].北京：機械工業(yè)出版社，2001.

[6] Zhang H, Ferrari D. Rate-controlled service disciplines[J].Journal of High Speed Networks,1995,3(4): 389-412.

[7] Feng W, Kandlur D, Saha D,etal. A self configuring RED gateway[J]. IEEE INFOCOM,1999,(3):1 320-1 328.

[8] Floyd S, Gummadi R, Shenker S .Adaptive RED: an algorithm for increasing the robustness of RED′s active queue management[Z], 2001.

[9] 王重鋼，隆克平.分組交換網(wǎng)絡(luò)中隊列調(diào)度算法的研究及展望[J].電子學(xué)報，2001,29(4):553-559.

[10] 王宏宇，顧冠群.集成服務(wù)網(wǎng)絡(luò)中的分組調(diào)度算法的研究綜述[J].計算機學(xué)報，1999,22(10):37-42.

[11] Shreedhar M ,Varghese G. Efficient fair queueing using deficit round-robin[J]. EEE Transactions on Networking, 1996,4(3): 375-385.

[12] Ott T J, Lakshman T V, Wong L H. SRED: stabilized RED[J].: IEEE INFOCOM, 1999,(3):1 346-1 355.