PbRED：基于優先級的RED改進算法*

江 明，劉 鋒

(1.北京航空航天大學電子信息工程學院，北京 100191;2.國家空管新航行系統技術重點實驗室，北京 100191)

1 引言

隨著互聯網規模的不斷增大，互聯網上的用戶和應用也都在快速增長，擁塞問題已經成為影響TCP傳輸性能的重大問題，對網絡服務質量QoS(Quality of Service)提出了更高的要求。隊列管理機制作為TCP/IP的擁塞控制手段，近年來得到研究者們的高度重視，在減輕擁塞、提升吞吐量方面起到了重要的作用[1～3]。

主動式隊列管理AQM(Active Queue Management)是基于FIFO調度策略的隊列管理機制[4]，能夠讓路由器主動決定在什么時候丟多少包，以實現擁塞控制。AQM能減少丟棄包的數量，提供更優秀的服務性能。AQM算法中最為著名的是隨機早期檢測RED(Random Early Detection)[5]。RED能夠有效控制隊列長度，可以更好地支持實時應用；能夠最少化全局同步的發生，使帶寬利用率不致降低。然而，RED沒有考慮業務流的優先級，不能支持服務質量區分，且對參數的敏感度較高。繼RED算法之后，研究人員又提出了BLUE[6]、GREEN[7]等算法和SRED[8]、ARED[9]、PRED[10]等RED改進版本。但是，這些算法和改進版本都沒有考慮優先級的問題。

在先前將RED應用于存在優先級的場景的研究中，研究者們提出的技術路線大致分為兩類。一類是將路由器緩存隊列拆分成多個具有不同優先級的虛擬隊列，對每個虛擬隊列賦予優先級。文獻[11]提出了隊列實時優先級的概念，將緩存隊列分成多個具有不同實時優先級的隊列，每當分組到達時按照擁塞程度計算各個隊列的實時優先級，并將分組存入優先級最高的隊列中；文獻[12]按照分組優先級的不同分成多個虛擬子隊列，并使用狀態方程計算隊列長度和丟棄概率；文獻[13]提出的算法思想與文獻[11]類似，但在計算丟棄概率時使用ARED算法來更新最大丟棄概率。這類算法需要維持多個虛擬隊列，會增加分組亂序的問題，從而導致TCP性能降低或者增加延遲抖動。

另一類則是將到來的分組按業務流的不同賦予優先級。最典型的是RIO算法及其改進算法RIO-C[14]。RIO在一個隊列中管理in分組和out分組而不需要維持兩個隊列；RIO-C在RIO的基礎上將丟棄優先級擴展為三類，然而會對高丟棄優先級的分組過量丟棄；文獻[15]提出PFRIO算法，為每類丟棄優先級設置一組參數并分別計算平均隊列長度和丟棄概率，但各優先級丟棄概率的差異仍然較大；文獻[16]的基本思想與文獻[11]類似，而使用IPv6包頭的流標簽域來標記優先級包和非優先級包。這類算法大多關注各優先級之間的丟包率比較和平均隊列長度，對吞吐量等性能沒有提升。在計算丟棄概率時往往使高丟棄優先級分組的丟棄概率急劇增加，有失公平性[14～17]。同時，還要維持多組參數，不僅需要消耗較多存儲資源，具有相當的計算復雜度，而且依然存在對參數敏感度的問題，由于參數眾多，參數敏感性問題甚至比RED更甚。

近年來，研究者們仍然對有優先級的RED有較高的關注，相關研究仍在繼續。文獻[18,19]針對AQM與VoIP相容的問題，提出了新的架構BOUDICCA，用基于AF-PHB和WRED配置的方法來降低成本并劃分優先級。BOUDICCA對VoIP網絡針對性較強，結合使用了OSPF路由選擇與RED的擁塞控制。它是幾種不同領域的算法結合起來的整體架構，并沒有對RED算法本身進行有效的改進，只是通過設置不同的Pmax來調整“金、銀、銅”三種不同優先級的丟棄概率，以保證“金”數據流的高QoS。文獻[20]提出DF-RED算法，用優先級來保護適應流。當適應流與非適應流同時存在且非適應流大量攫取資源時，DF-RED增大非適應流的丟棄概率，從而起到保護適應流的作用。DF-RED的優先級是在網絡運行中動態確定的，因此其計算成本較高，而且從仿真結果看，其隊列長度變化比RED更劇烈。文獻[21]提出的算法使用反饋的方式，把擁塞檢測信號通知給tcp流，能更快地探知到早期擁塞。其只在入口節點對分組進行優先級的劃分，對適應流和非適應流的性能保障有明顯區分度，但同種流之間則無明顯區分。

