朱國暉

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

0 前 言

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

1 緩沖管理

1.1 緩沖管理的意義

就單個網(wǎng)絡(luò)傳輸節(jié)點(diǎn)而言，其控制目標(biāo)在于解決輸出鏈路的帶寬資源分配問題，把有限的資源公平而有效的分配給不同的服務(wù)類別(或用戶流等).而在眾多網(wǎng)絡(luò)傳輸節(jié)點(diǎn)構(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ǎn)上主要是通過基于多個隊(duì)列的分組調(diào)度來實(shí)現(xiàn).雖然緩沖管理機(jī)制直接涉及到的是節(jié)點(diǎn)中的隊(duì)列緩沖資源，直接影響到的也只是分組丟失率性能，然而其對系統(tǒng)帶寬分配的性能有著不可忽視的影響：合理的系統(tǒng)隊(duì)列緩沖容量，對于平衡系統(tǒng)吞吐量和分組排隊(duì)延遲起著至關(guān)重要的作用；在多隊(duì)列情況下，緩沖資源在不同隊(duì)列之間的分配只有在與輸出帶寬的分配相互一致時才能獲得最佳的緩沖效果.

最早的擁塞控制機(jī)制出現(xiàn)在TCP協(xié)議中，并采用慢啟動和擁塞避免算法來調(diào)整自己的數(shù)據(jù)發(fā)送速率，緩解傳輸網(wǎng)絡(luò)的壓力.隨著顯示擁塞通告(ENC)和主動隊(duì)列管理(AQM)的思想的提出，擁塞控制不再只是網(wǎng)絡(luò)用戶的責(zé)任，在網(wǎng)絡(luò)的傳輸節(jié)點(diǎn)中也引入了擁塞控制的機(jī)制.如何有效配合網(wǎng)絡(luò)用戶采用的協(xié)議，盡量避免擁塞的出現(xiàn)；如何區(qū)分出不遵守?fù)砣刂品秶挠脩簦⑾拗破洳恢劣谟绊懫渌脩艉驼麄€網(wǎng)絡(luò)的有效運(yùn)行等，都成為網(wǎng)絡(luò)傳輸節(jié)點(diǎn)中的對列緩沖管理機(jī)制需要解決的關(guān)鍵問題.

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

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

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

2 緩沖管理的典型算法

2.1 RED及其衍生算法

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

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

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

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

每次分組到達(dá)到時，

(1)

在此基礎(chǔ)上，文獻(xiàn)[5]更嚴(yán)格地限定了平均隊(duì)列長度的允許變化范圍和標(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è)置也是在實(shí)現(xiàn)中需要考慮的問題.

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

3.1 新算法的描述

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

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

算法的具體流程如下：

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

(1)隊(duì)列的入優(yōu)先級分別是p1in，p2in，p3in，并且假設(shè)其優(yōu)先級的高低順序?yàn)閜1in

(2)隊(duì)列的出優(yōu)先級分別是p1out，p2out，p3out,并且假設(shè)其優(yōu)先級的高低順序?yàn)閜1out

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

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

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

(2)

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

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

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

(3)

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

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

(4)

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

(5)

即為分組的瞬時隊(duì)列長度.

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

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

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

(6)

分組的丟棄概率pb按照下面的式子進(jìn)行計(jì)算：

(7)

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

(8)

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

3.3 算法小結(jié)

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

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

4 結(jié)束語

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

參考文獻(xiàn)

[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].北京：機(jī)械工業(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ò)中隊(duì)列調(diào)度算法的研究及展望[J].電子學(xué)報(bào)，2001,29(4):553-559.

[10] 王宏宇，顧冠群.集成服務(wù)網(wǎng)絡(luò)中的分組調(diào)度算法的研究綜述[J].計(jì)算機(jī)學(xué)報(bào)，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.