韓建萍，張建國

(1.太原理工大學(xué) a.新型傳感器與智能控制教育部重點(diǎn)實(shí)驗(yàn)室，b.物理與光電工程學(xué)院，太原 030024；2.山西能源學(xué)院，山西 晉中 030600)

在IP網(wǎng)絡(luò)中，網(wǎng)絡(luò)鏈路丟包率推理是基于主動(dòng)探測(cè)獲得的端到端(end-to-end，E2E)路徑丟包率數(shù)據(jù)以及路徑通過的鏈路信息進(jìn)行推理的研究[1]。鏈路丟包率推理方法分為以下三類：

1) 采用多播路由發(fā)送多播探測(cè)包，利用包與包之間的強(qiáng)時(shí)間相關(guān)性，推測(cè)出擁塞的鏈路[2-3]。此類推理方法只能應(yīng)用于支持多播的網(wǎng)絡(luò)中。如果需要采用單播模擬多播，部署成本和計(jì)算成本較高。

2) 在假設(shè)鏈路發(fā)生擁塞的概率相等、發(fā)生擁塞的鏈路個(gè)數(shù)較少等條件下，對(duì)鏈路丟包率進(jìn)行推理[4-5]。此類方法涉及的假設(shè)條件需要基于經(jīng)驗(yàn)分析或理論論證，否則假設(shè)條件是否成立是此種推理方法是否可行的爭(zhēng)論點(diǎn)。

3) 基于路徑的多次探測(cè)結(jié)果，求取路徑的均值、方差值，用于鏈路丟包率的推理[6-8]。此類方法需要多次發(fā)送探測(cè)包，容易造成網(wǎng)絡(luò)擁塞。

通過對(duì)已有研究分析可知，方式1)主要集中解決多播網(wǎng)絡(luò)中的鏈路丟包率推理問題，方式3)的多次探測(cè)方式，對(duì)網(wǎng)絡(luò)數(shù)據(jù)包的正常發(fā)送和接收產(chǎn)生一定的影響。本文采用方式2)中的鏈路丟包率推理算法。但是，已有的方式2)的研究中，需要假設(shè)子鏈路或通過率較高的路徑中的鏈路作為不丟包鏈路、或者假設(shè)共享數(shù)目最多的鏈路為丟包鏈路，這種假設(shè)缺少有效的推理和證明。為解決此問題，本文提出了基于鏈路內(nèi)在相關(guān)性的IP網(wǎng)絡(luò)擁塞鏈路丟包率推斷算法(LICA)。首先，對(duì)探測(cè)路徑中網(wǎng)絡(luò)鏈路的相關(guān)性進(jìn)行了分析，基于變形的高斯約旦消元法，將探測(cè)矩陣劃分為多個(gè)獨(dú)立的子集；其次，針對(duì)每個(gè)獨(dú)立子集，建立基于貝葉斯網(wǎng)絡(luò)的鏈路擁塞推理模型，并基于每條鏈路的擁塞貢獻(xiàn)率推理鏈路擁塞概率排序集合；最后，基于代數(shù)模型推理求解化簡后的非奇異矩陣的唯一解，從而得到擁塞鏈路的丟包率。在性能分析部分，通過與相關(guān)算法比較，驗(yàn)證了本文算法的性能優(yōu)勢(shì)。

1 問題描述

假設(shè)探測(cè)得到的路徑集合為P={P1,P2,…,Pi}，包含的網(wǎng)絡(luò)鏈路集合為L={l1,l2,…,lj}.基于代數(shù)模型將網(wǎng)絡(luò)拓?fù)浜推渖系奶綔y(cè)定義為路由矩陣A.該路由矩陣包括M行、N列，其中，M行代表M個(gè)探測(cè)路徑，N列代表N個(gè)網(wǎng)絡(luò)鏈路。矩陣元素Aij=0表示探測(cè)路徑Pi沒有經(jīng)過網(wǎng)絡(luò)鏈路lj.矩陣元素Aij=1表示探測(cè)路徑Pi經(jīng)過網(wǎng)絡(luò)鏈路lj.以圖1的網(wǎng)絡(luò)拓?fù)錇槔?，如果存在?中所示的探測(cè)路徑P1,P2,P3,P4,P5,P6，可以得到圖2所示的路由矩陣A.

圖1 網(wǎng)絡(luò)拓?fù)渑e例Fig.1 Example of network topology

路徑通過的鏈路通過率P1:H1→H2e1→e2→e30.77P2:H1→H3e1→e8→e7→e51.0P3:H1→H4e1→e10→e90.85P4:H2→H3e3→e4→e50.61P5:H2→H4e3→e4→e6→e90.39P6:H3→H4e5→e6→e90.59

