基于主動隊列管理算法的研究

摘 要:主要對自適應虛擬隊列(AVQ)算法、動態(tài)閾值(DT)算法以及隊列長度閾值(QLT)分組調度算法等異同點及適用范圍進行了描述，在理論上進行了分析。通過比較各個算法的優(yōu)點及存在的問題，針對AVQ算法進行了改進，使其在原性能的基礎上增加了區(qū)分服務的功能。基本上保持了原算法的優(yōu)點，即具有低時延、低分組丟失率和高鏈路利用率。

關鍵詞:主動隊列管理算法; 自適應虛擬隊列算法; 動態(tài)閾值算法; 隊列長度閾值算法; 改進的AVQ算法

中圖分類號:TN919-34文獻標識碼:A

文章編號:1004-373X(2010)21-0142-03

Research on Active Queue Management Algorithm

ZHANG Qun-liang

(Xi’an University of Post and Telecommunications，Xi’an 710121， China)

Abstract: The differences and application of adaptive virtual queuing (AVQ)， dynamic threshold (DT)， queue length threshold (QLT) and so on are introduced. A new AVQ algorithm which can provide service differentiation for traffics at a network router can be achieved based on the scheme AVQ.

Keywords: active queue management; AVQ algorithm; DT algorithm; QLT algorithm; improved AVQ algorithm

收稿日期:2010-06-09

0 引 言

主動隊列管理(Active Queue Management，AQM)是目前隊列管理的主流技術，也是實現(xiàn)擁塞控制的重要手段之一，長期以來一直受到廣泛的關注?；诓煌碚摰母鞣N主動隊列管理算法隨之涌現(xiàn)，這些隊列管理算法在一定程度上完成了網(wǎng)絡擁塞控制任務，但是也不同程度地在公平性、可擴展性以及算法的復雜度上存在缺陷。

自適應虛擬隊列(Adaptive Virtual Queue，AVQ)算法是一種AQM算法，具有低時延、低分組丟失率和高鏈路利用率等優(yōu)點，但其不能進行區(qū)分服務。借鑒動態(tài)閾值算法(Dynamic Threshold，DT)動態(tài)分配緩沖資源的思想，將原算法在路由器中維持一個虛擬隊列改為維持多個虛擬隊列，從而實現(xiàn)了區(qū)分服務的性能。改進后的AVQ算法必須與一種基于優(yōu)先級的調度算法相結合，理論上它可以與任何一種基于優(yōu)先級的調度算法相結合。

1 自適應虛擬隊列(AVQ)算法

AVQ算法是近年來提出的一種AQM算法，由于具有低時延、低分組丟失率和高鏈路利用率等優(yōu)點而備受關注，但它不能進行區(qū)分服務。在實際操作中，AVQ并不需要對虛擬隊列進行入隊出隊操作，只需要維護虛擬的隊列長度即可，每當新的分組到達時，首先根據(jù):

LVQ=max(LVQ-(t-s)，0)

(1)

刷新虛擬隊列長度，其中，LVQ為虛擬隊列長度;t為當前時間;s為上個分組到達的時間;為虛擬服務速率。如果該分組的加入不會引起虛擬緩沖區(qū)溢出，則:

LVQ=LVQ+b

(2)

進一步更新虛擬隊列的長度，其中，b為到達分組的大小。當每一個分組到達的時候，通過:

=α(γC-λ)

(3)

計算出新的虛擬服務速率。其中，α為衰減因子;γ為期望的鏈路利用率;C為實際服務速率;λ為流量到達的速率。α和γ是 AVQ算法需要設定的兩個參數(shù)，α影響算法的穩(wěn)定性和隊列長度的收斂速率，而選擇不同的γ值可以控制算法對非響應流的魯棒性。

根據(jù)式(3)，分組到達的速率信息被轉換成虛擬服務速率的變化信息，并且進一步轉化為虛擬隊列長度的變化信息，所以AVQ是一種基于流量速率標記方式的AQM算法。這種方式能夠比基于隊列長度的算法(如 RED)更早地發(fā)現(xiàn)網(wǎng)絡擁塞并通知端系統(tǒng)，從而有效地降低時延。不難看出，當分組到達速率超過γC時，虛擬服務速率降低，虛擬隊列長度增大，最后導致虛擬緩沖區(qū)溢出，對到達分組進行標記或丟棄，以通知端系統(tǒng)進行擁塞控制，此時實際緩沖區(qū)仍有部分空閑空間;相反分組到達速率較低時，虛擬服務速率接近實際服務速率C，虛擬緩沖區(qū)不會溢出，從而達到了根據(jù)分組到達速率變化決定其分組丟棄率的目的。

算法的偽代碼如下:

LVQ=max(LVQ-(t-s)，0)

if LVQ+b>B

實際隊列中標記或丟棄分組

else

允許分組進入隊列，LVQ=LVQ+b

endif

=max(min(+α*γ*C(t-s)，C)-α*b，0)

S=t

AVQ算法通過自適應參數(shù)調整來控制輸出鏈路的帶寬利用率，在保證高的系統(tǒng)吞吐量的同時，也可以獲得相當有效的隊列長度控制，進而獲得更短的排隊延遲。

