基于自相似流量的一種新的隊列管理算法

摘要:鑒于網(wǎng)絡(luò)流量的自相似特性，結(jié)合應(yīng)對該特性可采用的兩種主要措施，提出了一種應(yīng)對該特性的一種新的隊列管理算法。算法包括兩部分，一是緩沖區(qū)管理算法，另一是隊列調(diào)度算法。新算法在緩沖區(qū)管理上采用了一種“偽擴充”緩沖區(qū)的方法?！皞螖U充”維持緩沖區(qū)總空間的不變的情況下，按照策略增加一個用于處理自相似突發(fā)流量的隊列。針對“擴充”后的緩沖區(qū)，采用基于靜態(tài)優(yōu)先級和輪詢的隊列調(diào)度算法。從理論上分析了，兩部分的結(jié)合產(chǎn)生的新的隊列管理算法在應(yīng)對自相似突發(fā)流量中的有用性。

關(guān)鍵詞:自相似;緩沖區(qū)管理算法;隊列調(diào)度算法;偽擴充;突發(fā)

A New Queues Management Algorithm Based on Self-Similar Traffic

ZHU Xun

(Department of Computer Science Technology， Chengdu University of Information Technology， Chengdu 610225， China)

Abstract: In view of network traffic self-similarity， reference to the two main available measures to deal this characteristic， this paper put forward a new queue management algorithm for the characteristic. The algorithm consists of buffer management strategy and queues scheduling strategy. The new queue management algorithm uses a new method which is named as \"pseudo-expansion buffer zone\". The \"pseudo-expansion\" strategy keeps the total buffer zone unchanged， but adds anther queue for dealing with self-similar burst traffic. For \"expanded\" buffer， new queue scheduling algorithm is based on static priority and round-robin. form the theoretical analysis， the new queue management algorithm is useful when dealing self-similar network traffic.

Key words: self-similarity; buffer management algorithm; queue scheduling algorithm; pseudo-expansion; burst

通過大量的網(wǎng)絡(luò)測量和分析證實了:Internet業(yè)務(wù)流(如LAN[1]、WAN[2]、Web[3]流量)在所有時間尺度均呈現(xiàn)自相似特性(Self-Similarity)。自相似突出表現(xiàn)為業(yè)務(wù)的突發(fā):沒有一個明確、本質(zhì)的長度，從微秒到分鐘，從分鐘到小時，數(shù)據(jù)流的突發(fā)性并不隨著時間規(guī)模的增大而變?nèi)?，不同時間標度數(shù)據(jù)流都表現(xiàn)出相似的突發(fā)特性[4]。在自相似流量下，基于傳統(tǒng)的排隊模型、泊松流模型、Markov鏈模型等網(wǎng)絡(luò)流量模型的隊列調(diào)度策略和分組交換算法已經(jīng)不太適應(yīng)。眾多專家學(xué)者對自相似流量下的分組交換算法做相當(dāng)多的研究，提出了一些更合適于的數(shù)據(jù)包調(diào)度、交換算法，如:基于動態(tài)優(yōu)先級和基于服務(wù)概率的隊列管理算法[5]。

在自相似網(wǎng)絡(luò)環(huán)境中，如果要得到較高有效緩存利用率或低溢出概率，可以采用以下兩種方法:一種是增加路由器緩存容量;另一種是采用有效的隊列管理算法。但使用第一種方法有如下缺點:當(dāng)大容量緩存都被充滿時，所有連接上的延遲都將急劇增大;突發(fā)聚集成更大的突發(fā)，導(dǎo)致?lián)砣^續(xù)拖延下去，因此增加緩存容量并不能有效降低溢出概率。因此，如何改進隊列管理算法成為眾多學(xué)者關(guān)注的焦點。

受文獻[5]及其他基于動態(tài)優(yōu)先級的隊列管理算法的啟發(fā)，本文提出了基于“偽擴充”的隊列管理算法。

1 新隊列管理算法介紹

該文提出的基于“偽擴充”的隊列管理算法由兩部分構(gòu)成:一是隊列緩沖區(qū)“偽擴充”，另一是針對擴充后的隊列調(diào)度算法。