在IP網(wǎng)絡(luò)的性能管理中，路徑的通過率等于該路徑所通過的鏈路的通過率乘積，如公式(1)所示，其中，使用Pri表示探測(cè)路徑Pi的通過率，使用lrj表示網(wǎng)絡(luò)鏈路lj的通過率。對(duì)公式(1)的兩邊取對(duì)數(shù)后，公式(1)變?yōu)楣?2)。對(duì)于所有的探測(cè)路徑P和網(wǎng)絡(luò)鏈路L構(gòu)成的集合，公式(2)可變?yōu)楣?3)。如果令Yi=lgPri，Xj=lglrj，則公式(3)可簡化為公式(4)。由于探測(cè)路徑由網(wǎng)絡(luò)鏈路組成，矩陣A屬于列不滿秩的矩陣，所以，矩陣A不存在唯一解，不能在已知路徑通過率、路徑與鏈路關(guān)系的條件下，計(jì)算出每條鏈路的通過率。

(1)

(2)

{lgPr1,lgPr2,…,lgPrM}=

(3)

Y=AX.

(4)

2 網(wǎng)絡(luò)鏈路丟包率推理算法

2.1 網(wǎng)絡(luò)模型化簡

(5)

(6)

2.2 鏈路擁塞推理模型構(gòu)建

圖3 基于貝葉斯網(wǎng)的鏈路擁塞推理模型Fig.3 Link congestion reasoning model based on Bayesian network

節(jié)點(diǎn)xi發(fā)生擁塞的概率p(xi)可以通過經(jīng)驗(yàn)積累或多次探測(cè)后求解兩種方式獲得[6]。因?yàn)榛谪惾~斯網(wǎng)的鏈路擁塞推理模型中的獨(dú)立鏈路序列都已發(fā)生擁塞，而且已計(jì)算出其通過率，所以，節(jié)點(diǎn)yj發(fā)生擁塞的概率p(yj)的取值為p(yj)=1.使用pro(xi)表示至少有一個(gè)獨(dú)立鏈路序列發(fā)生擁塞是由當(dāng)前鏈路xi發(fā)生擁塞而產(chǎn)生的概率，計(jì)算方法見公式(7)，其中，p(yj)表示節(jié)點(diǎn)yj發(fā)生擁塞的概率，p(xi|yj)表示節(jié)點(diǎn)yj發(fā)生擁塞是由于節(jié)點(diǎn)xi發(fā)生擁塞導(dǎo)致的概率，∏yj∈Nxi(1-p(xi|yj)p(yj))表示與當(dāng)前鏈路xi相關(guān)聯(lián)的所有獨(dú)立鏈路序列的集合都不在集合Nxi中，其中Nxi表示所有獨(dú)立鏈路序列中包含當(dāng)前鏈路xi的集合。根據(jù)貝葉斯公式，公式(7)中p(xi|yj)的計(jì)算方法如公式(8)所示。由節(jié)點(diǎn)yj的定義可知，節(jié)點(diǎn)yj代表的獨(dú)立鏈路序列是發(fā)生擁塞的鏈路序列，p(yj)=1，所以，公式(7)可以簡化為公式(9).

pro(xi)=1-∏yj∈Nxi(1-p(xi|yj)p(yj)).

(7)

(8)

pro(xi)=1-∏yj∈Nxi(1-p(xi|yj)) .

(9)

2.3 鏈路擁塞概率排序

(10)

2.4 鏈路丟包率推理

(11)

2.5 算法步驟及偽代碼

本文提出的基于鏈路內(nèi)在相關(guān)性的IP網(wǎng)絡(luò)擁塞鏈路丟包率推斷算法偽代碼如下。

輸入：路徑集合P={P1,P2,…,Pi}，鏈路集合L={l1,l2,…,lj}，路由矩陣A，路徑通過率Yi，

輸出：鏈路通過率Xj

1) 計(jì)算公式(8)求解p(xi|yj)；

2) 使用{x1,x2,…,xu}、{y1,y2,…,yv}、p(xi|yj)建立推理模型；

3) 計(jì)算公式(10)求解CCR(xi)；

3 性能分析

3.1 實(shí)驗(yàn)環(huán)境

本文使用網(wǎng)絡(luò)拓?fù)洚a(chǎn)生工具Brite生成Waxman，Barabasi-Albert，Hierarchical三種冪率網(wǎng)絡(luò)拓?fù)鋄9]。其中，Waxman網(wǎng)絡(luò)拓?fù)涞奶攸c(diǎn)是端到端路徑經(jīng)過較多的鏈路。 Barabasi-Albert網(wǎng)絡(luò)拓?fù)涞奶攸c(diǎn)是端到端路徑經(jīng)過較少的鏈路。Hierarchical網(wǎng)絡(luò)拓?fù)洳捎梅旨?jí)的層次型網(wǎng)絡(luò)特性。網(wǎng)絡(luò)拓?fù)涞木W(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)設(shè)置為500，每種實(shí)驗(yàn)數(shù)據(jù)采用20次實(shí)驗(yàn)結(jié)果的平均值。采用文獻(xiàn)[10]中提出的LLRD1模型實(shí)現(xiàn)鏈路的丟包模型。LLRD1模型中的正常鏈路取值服從[0,0.05)的均勻分布、擁塞鏈路取值服從[0.05,0.15]的均勻分布。