本文提出一種新的RED改進機制—基于優先級的RED PbRED(Priority based RED)，針對RED沒有考慮到業務流存在優先級從而無法區分服務質量的情況，對業務流賦予優先級，使用優先級信息調整丟棄概率，優先級越高，丟棄概率越小，反之亦然。不同于現有的算法，PbRED可以通過調節可調參數，自由調整不同優先級業務流的丟棄概率，從而使不同優先級服務質量的線性區分度具有可控性，保證高優先級業務流獲得更好的吞吐量性能，并且提高tcp流對cbr流的競爭力。在得到較好性能的同時，幾乎不會損失公平性。

2 隨機早期檢測算法RED

RED的基本思想是通過監控路由器輸出端口隊列的平均長度來探測擁塞，一旦發現擁塞逼近，就隨機地選擇連接來通知擁塞，使它們在隊列溢出導致丟包之前減小發送窗口，降低發送數據的速率，從而緩解網絡擁塞。每當有分組到達時，RED算法首先計算此時的平均隊列長度Lave，并將之與隊列長度最小門限THmin和最大門限THmax比較。若LaveTHmax，則丟棄這個分組；若THmin

RED算法能夠準確地辨別擁塞，有效緩解全局同步現象，提高網絡資源的利用率；能夠有效地將平均隊列長度控制在較低的長度，緩解早期擁塞現象；同時，RED算法的控制原理簡單，計算復雜度低，實現簡便。

RED算法沒有考慮到不同業務流存在不同優先級的情況，因而不能較好地區分服務。在實際應用中，很多時候希望不同的業務流得到不同的服務質量。當帶寬資源有限時，應當優先保證實時性業務的服務質量，例如視頻流、音頻流和文本流同時存在時，我們希望視頻流能夠得到高于其他兩個流的服務質量，而音頻流的服務質量又應當高于文本流。又如付費用戶的業務流理應比非付費用戶的業務流得到更好的服務。

另外，RED雖然能夠在ftp流之間較為公平地分配帶寬，但當ftp流和非ftp流(例如cbr流)同時存在時，RED就不能有效地保護ftp流。因為RED本質上還是通過丟棄數據包來通知ftp源減小發送窗口來控制擁塞，而cbr流沒有擁塞控制機制，不會由于丟包而降低發送速率。因此，當發生擁塞時，cbr流能夠比ftp攫取到更多的網絡帶寬，這是我們不希望看到的。

3 PbRED算法

3.1 PbRED改進算法的基本思想

在RED計算丟棄概率Pdrop時，對所有的業務流的計算都是相同的，在所有的流之間隨機挑選要丟棄的分組。這樣的做法對不同優先級的業務流沒有區分度，高優先級的業務流與低優先級的業務流得到的服務質量是大致相同的。

本文提出的PbRED算法，使用優先級信息來計算丟棄概率Pdrop，使高優先級業務流的Pdrop減小，低優先級業務流的Pdrop增大，進而使高優先級業務流獲得相對較多的資源。同時，由于cbr流的優先級最低，能夠通過大量丟棄cbr流的包，把cbr流攫取的帶寬提供給tcp流，從而提高tcp流對cbr流的競爭力，保護tcp流。

3.2 PbRED算法

在實際的應用中，應當根據不同業務流類型、業務流的緊急程度等信息來確定業務流的優先級。而在本文理論分析及仿真實驗中，為簡化起見，直接對每個業務流分配優先級。本文規定，用從1開始的自然數來代表每個業務流的優先級，并用prio_表示優先級這個變量。優先級最高的業務流，其prio_值為1；優先級第二高的業務流，其prio_值為2，以此類推。在本文的分析中，假設網絡中共有n條業務流，且優先級互不相同，優先級最低為n。

