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

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

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

在自相似網(wǎng)絡(luò)環(huán)境中，如果要得到較高有效緩存利用率或低溢出概率，可以采用以下兩種方法:一種是增加路由器緩存容量;另一種是采用有效的隊(duì)列管理算法。……