2 動態(tài)閾值(DT)算法

DT算法基于共享存儲器模式的分組交換方式，首先提出了在多個物理端口之間公平分配緩沖資源的方案，如式(4)所示:

T(t)=α(B-Q(t))=α(B-∑iQi(t))

Qi(t)≤T(t)時，允許接收分組

(4)

式中:B為系統(tǒng)緩沖空間的容量;Qi(t)為端口i的隊列長度;Q(t)為當前系統(tǒng)總隊列長度，即為總的緩沖空間占用量;T(t)為控制分組丟棄時采用的閾值參數(shù);α為一調節(jié)因子。從公式可以看出，DT算法根據(jù)系統(tǒng)狀態(tài)動態(tài)調整控制閾值，閾值的大小與當前系統(tǒng)中空閑緩沖資源成正比，當端口占據(jù)的緩沖空間超過控制閾值時，將阻塞該端口，不允許其接收更多的到達分組。

DT算法總是預留一部分緩沖資源，雖然造成了一定的資源浪費，但是對于調整系統(tǒng)的瞬態(tài)性能提供了有效的支持。

為了適應區(qū)分服務的需求，DT算法在物理端口的基礎上，引入了對不同優(yōu)先級的服務支持。DT算法為每個優(yōu)先級設置一個不同的調節(jié)因子αP，算法如式(5)所示:



TP(t)=αP(B-Q(t))=αP(B-∑i∑PQiP(t))

QiP(t)≤TP(t)時，允許接收分組

(5)

式中:

QiP(t)為端口i優(yōu)先級P對應的隊列長度;TP(t)為優(yōu)先級P對應的控制閾值。

DT算法為低優(yōu)先級分組提供了一定的緩沖資源，使其總能獲得一定的服務，而且不同優(yōu)先級之間的緩沖資源比可以通過對α因子的調節(jié)來實現(xiàn)。只要α因子的值滿足一定的條件，就能保證系統(tǒng)性能的穩(wěn)定性。

DT算法通過對動態(tài)控制參數(shù)的調整，能夠在一定程度上適應網(wǎng)絡流量的變化，同時通過預留緩沖資源來保證不同優(yōu)先級服務之間的公平性。DT動態(tài)閾值方案在丟失率性能上優(yōu)于靜態(tài)閾值方案。

3 隊列長度閾值算法(QLT)

QLT(Queue Length Threshold)和PQ(Strict Priority Queue)是基于靜態(tài)優(yōu)先級的兩種常見算法，QLT算法是對PQ算法性能改進的一種算法。

PQ算法給每個隊列賦予不同的優(yōu)先級，每次需要調度時，具有最高優(yōu)先級非空隊列中的分組最先被選擇服務。如果最高優(yōu)先級的隊列為空，則服務具有次高優(yōu)先級的隊列，如此類推。這樣，最重要的分組就能得到最好的服務，比如最小時延。這類算法簡單，容易實現(xiàn)，然而當高優(yōu)先級隊列源源不斷地有分組到達時，就會造成低優(yōu)先級分組被“餓死”的現(xiàn)象，即在很長一段時間內得不到服務，所以公平性很差。

QLT算法就是針對這個問題進行改進的，它給每個隊列設置調度閾值，需要進行調度時從最高優(yōu)先級開始比較隊列的長度和調度閾值，當最高優(yōu)先級的隊列長度大于等于其調度閾值時，該隊列頭部分組首先被選擇服務;當最高優(yōu)先級的隊列長度小于其調度閾值時，不再服務該隊列，而是檢查具有次高優(yōu)先級的隊列，如此類推。通過設置合理的調度閾值，QLT算法在保證優(yōu)先級關系的基礎上，提高了公平性。

4 AVQ算法的改進

相對于原AVQ來說，這種新算法的優(yōu)點是針對不同的業(yè)務賦以不同的優(yōu)先級，根據(jù)不同的優(yōu)先級給予不同的服務等級，從而達到保證業(yè)務Qos指標的目的。雖然與AVQ算法相比，運算負載度可能會有所升高，但只要解決好隊列調度算法與緩存管理的協(xié)調，算法的復雜度就不會很高。

首先基于AVQ算法在路由器上維持一個虛擬隊列的思想，在路由器中維持多個虛擬隊列(下面以N為例)，每個虛擬隊列對應一個實際隊列，它們之間完全共享緩沖資源和輸出鏈路帶寬。虛擬隊列的虛擬帶寬i小于實際隊列對應的輸出鏈路帶寬C，而其總的緩沖容量與實際隊列的一致。在實際操作中，不需要對每個虛擬隊列進行入隊和出隊操作，只需要維護每個虛擬隊列的長度VQi即可。其中，緩沖資源在每個隊列間的分配借鑒DT算法的思想，實行動態(tài)閾值分配。

Ti=αi(B-∑iVQi)

VQi+bi≤Ti時，允許接收分組

(6)