在PbRED算法中，丟棄概率Pdrop對所有業務流不再是相同的，而是與每個業務流的優先級相關。優先級越高，丟棄概率越小。新的丟棄概率計算方法為：

Pdrop=Pdrop-old×F(prio_)

(1)

其中，Pdrop-old是改進前的丟棄概率，即RED算法中的丟棄概率。F(prio_)是不同優先級對應的縮減系數，F(prio_)∈[0,1]。F(prio_)的計算方法為：

(2)

其中，n表示優先級的個數；MDfst(即Min-Drop-first)代表優先級為1的縮減系數值，它是所有優先級的縮減系數中的最小值；第n個優先級的縮減系數為2-MDfst。由于所有優先級的縮減系數是線性變化的，這就保證了在正常情況下，所有縮減系數的數學期望是1，即從統計的角度來講，丟棄概率的期望值與RED是相同的。

F(prio_)函數如圖1所示。低優先級業務流的丟棄概率在乘以縮減系數之后有可能增大至超過1，對于超過1的丟棄概率，都以1計算。

Figure 1 F(prio_) function圖1 F(prio_)函數

3.3 PbRED的分析

PbRED算法中的優先級與IP協議中規定的優先級物理意義相同，但為了理論研究和仿真實驗的簡化，使用的是IPv6數據報首部中的“Flow Label(流標號)”域。由于使用已有的域，不必另行增加報頭的開銷，也不會增加計算復雜度。

MDfst是PbRED算法中一個很重要的可調參數，它的取值會影響到PbRED算法的性能。PbRED通過調節參數MDfst來調整不同優先級業務流的丟棄概率。從圖1中能夠看出，MDfst的取值越小，各優先級的縮減系數之間的差值越大。MDfst的兩個極限值分別是0和1。當MDfst=0時，優先級為1的流的分組的Pdrop=0，即不會被丟棄。當MDfst=1時，所有優先級的丟棄概率都是Pdrop-old，即此時就是RED。從這個角度，可以把RED算法看成是PbRED算法的一個特例。MDfst的取值在0.3～0.6時，能夠取得較好的性能，本文中取MDfst=0.5。

PbRED既不必維持多個虛擬隊列，也不需要多組參數，因此不存在分組亂序和參數敏感性的問題。

3.4 PbRED算法細節

由以上對PbRED算法的介紹和分析，最終總結PbRED算法的偽代碼如算法1所述。

算法1PbRED算法

輸入：

p//新近到達的分組;

n//優先級數量;

MDfst//第1優先級的縮減系數。

輸出：

Pdrop//分組p的丟棄概率

/*首先由RED算法進行處理，若此時平均隊長在上下門限之間，則得到RED算法的丟棄概率*/

