具有自相似性質(zhì)的業(yè)務(wù)流的主動(dòng)隊(duì)列管理算法

付鈺　張艷琴　胡俊超　潘彩平

摘 要：近年來的研究表明，網(wǎng)絡(luò)流量呈現(xiàn)出很強(qiáng)的自相似特性，這是造成網(wǎng)絡(luò)擁塞的重要因素之一。因此該文提出了一種基于時(shí)間的主動(dòng)隊(duì)列管理算法，該算法利用ON/OFF源模型模擬產(chǎn)生自相似流，依據(jù)信源持續(xù)發(fā)送數(shù)據(jù)包的時(shí)間，來選擇性地接收數(shù)據(jù)包。用MATLAB進(jìn)行仿真，實(shí)驗(yàn)結(jié)果表明該算法的隊(duì)列管理性能明顯優(yōu)于ARED等傳統(tǒng)隊(duì)列管理算法，能很好地控制隊(duì)列長度。

關(guān)鍵詞：自相似 主動(dòng)隊(duì)列管理 ON/OFF源 擁塞控制

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2017）06（c）-0142-02

20世紀(jì)90年代初，D.V.Wilson等人對(duì)實(shí)際的網(wǎng)絡(luò)流量進(jìn)行了大量的研究[2]，通過收集大量以太網(wǎng)業(yè)務(wù)流的數(shù)據(jù)包，對(duì)現(xiàn)實(shí)網(wǎng)絡(luò)流量做出了充分觀察與分析，最終得出現(xiàn)實(shí)網(wǎng)絡(luò)流量模型的統(tǒng)計(jì)特性與傳統(tǒng)流量模型的統(tǒng)計(jì)特性有著較大的差別。實(shí)際的網(wǎng)絡(luò)流量表現(xiàn)出明顯的自相似特性，反應(yīng)在網(wǎng)絡(luò)流量上面，就是指網(wǎng)絡(luò)流量是一種隨機(jī)過程，并且在時(shí)間尺度上呈現(xiàn)出自相似性，在進(jìn)行合理的放大后，依然具有這種性質(zhì)。自相似性對(duì)網(wǎng)絡(luò)擁塞控制具有很深的影響，所以傳統(tǒng)的基于泊松流量模型的信源已經(jīng)不能滿足研究的需要。為了能夠模擬出更加真實(shí)的網(wǎng)絡(luò)流量模型，我們需要改進(jìn)信源模型。在仿真實(shí)驗(yàn)中采用ON/OFF源模型[4]產(chǎn)生具有自相似性的流量，并提出一種依據(jù)信源持續(xù)發(fā)送數(shù)據(jù)的時(shí)間長短來控制接收數(shù)據(jù)包的新算法。

1 ON/OFF源模型生成自相似流

ON/OFF源是一種信源模型，用于模擬網(wǎng)絡(luò)業(yè)務(wù)流量的產(chǎn)生。ON/OFF源的產(chǎn)生機(jī)制是模仿真實(shí)的用戶，在產(chǎn)生流量的時(shí)候，每個(gè)用戶會(huì)持續(xù)發(fā)送數(shù)據(jù)包，然后會(huì)停止一段時(shí)間，用ON周期與OFF周期分別代表持續(xù)發(fā)送時(shí)間與停止發(fā)送的時(shí)間。并且ON周期與OFF周期獨(dú)立同分布，具有嚴(yán)格交替性。在ON周期按恒定速率發(fā)送數(shù)據(jù)包，在OFF周期停止發(fā)送數(shù)據(jù)包。Willinger等人從以太網(wǎng)單個(gè)信源抽象出的ON/OFF模型中發(fā)現(xiàn)ON周期與OFF周期的持續(xù)時(shí)間呈重尾分布，重尾分布是網(wǎng)絡(luò)流量自相似性質(zhì)的一個(gè)重要的因素。Willinger等人證明當(dāng)很多個(gè)服從Pareto分布的ON/OFF源疊加之后，就能產(chǎn)生具有自相似性質(zhì)的流量。Pareto分布的概率密度是：

當(dāng)時(shí)，Hurst系數(shù)H滿足。用ON/OFF源模型模擬網(wǎng)絡(luò)流量具有簡單、容易實(shí)現(xiàn)等特點(diǎn)，能夠有效地模擬出真實(shí)的網(wǎng)絡(luò)流量。

2 擁塞控制與主動(dòng)隊(duì)列管理

通信網(wǎng)絡(luò)中的帶寬，交換節(jié)點(diǎn)中的緩存容量和處理機(jī)等等，都是網(wǎng)絡(luò)資源。當(dāng)大量的流量在網(wǎng)絡(luò)中傳輸時(shí)，若對(duì)某一資源的需求超過了該資源所能提供的可用部分，網(wǎng)絡(luò)的性能就會(huì)下降，甚至嚴(yán)重影響通信質(zhì)量，導(dǎo)致延遲增大，重要的數(shù)據(jù)無法及時(shí)到達(dá)，破環(huán)一致性等等，給用戶帶來很差的網(wǎng)絡(luò)體驗(yàn)。這種情況就是網(wǎng)絡(luò)擁塞[3]。

