基于Bayesian網(wǎng)IP網(wǎng)絡(luò)擁塞鏈路定位算法

周 欣，周 巍

(西北工業(yè)大學(xué)自動(dòng)化學(xué)院，電子信息學(xué)院 西安 710072)

基于Bayesian網(wǎng)IP網(wǎng)絡(luò)擁塞鏈路定位算法

周 欣，周 巍

(西北工業(yè)大學(xué)自動(dòng)化學(xué)院，電子信息學(xué)院 西安 710072)

在借助E2E路徑性能主動(dòng)探測(cè)技術(shù)進(jìn)行內(nèi)部擁塞鏈路推理的網(wǎng)絡(luò)層析成像方法中，傳統(tǒng)的利用路徑探測(cè)計(jì)算鏈路丟包率的方法涉及線性方程組求逆，其計(jì)算量過(guò)大可能導(dǎo)致算法失效。對(duì)此，該文提出一種基于布爾代數(shù)的IP網(wǎng)絡(luò)擁塞鏈路定位算法，通過(guò)對(duì)求解先驗(yàn)概率的線性方程組構(gòu)造滿秩系數(shù)矩陣，從而計(jì)算出各鏈路擁塞先驗(yàn)概率，再借助貝葉斯最大后驗(yàn)概率算法推理定位當(dāng)前時(shí)刻擁塞鏈路集合。實(shí)驗(yàn)驗(yàn)證了該算法的有效性及準(zhǔn)確性。

貝葉斯最大后驗(yàn)概率; Boolean代數(shù); 擁塞鏈路推理; IP網(wǎng)絡(luò)

如何在網(wǎng)絡(luò)中進(jìn)行快速故障定位進(jìn)而保障業(yè)務(wù)的正常運(yùn)作，成為IP網(wǎng)絡(luò)故障管理的核心問(wèn)題。根據(jù)端到端的測(cè)量來(lái)推斷內(nèi)部鏈路特性的方法被稱為網(wǎng)絡(luò)Tomography方法，并根據(jù)求解方式不同分為兩類：第一類需要在廣播探測(cè)數(shù)據(jù)包之間存在很強(qiáng)的時(shí)間相關(guān)性[1-2]，并進(jìn)行矩陣求逆；第二類利用解決布爾代數(shù)求逆的方法推導(dǎo)網(wǎng)絡(luò)中擁塞鏈路的分布[3-4]。在第一類中，文獻(xiàn)[5-6]利用發(fā)送多播探測(cè)數(shù)據(jù)包的方法推算網(wǎng)絡(luò)鏈路丟包率，但受到現(xiàn)實(shí)網(wǎng)絡(luò)中支持多播路由器的數(shù)量限制。此類方法與多播副本相比準(zhǔn)確率較低，開(kāi)發(fā)和管理的費(fèi)用卻很高；同時(shí)計(jì)算鏈路丟包率的迭代算法應(yīng)用于大規(guī)模網(wǎng)絡(luò)中的實(shí)時(shí)代價(jià)過(guò)高。在第二類方法中則是采用不相關(guān)的端到端測(cè)量值來(lái)識(shí)別擁塞鏈路。這里通常要假設(shè)所有鏈路具有相同的擁塞先驗(yàn)概率0P，且0P比較小。但在實(shí)際網(wǎng)絡(luò)環(huán)境中，每個(gè)鏈路具有的擁塞概率不可能都相同，且當(dāng)0P較大時(shí)此類算法的結(jié)果也比較差[4]。文獻(xiàn)[7]利用ICMP回送請(qǐng)求來(lái)推斷丟包率，但由于安全和性能等原因使得許多路由器限制了對(duì)該類請(qǐng)求的反映，因此實(shí)時(shí)性較差。

針對(duì)以上問(wèn)題，本文使用一段時(shí)間內(nèi)多個(gè)快照求路徑丟包率，再利用一種基于貝葉斯網(wǎng)絡(luò)的擁塞鏈路定位算法(Bayesian network–based congested link position algorithm, BNCLPA)獲得鏈路擁塞先驗(yàn)概率，然后在下一次快照中使用最大后驗(yàn)估計(jì)(MAP)尋找擁塞鏈路。

1 網(wǎng)絡(luò)和性能模型

1.1 網(wǎng)絡(luò)建模