1：if(Lave>THmin&&Lave

2：{

3： 由RED算法計算丟棄概率Pdrop-old；

4：}

//獲取分組p的優先級信息

5：獲取p→prio_；

//計算p的縮減系數及丟棄概率

6：計算p的縮減系數；//由式(2)

7：計算丟棄概率；//由式(1)

8：if(Pdrop>1)

9：{

10：Pdrop=1；/*針對低優先級丟棄概率可能大于1的情況進行調整*/

11：}

12：返回Pdrop；

PbRED流程圖如圖2所示。

Figure 2 Flow chart of PbRED圖2 PbRED流程圖

4 仿真結果及分析

仿真使用NS2模擬實驗平臺[22～25]對RED和PbRED兩種算法進行了實現和性能評估。仿真采用的性能指標有三項，分別是：

(1)丟包率：在傳輸過程中丟失的數據分組數與信源總共發送的數據分組數的比率。

(2)隊列長度：包括瞬時隊列長度和平均隊列長度，以字節為單位，除以分組大小即得包的個數。

(3)吞吐量：單位時間內信宿接收到的數據量。

4.1 仿真場景

仿真使用的場景是隊列管理實驗典型的單邊啞鈴型結構，如圖3所示。

Figure 3 Simulation script圖3 仿真場景

節點0、1、2、3、4為五個信源，業務流類型分別為四個ftp源和一個cbr源，代號分別為ftp0～ftp3和cbr，優先級依次為1、2、3、4、5。節點5和6之間的鏈路為瓶頸鏈路5-6，其帶寬為0.5 Mb，延時為20 ms。五條信源鏈路0-5、1-5、2-5、3-5、4-5的參數相同，帶寬為2 Mb，延時為10 ms。所有tcp源的發送窗口均為10 000，cbr源的發送速率為0.1 Mb，所有數據源的分組大小均為500。實驗中取MDfst=0.5，RED算法的各參數均為NS2下的默認參數，即THmin=5，THmax=15。仿真時間為1 000 s。

4.2 實驗結果

4.2.1 丟包率

表1為仿真的丟包率的統計結果。從表1中可以看出，由于cbr流不受擁塞控制，在發生擁塞時不會降低發送速率(即兩種算法下，發送包數不變)。RED算法對各業務流的丟棄概率大致相同，但由于cbr流發送速率大于ftp流，故丟包率相對較小，因此能夠攫取到更多資源，其丟包率遠遠小于ftp流。而PbRED算法在區分各優先級的丟包率的同時，能夠大幅提升cbr流的丟包率(因為其優先級最低)，使得ftp流能夠獲得更多資源，從而達到保護ftp流的目的。

Table 1 Statistics of loss rate

根據表1中的丟包率數據，繪制丟包率柱狀圖如圖4所示，圖中每個數據源的左側柱為RED的數據，右側柱為PbRED的數據。從圖4中可以形象地看出，PbRED使得各優先級的丟棄概率呈現出區分度，并且大大提升了cbr流的丟棄概率，從而保護了tcp流。

Figure 4 Statistical histogram of loss rate圖4 丟包率統計柱狀圖

4.2.2 隊列長度

圖5為仿真的隊列長度的統計結果。從圖5中可以看出，雖然瞬時隊列長度變化非常劇烈，但RED算法和PbRED算法都能夠使得平均隊列長度維持在12～13個左右，即PbRED算法不會增加隊列的平均長度。

Figure 5 Statistical chart of queue length圖5 隊列長度統計圖

4.2.3 吞吐量

圖6和圖7為仿真的吞吐量的統計結果。圖6a為總體的吞吐量統計圖，將DropTail、RED和PbRED三種算法進行比較；圖6b是部分放大圖。從圖中可以清楚地看到，RED算法的吞吐量相比于DropTail有一定的提升，而PbRED算法又能夠在RED算法的基礎上進一步較大幅度地提升總體吞吐量。

Figure 6 Statistical chart of total throughput圖6 總體吞吐量圖

圖7為各優先級的吞吐量統計圖，從圖7a中能夠看出，RED算法沒有考慮優先級的影響，故各業務流的吞吐量非常接近，各ftp流的吞吐量沒有區分度，而cbr流的吞吐量也與ftp流相接近。而圖7b中，PbRED能夠合理地區分各優先級的服務質量，各優先級的吞吐量水平呈現顯著差異，高優先級的業務流的吞吐量得到較大提升，ftp0的吞吐量上升幅度最大。同時，cbr流的吞吐量有明顯下降，把一部分帶寬資源讓給了ftp流，從而達到了保護tcp流的目的。

Figure 7 Statistical chart of each priority’s throughput圖7 各優先級吞吐量圖

4.2.4 公平性

為了評估PbRED的公平性能，利用文獻[17]中對算法公平性指標的定義：

(3)

其中,xi表示每個優先級數據源所發送的數據包數量，n表示數據源的數目。公平性指數FI在[0,1]，且FI越大，算法的公平性越好。

根據表1中的發送包數據，由式(3)計算得到RED的公平性指數為0.919 6，而PbRED算法的公平性指數為0.909 6。按照文獻[14～16]的仿真結果，由式(3)計算得到RIO-C、PFRIO和文獻[16]算法的公平性指數分別為0.668 0、0.800 6和0.500 0。比較結果可以看出，文獻[14～16]的三種算法的公平性均有不同程度的犧牲，RED算法的公平性最好，本文的PbRED算法的公平性與RED算法接近。

4.2.5 實驗小結

多次仿真實驗得到的結果與理論分析得出的結論相吻合，表明了PbRED算法的合理性和正確性。當各業務流有不同優先級時，PbRED能夠在略微提升整體吞吐量、有效控制平均隊列長度的前提下，合理區分不同優先級業務流的服務質量，保證高優先級業務流得到更好的服務質量。同時，能夠增大低優先級cbr流的丟包率，降低cbr流的吞吐量，將帶寬資源更多地分配給ftp流，從而提高ftp對cbr流的資源競爭力，有效保護ftp流。

5 結束語

本文提出了一種新的基于優先級的RED改進算法—PbRED，針對RED沒有考慮到業務流優先級、不能區分服務質量的情況進行了改進，使用優先級信息計算丟棄概率，使不同優先級業務流的服務質量存在線性區分度，優先級越高，丟棄概率越小，反之亦然。通過調節可調參數，可以自由調整不同優先級業務流的丟棄概率，從而控制不同優先級服務質量的區分度。在保證高優先級業務流能得到更好的服務質量的同時，提高tcp流對cbr流的競爭力，有效保護tcp流。仿真實驗表明，在保證不降低整體吞吐量、平均隊列長度不變、公平性較好的前提下，PbRED算法能夠合理區分不同優先級業務流的服務質量，并保證高優先級業務流得到更好的吞吐量性能。同時，能夠增大低優先級cbr流的丟包率，降低cbr流的吞吐量，將帶寬資源更多地分配給ftp流，從而提高ftp對cbr流的資源競爭力，有效保護ftp流。

隨著RED算法在網絡中的廣泛應用，研究者們一直在尋求對它進行各個方向的改進。未來的工作將對PbRED的參數進行深入探討，確定各參數的最佳值，如如何取值能夠得到最佳折衷和最優性能、上下門限應如何取值才可以得到最好的性能、是否需要調整其它參數等；同時要考慮如何減少低優先級付出的代價，使得整體的性能進一步優化。這些都是很有價值的研究方向。

[1] Wu Chun-ming,Jiang Ming,Zhu Miao-liang.Research on some active queue management algorithms[J].Chinese Journal of Electronics,2004,32(3):429-434.(in Chinese)

[2] Xu Yan,Wang Zheng-hong.Comparative study of several active queue management algorithms[J].Journal of Jiangsu Polytechnic University,2004,16(4):52-55.(in Chinese)

[3] Xie Xi-ren.Computer networks[M].Beijing:Publishing House of Electronics Industry,2011.(in Chinese)

[4] Braden B，Clark D，Crowcroft J, et al. IETF RFC2309 . Recommendations on queue management and congestion avoidance in the Internet[S].The Internet Society,1998.

[5] FIoyd S,Jacobson V.Random early detection gateway for congestion avoidance[J]. IEEE/ ACM Transactions on Networking，1993,1(4):397-413.

[6] Feng W C，Kandlur D D,Saha D.Blue:A new class of active queue management algorithm[R].Michigan:University of Michigan Technical Reports,1999.

[7] Wydrowski B, Zukerman M. GREEN:An active queue management algorithm for a self managed internet[C]∥Proc of ICC’02, 2002:2368-2372.

[8] Ott T J，Lakshman T V，Wong L. SRED:Stabilized RED[C]∥Proc of IEEE INFOCOM’99，1999:1346-1355.

[9] Floyd S，Gummadi R，Shenker S. Adaptive RED:An algorithm for increasing the robustness of RED’s active queue management[EB/OL].[2013-05-10].http://www.icir.org/floyd/papers.html.

[10] Shi Pei-xin,Lei Zhen-ming.PRED:An active queue management for SPFQ[J].Computer Engineering and Applications,2003,39(26):1-5.(in Chinese)

[11] Zhang Ke-ping,Tian Liao,Li Zeng-zhi.PRED:A new queue management algorithm with priority and self-adaption[J].Chinese Journal of Electronics,2004,32(6):1039-1043.(in Chinese)

[12] Yang Qing-xiang,Li An-fu.Packet priority-based queue management and adaptive packet drop mechanism[J].Electric Power Automation Equipment,2006,26(4):18-20.(in Chinese)

[13] Zhu Guo-hui.An algorithm with priority improved on RED[J].Journal of Shaanxi University of Science&Technology,2010,28(5):146-150.(in Chinese)

[14] Clark D，Wang W J. Explicit allocation of best-effort packet delivery service[J]. IEEE/ACM Transactions on Networking, 1998,6(4):362-373.

[15] Kang Ya-nan,Zhang Cai-yun,Cheng Ru-zhen.Active queue management research for DiffServ model[J].Computer Engineering and Applications,2009,45(5):125-128.(in Chinese)

[16] Zhang Li-li.Research of priority detection RED based on IPv6[D].Jilin:Jilin University,2012.(in Chinese)

[17] Jain R，Chiu D M，Hawe W. A quantitative measure of fairness and discrimination for resource allocation in shared systems[R]. Technical Report TR301. Maynard:Digital Equipment Corp,1984.

[18] Pitts J M, Yang Qiang, Schormans J A. Using AF-PHB BOUDICCA configuration for reliable real-time precedence-based SLAs in degraded IP networks[C]∥Proc of IEEE Military Communication Conference,2007:495-501.

[19] Pitts J M, Wang X, Yang Qiang, et al. Excess-rate queueing theory for M/M/1/RED with application to VoIP QoS[J]. IEEE Electronics Letters, 2006,42(20):1188-1189.

[20] Yu Guan-wei,Xing Wei,Lu Dong-ming.DF-RED:A dynamic fairness based RED algorithm[J].Manufacturing Automation,2010,32(9):7-13.(in Chinese)

[21] Li Xin,Chen Hao,Chen Jian.Scheme research of congestion management in DiffServ networks based on feedback[J].Application Research of Computers,2013,29(8):3088-3090.(in Chinese)

[22] Sanjeev P, Gupta P K, Garg A.Comparative analysis of congestion control algorithms using ns2[J].IJCSI International Journal of Computer Science Issues, 2011,8(1):1-4.

[23] Huang Hua-ji,Feng Sui-li,Qin Li-jiao,et al.NS network simulation and protocol emulation[M].Beijing:Posts&Telecom Press,2010.(in Chinese)

[24] Fang Lu-ping,Liu Shi-hua,Chen Pan,et al.NS-2 network simulation basis and application[M].Beijing:National Defense Industry Press,2008.(in Chinese)

[25] NS2[EB/OL].[2013-05-10].http://www.isi.edu/nsnam/ns/.

附中文參考文獻

[1] 吳春明，姜明，朱淼良.幾種主動式隊列管理算法的比較研究[J].電子學報，2004, 32(3):429-434.

[2] 徐燕，王正洪.幾種主動隊列管理擁塞控制算法的比較研究[J].江蘇工業學院學報，2004, 16(4):52-55.

[3] 謝希仁.計算機網絡[M].北京：電子工業出版社，2011.

[10] 時培昕，雷振明.PRED：一種配合隊列調度的RED算法[J].計算機工程與應用，2003,39(26):1-5.

[11] 張克平，田遼，李增智.PRED：一種具有優先級自適應的隊列管理新算法[J].電子學報，2004,32(6)：1039-1043.

[12] 楊慶祥，李安伏.基于分組優先級的隊列管理與自適應丟包機制[J].電力自動化設備，2006,26(4)：18-20.

[13] 朱國暉.帶有進出優先級的RED改進算法[J].陜西科技大學學報，2010,28(5)：146-150.

[15] 康亞男，張彩云，成汝震.DiffServ模型中主動隊列管理研究[J].計算機工程與應用，2009,45(5)：125-128.

[16] 張黎麗.基于IPv6網絡的優先級檢測RED算法的研究[D].吉林：吉林大學，2012.

[20] 余冠瑋，邢衛，魯東明.DF-RED：一種基于動態公平性的RED算法[J].制造業自動化，2010，32(9)：7-13.

[21] 李昕，陳浩，陳堅.基于反饋的區分服務網絡擁塞管理方案研究[J].計算機應用研究，2012,29(8)：3088-3090.

[23] 黃化吉，馮穗力，秦麗姣，等.NS網絡模擬和協議仿真[M].北京：人民郵電出版社，2010.

[24] 方路平，劉世華，陳盼，等. NS-2網絡模擬基礎與應用[M].北京：國防工業出版社，2008.