為避免網(wǎng)絡(luò)擁塞，就迫切需要有效的網(wǎng)絡(luò)擁塞控制技術(shù)，以防止過多的數(shù)據(jù)注入到網(wǎng)絡(luò)中，這樣就可以使網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)節(jié)點(diǎn)不致過載，保證通信質(zhì)量。目前的網(wǎng)絡(luò)擁塞控制，一是在協(xié)議層面上的，也就是TCP網(wǎng)絡(luò)擁塞控制協(xié)議。還有一種減少網(wǎng)絡(luò)擁塞發(fā)生的辦法是主動(dòng)隊(duì)列管理，主要原理是在接收到數(shù)據(jù)包后根據(jù)資源的占用情況對(duì)數(shù)據(jù)包選擇性地丟棄，這可以保證在網(wǎng)絡(luò)擁塞發(fā)生前及時(shí)地調(diào)節(jié)信源發(fā)送的數(shù)據(jù)量。比如隨機(jī)早期檢測(cè)算法RED以及其各種改進(jìn)的算法ARED，HPRED等[1]。

3 自相似流的隊(duì)列管理算法

在自相似業(yè)務(wù)流下，以前的各種隊(duì)列管理算法雖然也能達(dá)到一定的擁塞控制要求，但是在越來越復(fù)雜的網(wǎng)絡(luò)流量環(huán)境下，仍然需要對(duì)其進(jìn)行改進(jìn)，以適應(yīng)不斷變化的網(wǎng)絡(luò)流量。本文提出一種基于信源持續(xù)發(fā)送時(shí)間長度的主動(dòng)隊(duì)列管理算法。此算法與基本的RED算法的思想相同，也是根據(jù)上限值與下限值來控制信源的發(fā)包速率，但是不再依據(jù)隊(duì)列長度來給定兩個(gè)上下限值，而是根據(jù)信源持續(xù)發(fā)送數(shù)據(jù)包的時(shí)間，當(dāng)信源發(fā)送數(shù)據(jù)包的持續(xù)時(shí)間過長時(shí)，就應(yīng)該增大概率丟棄一些數(shù)據(jù)包，當(dāng)信源持續(xù)發(fā)送數(shù)據(jù)包的時(shí)間比較短時(shí)，應(yīng)該以更大概率接收數(shù)據(jù)包，這里涉及到兩個(gè)重要的參數(shù)a和b，分別代表系統(tǒng)所允許的信源發(fā)送時(shí)間的最大值和最小值，信源實(shí)際的發(fā)送時(shí)間為t，然后根據(jù)以下過程接收數(shù)據(jù)包：

步驟1：從信源接收到數(shù)據(jù)包，并初始化參數(shù)a和b。

步驟2：判斷信源發(fā)送數(shù)據(jù)包的持續(xù)時(shí)間t，若tb，進(jìn)入步驟5。

步驟3：按概率1接收數(shù)據(jù)包。

步驟4：根據(jù)算法計(jì)算出概率P，按概率P接收數(shù)據(jù)包。

步驟5：按概率1拒絕數(shù)據(jù)包。

以下是仿真結(jié)果：

由仿真結(jié)果圖可以看出，在自相似流模型下，ARED隊(duì)列管理算法下的緩存平均隊(duì)列長度比較大，與舊的ARED隊(duì)列管理算法相比較，新的隊(duì)列管理算法對(duì)應(yīng)的平均隊(duì)列長度大約為30，ARED列隊(duì)管理算法對(duì)應(yīng)的平均隊(duì)列長度大約為50，降低了40%左右。這對(duì)于資源有限的衛(wèi)星網(wǎng)絡(luò)來說，新算法可以減少一定的硬件資源成本，降低網(wǎng)絡(luò)延遲抖動(dòng)的風(fēng)險(xiǎn)。

4 結(jié)語

該文主要介紹了在自相似流模型下基于時(shí)間的主動(dòng)隊(duì)列管理算法。該算法根據(jù)信源發(fā)送數(shù)據(jù)包的持續(xù)時(shí)間來選擇性地接收到達(dá)的數(shù)據(jù)包，當(dāng)發(fā)送時(shí)間過長時(shí)，以較大概率丟棄一定數(shù)量的數(shù)據(jù)包，當(dāng)發(fā)送時(shí)間比較短時(shí)，以更大的概率接收數(shù)據(jù)包。在仿真實(shí)驗(yàn)中表現(xiàn)出比ARED算法更好的隊(duì)列管理性能，有效地降低了緩存中的平均隊(duì)列長度，并且使隊(duì)列長度更加平穩(wěn)，可以在一定程度上減少網(wǎng)絡(luò)擁塞發(fā)生的可能性。

參考文獻(xiàn)

[1] 余信珂.基于改進(jìn)的控制時(shí)延主動(dòng)隊(duì)列管理算法研究[D].深圳大學(xué)，2016.

[2] 于秦.無線網(wǎng)絡(luò)流量分形特性分析與建模[D].電子科技大學(xué)，2006.

[3] 張婭.自相似業(yè)務(wù)模型下主動(dòng)隊(duì)列管理算法的研究[D].江蘇大學(xué)，2007.

[4] 胡嚴(yán)，張光昭.重尾ON/OFF源模型生成自相似業(yè)務(wù)流研究[J].電路與系統(tǒng)學(xué)報(bào)，2001（3）：72-76，15.