首先，利用貝葉斯網(wǎng)絡(luò)模型有向圖g=(ν,ε)對(duì)擁塞鏈路集合定位問(wèn)題進(jìn)行建模。其中，ν表示網(wǎng)絡(luò)中的節(jié)點(diǎn)，ε表示節(jié)點(diǎn)間的通信鏈路，數(shù)量分別為nν=|ν|和ne=|ε|；VB表示所有優(yōu)勢(shì)點(diǎn)的集合且 nB為其中的點(diǎn)數(shù)，Ps,t為從源點(diǎn)s到目的節(jié)點(diǎn)t所經(jīng)過(guò)的路徑，表示優(yōu)勢(shì)點(diǎn)之間路徑的集合且其中的路徑數(shù)為nP=nB(nB?1)=|P|。對(duì)于一個(gè)已知的g=(ν,ε) 和 P，按照下述方法計(jì)算選路矩陣D(nP×ne)：若路徑Pi包含鏈路ej則Dij=1，否則Dij=0。D的一行對(duì)應(yīng)一條路徑，一列對(duì)應(yīng)一條鏈路。若D的某一列為全零，則丟棄這些列得到矩陣D(nP×nc)，nc表示非零鏈路的數(shù)量且 nc≤ne。εc表示至少被P中的一條路徑所包含的鏈路集合且|εc|=nc。圖1所示的IP網(wǎng)絡(luò)共有9個(gè)節(jié)點(diǎn)和9條鏈路，其中節(jié)點(diǎn)1和2為源節(jié)點(diǎn)，節(jié)點(diǎn)6～8為目的節(jié)點(diǎn)，路徑與鏈路的對(duì)應(yīng)關(guān)系如表1所示。

圖1 IP網(wǎng)絡(luò)

表1 路徑與鏈路關(guān)系

根據(jù)表1可以得到選路矩陣為：

1.2 性能建模

若已知網(wǎng)絡(luò)拓?fù)浜投说蕉说穆窂絹G包率，則鏈路丟包率和路徑丟包率之間為線性關(guān)系：

式中，φi表示路徑Pi的傳輸率；φek表示鏈路ek的傳輸率。為了確定鏈路的傳輸率，需要求解式(3)。由于許多網(wǎng)絡(luò)中的D不是滿秩矩陣，即其秩r(D)＜min(nP,nc)，所以式(3)的解不唯一。

本文的目的是識(shí)別擁塞鏈路，因此可以做以下改進(jìn)：閾值tl表示根據(jù)應(yīng)用程序指定的極限值，當(dāng)φek≥tl時(shí)認(rèn)為鏈路ek是連通的，否則鏈路ek就是擁塞的；變量yi表示路徑iP的狀態(tài)，當(dāng)iP是通的yi=0，當(dāng) Pi是擁塞的yi=1；變量xk表示鏈路ek的狀態(tài)，當(dāng)ek是通的xk=0，當(dāng)ek是擁塞的xk=1。

圖2 代數(shù)模型向布爾模型轉(zhuǎn)化

建立一個(gè)布爾線性代數(shù)方程組：

式中，‘V’表示二進(jìn)制最大操作；‘?’表示通常的乘法操作。式(4)可以用向量表示為：

式中，dk表示矩陣D的第k個(gè)列向量。圖2說(shuō)明了從線性代數(shù)到布爾代數(shù)的轉(zhuǎn)換。圖中e1=SA是好的鏈路且φe1=1，e2=AB及e3=AC都是擁塞鏈路且φe2=0.8、φe3=0.8。令t1=0.9，則tp=0.92=0.81，路徑1P(S到B)和P2(S到C)都是擁塞的。

在布爾代數(shù)中，路徑傳輸率和鏈路傳輸率之間是線性關(guān)系，而鏈路狀態(tài)和路徑狀態(tài)也呈線性關(guān)系。一般來(lái)說(shuō)，當(dāng)且僅當(dāng)D的所有列在布爾代數(shù)中都線性無(wú)關(guān)時(shí)此方程才有唯一的解，但實(shí)際中很難滿足。因此，需要利用網(wǎng)絡(luò)中鏈路的其他信息來(lái)找到式(4)最有可能的解。首先，用向量表示鏈路狀態(tài)概率，在理論上可以從端到端的測(cè)量中獲得p。本文提出了一種利用BNCLP算法從較少的快照中估算p，再把p作為一個(gè)鏈路狀態(tài)的先驗(yàn)概率，利用已知信息尋求確定真正擁塞鏈路的方法。

2 BNCLPA算法

BNCLPA算法的原理框圖如圖3所示。

圖3 BNCLPA算法原理框圖