1.1 緩沖區(qū)管理算法

在應(yīng)對自相似突發(fā)流量的解決方法中有一種可用的方法是擴大緩沖區(qū)容量，“偽擴充”隊列管理算法結(jié)合了這種的思想。“偽擴充”策略是在保持隊列緩沖區(qū)總大小不變的情況下，按照一定策略，從原有緩沖區(qū)隊列中，對各個隊列進行適當(dāng)比例的空間截取，把這些截取的空間進行拼接成一個新的隊列，即為“擴充”了緩沖區(qū)。再結(jié)合隊列管理算法，提高自相似流量下隊列緩沖區(qū)的利用率?！皵U充”的新隊列用于輔助每一個隊列應(yīng)對突發(fā)的自相似網(wǎng)絡(luò)流量，相當(dāng)于擴大了單個隊列的容量。

緩沖區(qū)截取的策略:假設(shè)原有緩沖區(qū)共分i個隊列，其中每個隊列的大小為p單位。新的算法是把i個隊列的緩沖區(qū)進行截短，設(shè)截取參數(shù)為a，把截取的i段緩沖區(qū)組合成一個隊列，如果使得合并的新隊列大小和截取操后的原隊列的大小保持相近，則a的取值為1/(i+1)。轉(zhuǎn)化效果如圖1所示。

緩沖區(qū)按照圖1所示意的“擴充”策略轉(zhuǎn)化后，當(dāng)某類型業(yè)務(wù)流對應(yīng)的隊列滿后，新隊列作為原隊列的一個后備隊列，這樣相當(dāng)于給原有隊列增大到原來的2i/(i+1)倍。

數(shù)據(jù)包從分類器進入相應(yīng)優(yōu)先級的隊列，當(dāng)相應(yīng)的隊列滿后，后續(xù)的數(shù)據(jù)包進入第n+1個隊列(即為新隊列)中，如果第n+1個隊列也為滿的情況下，對后續(xù)數(shù)據(jù)包做簡單的丟棄。

1.2隊列調(diào)度算法

對于隊列服務(wù)管理常用的有兩類，一種是基于通用處理機共享，一種是基于輪詢。這兩類算法存在一個共同的問題， 即需要執(zhí)行基于數(shù)據(jù)包的權(quán)重計算，其中對基于GPS的算法， 需要對每個數(shù)據(jù)包進行虛時間計算;而基于動態(tài)優(yōu)先級的輪詢類算法， 每發(fā)送一個數(shù)據(jù)包就需要重新計算權(quán)重參數(shù)。對比兩種算法的計算復(fù)雜度，基于輪詢的算法更小，所以本文提出的隊列調(diào)度策略基于輪詢算法。

本論文提出的算法的隊列管理策略如下:給緩沖區(qū)中各個隊列進行優(yōu)先級設(shè)定，以及時間片分配，每個隊列分配到的優(yōu)先級和時間片作為一個常量。如緩沖區(qū)共有隊列n個，“擴充”后則為n+1個，對n個隊列進行優(yōu)先級分配，第一個隊列優(yōu)先級設(shè)定為1，也即為最低優(yōu)先級，時間片分配t1個單位;第二個優(yōu)先級設(shè)定為2，時間片分配t2個單位;以此類推至第n個隊列。第n+1個隊列(即為新隊列)調(diào)度算法按照隊列分配的時間片進行，兼顧緩沖區(qū)原有隊列的時間片分配，新隊列的時間片分配原則按照平均的原則，做原有隊列分配時間片和的平均值。新隊列的優(yōu)先級定位0，其時間片分配按tn/i個單位，即按照中等優(yōu)先級隊列分配時間片。

隊列輪詢服務(wù)算法流程如下:

1)對隊列的執(zhí)行為從優(yōu)先級最高的隊列開始，設(shè)置一個變量index值為n(變量index用于存儲當(dāng)前接受服務(wù)隊列優(yōu)先級，也即是指向當(dāng)前接受服務(wù)的隊列);