通過對(duì)已有研究分析可知，算法LABLA[5]，算法NTSPA[8]與本文解決的問題相同，并且是已知算法中性能較好的算法。為了分析算法性能，本文從鏈路通過率絕對(duì)誤差ELPRA(Link pass rate absolute error，LPRAE)(公式12)、擁塞鏈路檢測(cè)率RCLD(congestion linkdetection rate,CLDR)(公式13)、擁塞鏈路誤判率RCLFP(congestion linkfalse positive rate,CLFPR)(公式14)三個(gè)方面對(duì)算法進(jìn)行分析。評(píng)估的公式中，α表示鏈路的真實(shí)通過率，β表示算法推理出的鏈路的通過率，ζ表示真實(shí)的擁塞鏈路，ψ表示算法推理出的擁塞鏈路。

ELPAA=|α-β| .

(12)

(13)

(14)

3.2 性能分析

3.2.1鏈路通過率絕對(duì)誤差

為了分析鏈路通過率絕對(duì)誤差的分布情況，本文將3種算法求解的誤差值與特定的誤差取值進(jìn)行比較，以結(jié)果值占比RRV(Result-value ratio，RVR)來衡量各個(gè)區(qū)間誤差值的分布情況。其中RRV表示各個(gè)結(jié)果值出現(xiàn)次數(shù)占總的結(jié)果值出現(xiàn)次數(shù)的比例，如公式(15)所示，其中，μ表示某個(gè)結(jié)果值出現(xiàn)的次數(shù)，υ表示所有結(jié)果值出現(xiàn)的次數(shù)。

(15)

圖4中顯示了三種算法的鏈路通過率絕對(duì)誤差的結(jié)果值占比，X軸表示鏈路通過率絕對(duì)誤差均值，Y軸表示鏈路通過率絕對(duì)誤差的結(jié)果值占比(%)。三種算法的鏈路通過率絕對(duì)誤差<0.005的結(jié)果值占比都大于98%，三種算法的鏈路通過率絕對(duì)誤差<0.05的結(jié)果值占比都約為99%，說明3種算法的鏈路通過率絕對(duì)誤差效果都較好。

圖4 鏈路通過率絕對(duì)誤差的結(jié)果值占比Fig.4 Comparison of theresult value ratio of the link pass rate absolute error

3.2.2擁塞鏈路檢測(cè)率

圖5中顯示了網(wǎng)絡(luò)擁塞率從5%增加到15%時(shí)，3種算法的擁塞鏈路檢測(cè)率。其中，X軸表示網(wǎng)絡(luò)擁塞率，Y軸表示擁塞鏈路檢測(cè)率。由圖可知，隨著網(wǎng)絡(luò)擁塞概率的增加，三種算法的擁塞鏈路檢測(cè)率都在降低，但是算法NTSPA降低較多，算法LICA的擁塞鏈路檢測(cè)率比較穩(wěn)定。算法LICA的擁塞鏈路檢測(cè)率約為96.3%，算法LABLA和算法NTSPA的擁塞鏈路檢測(cè)率約為94.7%和91.5%，所以，在擁塞鏈路檢測(cè)率方面，本文算法LICA取得了較高的檢測(cè)率。

圖5 擁塞鏈路檢測(cè)率比較Fig.5 Comparison of congestion link detection rates

3.2.3擁塞鏈路誤判率

圖6中顯示了網(wǎng)絡(luò)擁塞率從5%增加到15%時(shí)，3種算法的擁塞鏈路誤判率。其中，X軸表示網(wǎng)絡(luò)擁塞率，Y軸表示擁塞鏈路誤判率。由圖可知，隨著網(wǎng)絡(luò)擁塞概率的增加，3種算法的擁塞鏈路誤判率都在增加，但是算法LICA的擁塞鏈路誤判率比較穩(wěn)定。算法LICA的擁塞鏈路誤判率約為3.5%，算法LABLA和算法NTSPA的擁塞鏈路誤判率分別為4.6%和5.5%，所以，在擁塞鏈路誤判率方面，本文算法LICA取得了較低的誤判率。

圖6 擁塞鏈路誤判率比較Fig.6 Comparison of congestion link error rates

4 結(jié)束語

通過對(duì)網(wǎng)絡(luò)鏈路丟包率推理的已有研究分析可知，已有研究通過假設(shè)來選擇不丟包鏈路，并且網(wǎng)絡(luò)拓?fù)浔容^復(fù)雜。為解決此問題，本文提出了基于鏈路內(nèi)在相關(guān)性的IP網(wǎng)絡(luò)擁塞鏈路丟包率推斷算法。通過性能分析可知，相比算法LABLA和算法NTSPA，本文算法取得了較好的擁塞鏈路推理效果。下一步研究中，將優(yōu)化本文的網(wǎng)絡(luò)模型和推理算法，用于解決多域環(huán)境下的鏈路丟包率推理問題。