2.1 先驗(yàn)概率學(xué)習(xí)

首先，設(shè)鏈路概率向量為p，檢測(cè)網(wǎng)路鏈路集合的概率為Pp，X是nc維隨機(jī)二進(jìn)制向量，Y為nP維隨機(jī)二進(jìn)制向量。若鏈路狀態(tài)概率滿足對(duì)任何y有 Pp(Y=y)=P(Y=y)，則p=。為了避免傳統(tǒng)方法中使用最大期望(expectation-maximization, EM)算法求解p時(shí)的計(jì)算代價(jià)過(guò)高且不具備全局收斂性的問(wèn)題，本文利用數(shù)學(xué)期望求解的方法對(duì)式(4)進(jìn)行推導(dǎo)，求出鏈路x的概率值。

對(duì)所有1≤ i≤np，有：

由于 r(D)＜min(np, nc)，所以需通過(guò)高階矩陣空間相關(guān)特性提供更多的信息。定義Yij為二進(jìn)制隨機(jī)變量，當(dāng)路徑i及j正常時(shí)Yij=0，否則Yij=1，則：

對(duì)所有滿足1≤ i≤j≤np的(i,j)對(duì)，定義：

結(jié)合式(6)和式(7)系統(tǒng)線性方程組為：

由此可構(gòu)造滿秩矩陣。在實(shí)際網(wǎng)絡(luò)中可以化簡(jiǎn)選路矩陣來(lái)減少求解式(11)的計(jì)算復(fù)雜度。如圖1所示的IP網(wǎng)絡(luò)，若根據(jù)m次快照測(cè)得ya=0，則L1、L4、L6全部為通的，把式(2)中的矩陣D進(jìn)行化簡(jiǎn)得到：

然后進(jìn)行初等行變換得到：

根據(jù)D1和D2得到最大線性無(wú)關(guān)組組成矩陣為：

D3即式(13)中的D[1]。將D3進(jìn)行最大化操作得到：

從D4中選出一行加入到D3中，形成的滿秩矩陣D5，即為式(13)所需滿秩矩陣：

而對(duì)于式(13)，選擇D2第一行與D3構(gòu)成一個(gè)滿秩矩陣，得到式 (11)中D(2)=[0 1 0 1 1]，。通過(guò)對(duì)取逆可求得鏈路的先驗(yàn)概率p。而在nc這條鏈路中，未參與式(11)計(jì)算的鏈路的概率值為0。

2.2 擁塞鏈路定位算法

設(shè)定已知信息選路矩陣為D(np×nc)，網(wǎng)絡(luò)中np條路徑最近一次快照值為Y，已求得鏈路狀態(tài)的先驗(yàn)概率為P。首先，定義最大評(píng)分參量argmaxxPp(X=x|Y=y)為擁塞鏈路集合的最大后驗(yàn)估計(jì)，Pp(?)為條件概率，則由貝葉斯公式可得：

式中，Pp(Y=y)僅依賴網(wǎng)絡(luò)狀態(tài)檢測(cè)，與x的選擇無(wú)關(guān)，故最大評(píng)分參量可表示為：

由于鏈路狀態(tài)xk是獨(dú)立隨機(jī)變量，則：

在給定X=x，Yi=0且Dikxk=0或等價(jià)于(1?Dik)xk= 1時(shí)，有：

可知概率為1或者0。定義R為從D[1]中移除所有正常路徑行以及其對(duì)應(yīng)鏈路的所有列，Rε是R中列的集合，那么對(duì)于鏈路集合χ∈Rε，所有的擁塞路徑至少覆蓋一條鏈路在χ中，有：

取對(duì)數(shù)再移除與x的取值無(wú)關(guān)的項(xiàng)得到：

3 仿真實(shí)驗(yàn)及結(jié)果分析

對(duì)于主動(dòng)探測(cè)技術(shù)，網(wǎng)絡(luò)拓?fù)湓诤艽蟪潭壬嫌绊懥颂綔y(cè)結(jié)果，從而影響到故障診斷的結(jié)果。Brite[8]拓?fù)洚a(chǎn)生器是網(wǎng)絡(luò)仿真實(shí)驗(yàn)中常用的網(wǎng)絡(luò)拓?fù)渖晒ぞ?，它可以生?種網(wǎng)絡(luò)拓?fù)淠Ｐ蚖axman[9]、BA[10]和GLP[11]。其中BA模型和GLP模型都是冪率類型，而GLP模型更接近于實(shí)際網(wǎng)絡(luò)的結(jié)構(gòu)特征，可以較準(zhǔn)確地模擬真實(shí)IP網(wǎng)的拓?fù)淝闆r。因此，本文采用Brite產(chǎn)生的GLP模型來(lái)進(jìn)行仿真實(shí)驗(yàn)。