2)如果隊列優(yōu)先級大于0，轉(zhuǎn)到3)，否則轉(zhuǎn)到6);

3)按照優(yōu)先級級別為index應(yīng)分配到的時間片進行服務(wù)，當(dāng)時間片用完但仍未處理完該隊列的數(shù)據(jù)包時，轉(zhuǎn)到4)，如果數(shù)據(jù)處理完，仍有時間片剩余時轉(zhuǎn)到5);

4)中斷該隊列的處理，index值減1，轉(zhuǎn)到2);

5)用剩余的時間片處理第n+1個隊列中數(shù)據(jù)，時間片用完時仍未處理完時，index值減1，轉(zhuǎn)到2);如第n+1個隊列中的數(shù)據(jù)處理完，但時間片仍有剩余時，轉(zhuǎn)入到下一個優(yōu)先級的隊列，index值減1，轉(zhuǎn)到2);

6)按照第n+1個隊列對應(yīng)的時間片進行數(shù)據(jù)包處理，時間片到但仍未處理完數(shù)據(jù)時，轉(zhuǎn)到1;處理完數(shù)據(jù)包后，時間片仍有剩余則轉(zhuǎn)到1)。

2新算法的優(yōu)點分析

2.1 適合自相似流量的突發(fā)性

自相似流量具有突發(fā)性，突發(fā)數(shù)據(jù)包到達是對隊列緩沖區(qū)的要求特別大。Laskin等人[6]基于FLM(Fractional Levy Motion)過程建立了一個經(jīng)典的解析模型，并得出自相似網(wǎng)絡(luò)環(huán)境中隊列緩存容量需求b(或稱隊列長度)與平均資源利用率ρ的關(guān)系如下:

b=cp 1/(a-a·H)(1-p) -H(1-H)，其中，c為一個常數(shù)，a∈(0，2)為特征指數(shù);H∈[1/a ，1)為自相似參數(shù)，且H越大，自相似程度越高。在c為1的情況下，從(a=2，H=0.7)、(a=2，H=0.9)、(a=0.6，H=0.8)和(a=1.2，H=0.8)四組條件下函數(shù)對應(yīng)的曲線分析，自相似參數(shù)H越大，曲線斜率變化越大，隊列緩存容量需要也越大，并在緩存平均利用率為35%~65%區(qū)間內(nèi)開始急劇增長[4]。

按照新算法，由于對發(fā)生突發(fā)業(yè)務(wù)流量的隊列長度增加了近一倍大小。也既是在沒有增加緩沖區(qū)總體容量和緩沖區(qū)數(shù)據(jù)包的處理時延的情況下，增大隊列緩沖區(qū)的容量。所以能有效應(yīng)對突發(fā)的自相似流量。

2.2較基于隊列長度動態(tài)管理算法

動態(tài)調(diào)整的算法，往往是在突發(fā)的自相似流量到達并溢出隊列時，根據(jù)丟包標識位的定時掃描發(fā)現(xiàn)，然后掃描有空閑的隊列上截取空閑部分，再進行和現(xiàn)有隊列拼接。其中丟包標識位的定時循環(huán)掃描、空閑隊列的掃描都是耗時的，并且空閑隊列的截取和拼接在較差情況下，會導(dǎo)致更多的丟包以及空閑隊列的掃描、截取和拼接的耗時。

本文提出的新的算法，把發(fā)生突發(fā)情況后，原隊列被填充滿后，會把更多的數(shù)據(jù)包轉(zhuǎn)移到新生成的隊列中，避免了隊列的丟包標示位的掃描、空閑隊列的掃描、截取和拼接造成的時延，有利于提高緩沖區(qū)中數(shù)據(jù)包的響應(yīng)時間，增大了吞吐量。

2.3較基于服務(wù)概率的隊列調(diào)度算法

基于優(yōu)先級調(diào)度的輪詢的算法存在“饑餓”問題，有的學(xué)者提出了“概率優(yōu)先級(probabilistic priority)”的概念來解決此問題[7]。該策略它為每個優(yōu)先級分配一個服務(wù)概率參數(shù)， 當(dāng)該優(yōu)先級獲得服務(wù)機會時，不是100%獲得服務(wù)， 而是以該服務(wù)概率參數(shù)的概率獲得服務(wù)。

