邱　艷， 張　洪

(1.水利部 綜合事業(yè)局, 北京　100053； 2.成都大學(xué) 信息科學(xué)與工程學(xué)院, 四川 成都　610106；3.模式識(shí)別與智能信息處理四川省高校重點(diǎn)實(shí)驗(yàn)室, 四川 成都　610106)

?

一種有效的網(wǎng)絡(luò)流量預(yù)測(cè)算法

邱艷1， 張洪2,3

(1.水利部 綜合事業(yè)局, 北京100053； 2.成都大學(xué) 信息科學(xué)與工程學(xué)院, 四川 成都610106；3.模式識(shí)別與智能信息處理四川省高校重點(diǎn)實(shí)驗(yàn)室, 四川 成都610106)

摘要：為了對(duì)網(wǎng)絡(luò)流量做定量研究，提出一種基于穩(wěn)態(tài)隊(duì)列長(zhǎng)度的新型網(wǎng)絡(luò)實(shí)際流量預(yù)測(cè)算法(Prediction algorithm based on Queue length of Steady state for FARIMA model，PQSF).該算法首先利用基于穩(wěn)態(tài)隊(duì)列長(zhǎng)度的乘積解理論推導(dǎo)節(jié)點(diǎn)數(shù)據(jù)包的排隊(duì)情況，計(jì)算出存在失效節(jié)點(diǎn)時(shí)流量平均對(duì)長(zhǎng)的數(shù)學(xué)公式，并結(jié)合FARIMA模型建立預(yù)測(cè)方法，最后通過(guò)網(wǎng)絡(luò)仿真對(duì)PQSF算法進(jìn)行驗(yàn)證.實(shí)驗(yàn)結(jié)果表明，該算法具有較好的適應(yīng)性.

關(guān)鍵詞：流量預(yù)測(cè)；乘積解；隊(duì)列長(zhǎng)度

0引言

隨著網(wǎng)絡(luò)規(guī)模的急劇增加，節(jié)點(diǎn)的有效性對(duì)網(wǎng)絡(luò)性能產(chǎn)生了重要影響.因此，準(zhǔn)確有效地分析、計(jì)算節(jié)點(diǎn)的有效性對(duì)于網(wǎng)絡(luò)流量的刻畫(huà)有著重要意義.為此，國(guó)內(nèi)外學(xué)者對(duì)網(wǎng)絡(luò)流量的計(jì)算進(jìn)行了大量研究工作，比如，Sahinoglu等[1]利用概率表達(dá)式對(duì)網(wǎng)絡(luò)的可靠性進(jìn)行評(píng)估，劉愛(ài)民等[2]提出通信網(wǎng)的可靠性評(píng)價(jià)測(cè)度，魏娟等[3]提出PFB算法如何對(duì)網(wǎng)絡(luò)流量進(jìn)行重新刻畫(huà)，張洪等[4]提出PDF算法對(duì)網(wǎng)絡(luò)流量的準(zhǔn)確預(yù)測(cè).基于上述研究結(jié)果，本研究依據(jù)最有乘解積等相關(guān)數(shù)學(xué)方法，利用離散時(shí)間排隊(duì)論相關(guān)知識(shí)，對(duì)網(wǎng)絡(luò)數(shù)據(jù)包流量進(jìn)行定量刻畫(huà)，建立平穩(wěn)的平均隊(duì)長(zhǎng)[5]的數(shù)學(xué)模型，并通過(guò)網(wǎng)絡(luò)仿真軟件對(duì)該算法進(jìn)行實(shí)驗(yàn)驗(yàn)證.

1相關(guān)定義

將N個(gè)離散時(shí)間排隊(duì)系統(tǒng)連接成一個(gè)網(wǎng)絡(luò)，每個(gè)系統(tǒng)依次記為結(jié)點(diǎn)，j,j=1,…，N.正如對(duì)單個(gè)離散時(shí)間排隊(duì)系統(tǒng)一樣，本研究約定每個(gè)結(jié)點(diǎn)處，數(shù)據(jù)包離去只能發(fā)生在時(shí)隙首端(n,n+)處.若在(n,n+)處有數(shù)據(jù)包從結(jié)點(diǎn)i完成服務(wù)離開(kāi)，它將以概率rij在該時(shí)隙末端成為結(jié)點(diǎn)j處的一個(gè)到達(dá)，i,j=1,…，N.約定從網(wǎng)絡(luò)外部到達(dá)各結(jié)點(diǎn)的數(shù)據(jù)包也發(fā)生在時(shí)隙末端(n-，n)處.也就是說(shuō)，網(wǎng)絡(luò)中每一個(gè)結(jié)點(diǎn)是一個(gè)晚到且有延遲入口的離散時(shí)間排隊(duì)系統(tǒng).這里，概率rij,i，j=1,…，N稱(chēng)為數(shù)據(jù)包在各結(jié)點(diǎn)之間的轉(zhuǎn)移概率，它們是構(gòu)成數(shù)據(jù)包在網(wǎng)絡(luò)中的某種路徑規(guī)矩，并滿足，