在仿真實(shí)驗(yàn)中，需要在不同的網(wǎng)絡(luò)擁塞層次下對(duì)算法進(jìn)行評(píng)價(jià)。本文使用丟包模型LM1[4]，其中擁塞鏈路的丟包率分布在0.05～1之間，好鏈路的丟包率在0～0.01之間。每條鏈路都有一個(gè)指定的丟包率，所以每條鏈路的實(shí)際丟包都遵循Gilbert過(guò)程，鏈路的狀態(tài)在不丟失任何數(shù)據(jù)包與丟失所有的數(shù)據(jù)包之間來(lái)回波動(dòng)。

本文利用Java語(yǔ)言中的Eclipse開(kāi)發(fā)平臺(tái)模擬端到端到探測(cè)、擁塞事件及算法推理。在求解鏈路擁塞概率pk時(shí)，考慮到式(13)中的系數(shù)矩陣是一個(gè)稀疏矩陣，采用迭代法來(lái)求解。同時(shí)，在求解pk時(shí)實(shí)現(xiàn)Java程序?qū)atlab程序的調(diào)用，以更方便有效地得到計(jì)算結(jié)果。

1) 擁塞率f對(duì)DR和FPR的影響。由Brite拓?fù)渖善鳟a(chǎn)生100個(gè)節(jié)點(diǎn)的拓?fù)洌瑩砣溌返陌俜直萬(wàn)∈[0.1,0.45]，步長(zhǎng)為0.05，連接某節(jié)點(diǎn)的總鏈路數(shù)d=7，學(xué)習(xí)先驗(yàn)概率時(shí)的快照次數(shù)m=40，擁塞鏈路的門(mén)限值t=0。從圖4中可以看出，隨著f的增加，算法的檢測(cè)率DR和誤檢率FPR會(huì)越來(lái)越低。

圖4 DR和FPR隨f的變化趨勢(shì)圖

2) 快照次數(shù)m對(duì)DR和FPR的影響。拓?fù)湟?guī)模分別為100、200和300個(gè)節(jié)點(diǎn)，m在5～100之間變化，d=7，f=0.1，t=0。從圖5中可以看出：當(dāng)m＜30時(shí)，DR較低而FPR較高，說(shuō)明快照次數(shù)太少無(wú)法準(zhǔn)確得到鏈路的先驗(yàn)擁塞概率，導(dǎo)致算法的DR較低而FPR較高，因此在推斷網(wǎng)絡(luò)故障時(shí)快照次數(shù)不能低于30；但是m并不是越大越好，若m過(guò)大如超過(guò)40后，DR并不會(huì)繼續(xù)升高而FPR也不會(huì)降低，同時(shí)主動(dòng)測(cè)試時(shí)發(fā)包數(shù)量過(guò)多會(huì)導(dǎo)致網(wǎng)絡(luò)負(fù)載增加、時(shí)間成本過(guò)大，影響算法的時(shí)效性。因此，在學(xué)習(xí)鏈路的先驗(yàn)擁塞概率時(shí)，應(yīng)使30≤m≤40。

圖5 不同拓?fù)湟?guī)模的DR和FPR隨m的變化趨勢(shì)圖

3) 拓?fù)湟?guī)模對(duì)DR和FPR的影響。生成的網(wǎng)絡(luò)拓?fù)湟?guī)模在50～350之間變化，f=0.1，t=0，d=7， m=30。從圖6可以看出：DR隨著拓?fù)湟?guī)模的增大而呈下降趨勢(shì)，并在一定的范圍內(nèi)有所波動(dòng)，但是下降的幅度不大，速度也不是很快；而FPR隨著拓?fù)湟?guī)模的增大，而呈上升趨勢(shì)，并在一定的范圍內(nèi)有所波動(dòng)，但是上升的幅度不大，且上升的速度也不是很快。這說(shuō)明BNPDA算法對(duì)拓?fù)湟?guī)模的變化具有較好的穩(wěn)定性。

圖6 拓?fù)湟?guī)模對(duì)DR和FPR的影響

4 結(jié) 束 語(yǔ)