本文中提出的隊列管理算法是更為簡單:它給固定優(yōu)先級的隊列分配固定的時間片。在隊列滿負荷工作的情況下，各個隊列循環(huán)掃描服務(wù)一遍后，優(yōu)先級最高的隊列得到了最長時間的服務(wù)，優(yōu)先級最低的得到的服務(wù)時間最少，從而保證了優(yōu)先級隊列的服務(wù)時間，又避免了“饑餓”現(xiàn)象的發(fā)生。本文中對“優(yōu)先級”的處理為:并非高優(yōu)先級的處理完再處理低優(yōu)先級的，而是按優(yōu)先級分配處理時間片。

2.4較自相似流量的檢測機制

在處理自相似突發(fā)流量研究中，有些學(xué)者提出了對自相似流量的早檢測的方法。文章[8]提出的隨即早檢測的方法是對比于泊松模型下的網(wǎng)絡(luò)流量，基于自相似流量的突發(fā)性，擴大最大和最小值之間差距的方式來檢測自相似流量，并設(shè)計了一種丟包策略。

由于自相似流量的突發(fā)的特性，考慮進入交換系統(tǒng)中多種不同的網(wǎng)絡(luò)數(shù)據(jù)流和同一數(shù)據(jù)流在具體的不同時間段下的流量波動，自相似流量的hurst指數(shù)的并不確定性，因此對于自相似流量的早檢測方法，都是具有局限性的。并且由于計算數(shù)據(jù)包到達的流量和比較流量是否達到自相似閾值都有一定耗時，本論文中提出的新算法節(jié)省了上述耗時操作，以分配更多的時間片給緩沖區(qū)隊列用于數(shù)據(jù)包處理。

3 結(jié)束語

該文中提出的算法，在緩沖區(qū)的管理策略上和隊列調(diào)度算法上，對比于眾多基于動態(tài)隊列調(diào)整的算法有著顯著的不同，“擴充”的緩沖區(qū)隊列、避免了動態(tài)調(diào)整隊列長度上的耗時和避免優(yōu)先權(quán)重計算的調(diào)度算法，三者會使得系統(tǒng)吞吐量更大，進而能有效應(yīng)對自相似的突發(fā)流量。

該算法下一步的工作是通過仿真，驗證算法的實際效果。然后研究實際情況下的不同業(yè)務(wù)流量，設(shè)計更優(yōu)的隊列管理算法。

參考文獻:

[1] Leland W E，Taqqu M，Willinger W.On the Self-Similar Nature of Ethernet Traffic (extended version)[J].IEEE/ACM Transactions on Networking (S1063-6692)，1994，2(1):1-15.

[2] Paxson V，F(xiàn)loyd S.Wide Area Traffic: the Failure of Poisson Modeling[J].IEEE/ACM Transactions on Networking (S1063-6692)，1995，3(3):226-244.

[3] Crovella M E，Bestavros A.Self-Similarity in World-Wide Web Traffic: Evidence and Possible Causes[J].IEEE/ACM Transactions on Networking (S1063-6692)，1997，5(6):835-846.

[4] 張連明.一種基于自相似業(yè)務(wù)的隊列管理算法[J].系統(tǒng)仿真學(xué)報，2007，2，19(3):597-600.

[5] 尹德斌，謝劍英.一種新的加權(quán)公平調(diào)度算法[J].計算機工程，2008，2，34(4):28-30.

[6] Laskin N，Lambadaris I，Harmantzis F C，Devetsikiotis M.Fractional Levy Motion and its Application to Network Traffic Modeling[J].Computer Networks (S1389-1286)，2002(40):363-375.

[7] Jiang Y，Tham C K，Ko C C.A probabilistic priority scheduling discipline formulti-service networks[C].In IEEE ISCC’2001，2001.

[8] 譚獻海.自相似流量隨機早檢測方法[J].西南交通大學(xué)學(xué)報，2008，43(1):19-24.