式中:Ti為優(yōu)先級為i的分組對應的控制閾值;VQi為優(yōu)先級為i的分組對應的長度;bi為到達分組長度;B為總的緩沖空間。如果該分組的加入不會引起該虛擬隊列溢出，則更新虛擬隊列長度:

VQi=VQi+bi

(7)

在鏈路輸出端運用單個調度器根據(jù)QLT的調度策略調度緩沖分組，并更新調度隊列的虛擬隊列長度VQi和虛擬服務速率i。

VQi=VQi-ai

(8)

i=i+α*γ*ti*C

(9)

其中，緩沖資源的管理和調度器的調度工作相互獨立進行，時間上不相沖突。

算法偽代碼如下:

ti=0(i=0，1，2，…，N)//虛擬隊列i中分組發(fā)送經歷時間

for(i=0;i≤N;i++)

{if(VQi≥Thi) //Thi為隊列i對應的調度閾值

在實際隊列中選擇頭部分組進行發(fā)送;

{ti=aii

VQi =max(VQi-ai，0)//ai為隊列i頭部分組長度

i=min(i+α*γ*ti*C，C) //更新虛擬隊列容量

break;//結束整個循環(huán)

}

}

當有新的分組到達時

Ti=αi(B-∑iVQi)//Ti為優(yōu)先級為i的分組對應的控制閾值

if(VQi+bi≤Ti)//VQi為隊列i對應的長度

VQi =VQi +bi;

else

實際隊列中標記或丟棄分組

endif

i=max(i-α*bi，0)

改進的AVQ算法同原AVQ算法比較而言，增加了基于優(yōu)先級的區(qū)分服務性能。另外，它同原AVQ算法相比有一些性能上的差別:它對緩沖資源在各虛擬隊列間的分配進行動態(tài)閾值控制，為低優(yōu)先級的分組提供了一定的緩沖資源，使其總能獲得一定的服務，而且不同優(yōu)先級之間的緩沖資源分配比可以通過對αi因子的調節(jié)來實現(xiàn)。只要αi的值滿足一定的條件，就能保證系統(tǒng)性能的穩(wěn)定性。其次，總是預留一部分緩沖資源，雖然造成了資源浪費，但是對于調整系統(tǒng)的瞬態(tài)性能提供了有效的支持，同時也保證了不同優(yōu)先級服務之間的公平性，而且通過動態(tài)控制參數(shù)的調整，能夠在一定程度上適應網(wǎng)絡流量的變化。

5 結 語

總體來說，改進的AVQ算法增加了基于優(yōu)先級的區(qū)分服務性能，基本上保持了原算法的優(yōu)點:低時延、低分組丟失率和高鏈路利用率，但卻需要維持多個虛擬隊列，這樣在算法復雜度上可能會大于原算法。

隨著Internet規(guī)模的不斷增大，先進的多媒體系統(tǒng)層出不窮。由于實時業(yè)務對網(wǎng)絡傳輸時延、延時抖動等特性較為敏感，當網(wǎng)絡上有突發(fā)性高的FTP或者含有圖像文件的 HTTP 等業(yè)務時，實時業(yè)務就會受到很大影響;另一方面，多媒體業(yè)務占去了大量的帶寬，這樣，現(xiàn)有網(wǎng)絡要保證的關鍵業(yè)務就難以得到可靠的傳輸。所以，在現(xiàn)有的網(wǎng)絡中如何保證不同業(yè)務的 QoS指標就成了一個十分重要的問題。

因此，如何在路由器中更好地將這些算法結合起來也是一個難點，隨著通信技術的不斷發(fā)展，相信這些問題都能被很好的解決。

參考文獻

[1]KUNNIYURS Srikant R.Analysis and design of an adaptive virtual queue (AVQ) algorithm for active queue management [C]//IEEE SIGCOMM 2001. [S.l.]: IEEE， 2001.

[2]CHOUDHURY A K， HAHNE E L.Dynamic queue length thresholds for shared-memory packet switches [J]. IEEE/ACM Trans. Networking，1998，6:130-140.

[3]CHIOPALKATTI R， KUROSE J， TOWSLEY D. Scheduling policies for real-time and non-real-time traffic in a statistical multiplexer [C]//IEEE INFOCOM′89. Ottawa， Camada: IEEE， 1989: 774-783.

[4]OTT Tenuis J， LAKSHMAN T V， WONG Larry H. SRED: stabilized RED [C]//IEEE INFOCOM′99. New York， USA: [s.n.]， 1999: 1346-1355.

[5]FENG W， KANDLUR D， SAHA D， et al. A self-configuring RED gateway [C]//IEEE INFOCOM′99. New York， USA: [s.n.]， 1999: 1320-1328.

[6]林闖，單志廣，任豐原.計算機網(wǎng)絡的服務質量(QoS)[M].北京:清華大學出版社，2004.

[7]高傳善.數(shù)據(jù)通信與計算機網(wǎng)絡[M].北京:高等教育出版社，2005.

[8]沈鑫剡.多媒體傳輸網(wǎng)絡與VoIP系統(tǒng)設計[M].北京:人民郵電出版社，2005.