針對(duì)現(xiàn)有方法在網(wǎng)絡(luò)鏈路故障診斷方面的不足，本文提出了一種基于貝葉斯網(wǎng)的故障診斷算法BNPDA。該方法采用主動(dòng)測(cè)量方式測(cè)量網(wǎng)絡(luò)端到端的性能，需要在被測(cè)網(wǎng)絡(luò)中部署探針硬件設(shè)備；同時(shí)主動(dòng)測(cè)量時(shí)所發(fā)的探測(cè)包也會(huì)在網(wǎng)絡(luò)中產(chǎn)生新的流量，增加網(wǎng)絡(luò)負(fù)載。如何在達(dá)到監(jiān)測(cè)網(wǎng)絡(luò)的情況下，盡量減少探針的部署和探針的發(fā)包數(shù)量，以減少對(duì)網(wǎng)絡(luò)的影響以及監(jiān)測(cè)系統(tǒng)的維護(hù)代價(jià)，同時(shí)獲取更多的網(wǎng)絡(luò)信息是今后研究的重點(diǎn)之一。

[1] OGINO N, KITAHARA T, ARAKAWAET S, et al. Decentralized Boolean network tomography based onnetwork partitioning[C]//In NOMS’16: IEEE/IFIP Network Operations and Management Symposium. Istanbul: IEEE, 2016: 162-170.

[2] DENG K, LI Y, ZHU W, et al. Fast parameter estimation in loss tomography for networks of general topology[J]. The Annals of Applied Statistics, 2016, 10(1): 144-164.

[3] DUFFIELD N G. Network tomography of binary network performance characteristics[J]. IEEE Trans on Information Theory, 2006, 52(12): 5373-5388.

[4] BATSAKIS A, MALIK T, TERZIS A. Practical passive lossy link inference[C]//Proc of PAM 2005: 6th International Workshop. Boston: Springer Berlin Heidelberg, 2005, 3431: 362-367.

[5] NGUYEN H X, THIRAN P . The Boolean solution to the congested IP link location problem: Theory and practice[C]//Proceedings of IEEE INFOCOM’07: 26th Annual IEEE Conference on Computer Communications. Alaska: IEEE, 2007: 2117-2125.

[6] DUFFIELD N G, PRESTI F L, PAXSON V, et al. Inferring link loss using striped unicast probes[C]//Proceeding of the IEEE INFOCOM’01: Conference on Computer Communications. [S.l.]: IEEE Communications Society, 2001: 915-923.

[7] MAHAJAN R, SPRING N, WETHERALL D, et al. User-level internet path diagnosis[C]//Proceedings of the 19th ACM Symposium on Operating Systems Principles. New York: ACM, 2003: 106-119.

[8] MEDINA A, LAKHINA A, MATTA I, et al. BRITE: an approach to universal topology gerneration[C]//Proceedings of MASCOTS: Proceedings Ninth International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems. Washington: IEEE, 2001: 346-353.

[9] WAXMAN B M. Routing of multipoint connections[J]. IEEE Journal of Selected Areas in Communication, 1988, 6(9): 1617-1622.

[10] BARABASI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.

[11] PALMER C R, STTEFFAN J G. Generating network topologies that obey power laws[C]//Proc of the GLOBECOM 2000: Global Telecommunications Conference. San Francisco: IEEE, 2000: 434-438.

編 輯 漆 蓉

IP Network Congested Link Location Algorithm Based on Bayesian Network

ZHOU Xin and ZHOU Wei

(School of Automation, School of Electronics and Information, Northwestern Polytechnical University Xi’an 710072)

In the method of end-to-end (E2E) path performance active detection (network tomography), the link loss rate solution methods involve the inverse of linear equations, so its large computation complexity may lead to failure. This paper proposes a new congestion link location algorithm based Boolean model. First the nonsingular coefficient matrix of the linear system for solving prior probability is formed; then the prior probability of link congestion is calculated. Finally, based on Bayesian maximum a posteriori probability (MAP) estimator, the set of congested links can be located. The validity and accuracy of this algorithm is verified by experiments.

Bayesian MAP; Boolean model; congested link location; IP network

TP393.09

A

10.3969/j.issn.1001-0548.2017.03.010

2016 ? 06 ? 23；

2016 ? 10 ? 11

國(guó)家自然科學(xué)基金(61602383)；中央高校基本科研業(yè)務(wù)費(fèi)(3102016ZY024)

周欣(1982 ? )，女，博士，主要從事信息處理方面的研究.