(1)

L=(L1,…,LN)，

n=(n1，…，nN)

(2)

并且，

L=n<=>L1=n1,…，LN=nN

(3)

定義1若網(wǎng)絡(luò)中離散時(shí)間排隊(duì)系統(tǒng)在相應(yīng)時(shí)刻具有穩(wěn)態(tài)隊(duì)長(zhǎng)，其分布如式(4)所示，那么該網(wǎng)絡(luò)有乘積解.

(4)

對(duì)連續(xù)時(shí)間排隊(duì)網(wǎng)絡(luò)，當(dāng)數(shù)據(jù)包到達(dá)和服務(wù)都是Poissn過(guò)程時(shí)可能有乘積解.而對(duì)于離散時(shí)間網(wǎng)絡(luò)中，各結(jié)點(diǎn)成批Bernoulli到達(dá)的排隊(duì)系統(tǒng)，為給出離散時(shí)間排隊(duì)網(wǎng)絡(luò)有乘積解的條件，引入離散時(shí)間準(zhǔn)可逆排隊(duì).

定義2一個(gè)晚到有延遲入口的離散時(shí)間排隊(duì)系統(tǒng)，具有成批Bernoulli到達(dá).在每個(gè)時(shí)隙末端(n-，n)處，到達(dá)批量X相互獨(dú)立，服從同一分布，

ai=P{X=i},i=0，1，…，N

(5)

Ll+1=Ll-Dl+Al,l≥0;

(6)

pD(n,i)=P{Dl=i|Lk,k=0,1,…，l-1;L1=n}=P{Dl=i|Ll=n},i=0,1,…，N

(7)

(8)

定理1數(shù)據(jù)包按照成批Bernoulli過(guò)程到達(dá)，批量分布為ai,i=0,1,…，N.這個(gè)離散時(shí)間排隊(duì)系統(tǒng)是準(zhǔn)可逆的，當(dāng)且僅當(dāng)ai=bi，i=0,1,…，N，并且離去函數(shù)形如，

(9)

(10)

在上述情況下，平穩(wěn)隊(duì)長(zhǎng)分布可表示為，

(11)

式中，c是共同的正規(guī)化因子.

2算法實(shí)現(xiàn)

本研究的算法實(shí)現(xiàn)過(guò)程如下：

1)在某時(shí)隙t初始化網(wǎng)絡(luò)中節(jié)點(diǎn)i及其相關(guān)鏈路的狀態(tài)參數(shù).

2)循環(huán)“1)”操作，根據(jù)文獻(xiàn)[6]，并根據(jù)式(4～7)建立系統(tǒng)平衡關(guān)系，

(λ+μ+w)p1,k=λp1,k-1+μp1,k+1+θp2,k，k≥2

(η+θ)p2,k=wp1,k+ηp2,k-1,k≥1

(12)

3)由于節(jié)點(diǎn)數(shù)據(jù)包服從Bernoulli過(guò)程到達(dá)，計(jì)算節(jié)點(diǎn)某時(shí)隙數(shù)據(jù)包到達(dá)概率為，

(13)

4)根據(jù)式(7)計(jì)算出節(jié)點(diǎn)在時(shí)隙邊界s處的轉(zhuǎn)移概率為，

p(n,n*)=P{Ls+1=n′|Ls=n},n,n′∈Ω

(14)

5)根據(jù)式(11)，(14)和“6)”計(jì)算出結(jié)點(diǎn)i的平穩(wěn)隊(duì)長(zhǎng)分布為，

6)使用基二FFT算法計(jì)算乘積()的反傅立葉變換，并且，

(15)

7)令t=t+1，跳轉(zhuǎn)到“1)”，直到網(wǎng)絡(luò)進(jìn)入另一狀態(tài).

8)算法結(jié)束.

3仿真實(shí)現(xiàn)

