基于主動(dòng)隊(duì)列管理算法的研究

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

關(guān)鍵詞:主動(dòng)隊(duì)列管理算法; 自適應(yīng)虛擬隊(duì)列算法; 動(dòng)態(tài)閾值算法; 隊(duì)列長(zhǎng)度閾值算法; 改進(jìn)的AVQ算法

中圖分類號(hào):TN919-34文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):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 引 言

主動(dòng)隊(duì)列管理(Active Queue Management，AQM)是目前隊(duì)列管理的主流技術(shù)，也是實(shí)現(xiàn)擁塞控制的重要手段之一，長(zhǎng)期以來一直受到廣泛的關(guān)注。基于不同理論的各種主動(dòng)隊(duì)列管理算法隨之涌現(xiàn)，這些隊(duì)列管理算法在一定程度上完成了網(wǎng)絡(luò)擁塞控制任務(wù)，但是也不同程度地在公平性、可擴(kuò)展性以及算法的復(fù)雜度上存在缺陷。

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

1 自適應(yīng)虛擬隊(duì)列(AVQ)算法

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

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

(1)

刷新虛擬隊(duì)列長(zhǎng)度，其中，LVQ為虛擬隊(duì)列長(zhǎng)度;t為當(dāng)前時(shí)間;s為上個(gè)分組到達(dá)的時(shí)間;為虛擬服務(wù)速率。如果該分組的加入不會(huì)引起虛擬緩沖區(qū)溢出，則:

LVQ=LVQ+b

(2)

進(jìn)一步更新虛擬隊(duì)列的長(zhǎng)度，其中，b為到達(dá)分組的大小。當(dāng)每一個(gè)分組到達(dá)的時(shí)候，通過:

=α(γC-λ)

(3)

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

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

算法的偽代碼如下:

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

if LVQ+b>B

實(shí)際隊(duì)列中標(biāo)記或丟棄分組

else

允許分組進(jìn)入隊(duì)列，LVQ=LVQ+b

endif

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

S=t

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

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

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

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

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

(4)

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

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

為了適應(yīng)區(qū)分服務(wù)的需求，DT算法在物理端口的基礎(chǔ)上，引入了對(duì)不同優(yōu)先級(jí)的服務(wù)支持。DT算法為每個(gè)優(yōu)先級(jí)設(shè)置一個(gè)不同的調(diào)節(jié)因子αP，算法如式(5)所示:



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

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

(5)

式中:

QiP(t)為端口i優(yōu)先級(jí)P對(duì)應(yīng)的隊(duì)列長(zhǎng)度;TP(t)為優(yōu)先級(jí)P對(duì)應(yīng)的控制閾值。

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

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

3 隊(duì)列長(zhǎng)度閾值算法(QLT)

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

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

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

4 AVQ算法的改進(jìn)

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

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

Ti=αi(B-∑iVQi)

VQi+bi≤Ti時(shí)，允許接收分組

(6)

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

VQi=VQi+bi

(7)

在鏈路輸出端運(yùn)用單個(gè)調(diào)度器根據(jù)QLT的調(diào)度策略調(diào)度緩沖分組，并更新調(diào)度隊(duì)列的虛擬隊(duì)列長(zhǎng)度VQi和虛擬服務(wù)速率i。

VQi=VQi-ai

(8)

i=i+α*γ*ti*C

(9)

其中，緩沖資源的管理和調(diào)度器的調(diào)度工作相互獨(dú)立進(jìn)行，時(shí)間上不相沖突。

算法偽代碼如下:

ti=0(i=0，1，2，…，N)//虛擬隊(duì)列i中分組發(fā)送經(jīng)歷時(shí)間

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

{if(VQi≥Thi) //Thi為隊(duì)列i對(duì)應(yīng)的調(diào)度閾值

在實(shí)際隊(duì)列中選擇頭部分組進(jìn)行發(fā)送;

{ti=aii

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

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

break;//結(jié)束整個(gè)循環(huán)

}

}

當(dāng)有新的分組到達(dá)時(shí)

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

if(VQi+bi≤Ti)//VQi為隊(duì)列i對(duì)應(yīng)的長(zhǎng)度

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

else

實(shí)際隊(duì)列中標(biāo)記或丟棄分組

endif

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

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

5 結(jié) 語

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

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

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

參考文獻(xiàn)

[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]林闖，單志廣，任豐原.計(jì)算機(jī)網(wǎng)絡(luò)的服務(wù)質(zhì)量(QoS)[M].北京:清華大學(xué)出版社，2004.

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

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