為了驗(yàn)證本研究提出算法的合理性和準(zhǔn)確性，首先在NS2網(wǎng)絡(luò)仿真軟件中，建立FARIMA節(jié)點(diǎn)模型，并且基于分形布朗運(yùn)動(dòng)(Fractional Brownian Motion，F(xiàn)BM)模型[7]產(chǎn)生點(diǎn)對(duì)點(diǎn)的網(wǎng)絡(luò)流量且成十字交叉形，結(jié)點(diǎn)平均數(shù)據(jù)包發(fā)生速率為1 800 Kbit/s.第1次仿真采用本研究提出的PFRF算法對(duì)網(wǎng)絡(luò)流量進(jìn)行模擬和預(yù)測(cè)，第2次仿真用FBM算法對(duì)網(wǎng)絡(luò)流量進(jìn)行監(jiān)控，結(jié)果如圖1所示.實(shí)驗(yàn)結(jié)果顯示，PFRF算法預(yù)測(cè)流量與原始流量較為接近，分析其標(biāo)準(zhǔn)差為10.3，說(shuō)明本算法具有一定的預(yù)測(cè)精度.

圖1PFRF預(yù)測(cè)算法與實(shí)際流量對(duì)比

圖2不同業(yè)務(wù)流到達(dá)率λ下平均隊(duì)長(zhǎng)和服務(wù)率之間的關(guān)系

4結(jié)語(yǔ)

本研究依據(jù)離散時(shí)間進(jìn)行相關(guān)數(shù)學(xué)公式推導(dǎo).當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)失效時(shí)，提出一種新型的網(wǎng)絡(luò)實(shí)際流量測(cè)算方法PFRF.該算法首先利用排隊(duì)論和FARIMA模型推導(dǎo)出節(jié)點(diǎn)數(shù)據(jù)包的排隊(duì)情況和平均對(duì)長(zhǎng)的表達(dá)式，同時(shí)通過(guò)數(shù)學(xué)仿真深入分析了影響流量性能的主要因素.實(shí)驗(yàn)結(jié)果也驗(yàn)證了PFRF算法的有效性.

參考文獻(xiàn)：

[1]Sahinoglu M,Libby D L.MeasuringavailabilityindexeswithsmallsamplesforcomponentandnetworkreliabilityusingtheSahinoglu-Libbyprobabilitymodel[J].IEEE Trans Instrum Meas,2005,54(3):1283-1295.

[2]Liu A M,Liu Y H.Trafficperformanceanalysisofnetworkwithunreliablecomponents[J].Chin J Electron，2002,30(10):1459-1462.

[3]Wei J,You L,Hu J.Anoveldepictmethodofactualtrafficperformance[J].Microelectron Comput,2013,30(3):35-37.

[4]Zhang H,Hu J,Shen Y C.Anewnetworktrafficpredictionalgorithmbasedondiscretequeue[J].J Comput Inform Syst，2015，11(12)：4255-4261.

[5]Nolan J,Panorska A.Kestimationofstablespctralmeasures[J].Math Comput Mod,2001,4(8):1113-1122.

[6]唐應(yīng)輝，唐小我.排隊(duì)論[M].北京：科學(xué)出版社，2006.

[7]Tan X H,Huang Y H,Jin W D.Modelingandperformanceanalysisofself-similartrafficbasedonFBM[C]//2007IFIPInternationalConferenceonNetworkandParallelComputing-Workshops.Washington,DC,USA:IEEE Press,2007:543-548.

Efficient Algorithm for Network Traffic Prediction

QIUYan1，ZHANGHong2,3

(1.Bureau of Comprehensive Development Ministry of Water Resources, Beijing 100053, China；2.School of Information Science and Engineering, Chengdu University, Chengdu 610106, China;3.Key Laboratory of Pattern Recognition and Intelligent Information Processing of Sichuan, Chengdu University, Chengdu 610106, China)

Abstract:In order to make quantitative research on network traffic,this paper puts forward a kind of prediction algorithm based on the queue length of steady state for FARIMA model,PQSF.The algorithm firstly uses the theory of product form solution based on the stable length of queue to derive node packet queue,then calculates the average flow rate for long mathematical formula when there are failure nodes,and establishes the prediction method combined with FARIMA.Finally, the paper validates the PQSF algorithm through the network simulation.The results show that the algorithm has comparatively good adaptability.

Key words：flow prediction;product form solution;length of queue

文章編號(hào)：1004-5422(2016)02-0150-03

收稿日期：2016-03-21.

作者簡(jiǎn)介：邱艷(1983 — )， 女， 碩士， 工程師， 從事計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)研究.

中圖分類(lèi)號(hào)：TP393.06

文獻(xiàn)標(biāo)志碼：A