基于變結(jié)構(gòu)離散動(dòng)態(tài)貝葉斯IP網(wǎng)絡(luò)擁塞鏈路推理

陳宇，周巍，段哲民，錢葉魁，趙鑫

(1. 西北工業(yè)大學(xué)電子信息學(xué)院，陜西 西安 710072；2. 鄭州航空工業(yè)管理學(xué)院電子通信工程學(xué)院，河南 鄭州 450015；3. 通信網(wǎng)信息傳輸與分發(fā)技術(shù)重點(diǎn)實(shí)驗(yàn)室，河北 石家莊050000；4. 解放軍防空兵學(xué)院導(dǎo)彈系，河南 鄭州 450052；5. 解放軍防空后學(xué)院彈炮一體系，河南 鄭州 450052)

基于變結(jié)構(gòu)離散動(dòng)態(tài)貝葉斯IP網(wǎng)絡(luò)擁塞鏈路推理

陳宇1,2,3，周巍1，段哲民1，錢葉魁4，趙鑫5

(1. 西北工業(yè)大學(xué)電子信息學(xué)院，陜西 西安 710072；2. 鄭州航空工業(yè)管理學(xué)院電子通信工程學(xué)院，河南 鄭州 450015；3. 通信網(wǎng)信息傳輸與分發(fā)技術(shù)重點(diǎn)實(shí)驗(yàn)室，河北 石家莊050000；4. 解放軍防空兵學(xué)院導(dǎo)彈系，河南 鄭州 450052；5. 解放軍防空后學(xué)院彈炮一體系，河南 鄭州 450052)

針對(duì)CLINK算法在路由改變時(shí)擁塞鏈路推理性能下降的問題，建立一種變結(jié)構(gòu)離散動(dòng)態(tài)貝葉斯網(wǎng)模型，通過引入馬爾可夫性及時(shí)齊性假設(shè)簡(jiǎn)化該模型，并基于簡(jiǎn)化模型提出一種IP網(wǎng)絡(luò)擁塞鏈路推理算法（VSDDB）。利用逐次超松弛迭代算法求解鏈路擁塞先驗(yàn)概率唯一解，基于貝葉斯最大后驗(yàn)準(zhǔn)則，借助加權(quán)啟發(fā)式貪心搜索算法推理擁塞鏈路集合。實(shí)驗(yàn)驗(yàn)證了VSDDB算法具有更好的推理性能。

IP網(wǎng)絡(luò)；變結(jié)構(gòu)離散動(dòng)態(tài)貝葉斯；擁塞鏈路推理；Boolean模型

1 引言

隨著IP網(wǎng)絡(luò)規(guī)模的迅速擴(kuò)大[1]，網(wǎng)絡(luò)結(jié)構(gòu)日益多樣，多鏈路擁塞現(xiàn)象頻有發(fā)生，人工定期檢查已不能適應(yīng)當(dāng)前大規(guī)模網(wǎng)絡(luò)的需要。因此，借助先進(jìn)的手段進(jìn)行有效、準(zhǔn)確的IP網(wǎng)絡(luò)內(nèi)部擁塞鏈路推理對(duì)網(wǎng)絡(luò)維護(hù)和管理非常重要。

基于ICMP(Internet control message protocol)的主動(dòng)探測(cè)技術(shù)[2]僅通過部分端到端(E2E,end-to-end)路徑的多次快照(snapshots)獲取E2E路徑的性能及拓?fù)湫畔ⅲ柚惾~斯理論等推理待測(cè)IP網(wǎng)絡(luò)中各鏈路性能的方法較基于SNMP(simple network management protocol)的被動(dòng)探測(cè)技術(shù)具有實(shí)時(shí)性好、需獲取的數(shù)據(jù)量小且不涉及用戶隱私等優(yōu)點(diǎn)，被廣泛應(yīng)用于互聯(lián)網(wǎng)內(nèi)部鏈路性能測(cè)量中。自 1996年Vardi首次提出在互聯(lián)網(wǎng)鏈路性能推理中使用類似醫(yī)學(xué)層析掃描(tomography)技術(shù)以來，借助主動(dòng)探測(cè)的tomography技術(shù)推理IP網(wǎng)絡(luò)內(nèi)部鏈路性能的方法主要包括以下兩大類。第一類方法使用多播方式[3]或多簇單播模擬多播的方式[4～6]，通過構(gòu)建待測(cè)IP網(wǎng)絡(luò)系統(tǒng)線性方程組求解各鏈路分組丟失率數(shù)值。此類方法需投入復(fù)雜的基礎(chǔ)設(shè)施建設(shè)[7]，且對(duì)各E2E路徑性能探測(cè)的時(shí)間相關(guān)性要求非常高，并假設(shè)鏈路性能服從某種特定分布或具有時(shí)空獨(dú)立性和平穩(wěn)性等[8]。出于安全等因素，當(dāng)前互聯(lián)網(wǎng)中大部分路由器對(duì)單播的支持度高于多播，時(shí)間相關(guān)性難以保證，且tomography技術(shù)是借助盡可能少的E2E路徑性能測(cè)量結(jié)果推理網(wǎng)絡(luò)內(nèi)部各鏈路性能，常導(dǎo)致構(gòu)建的系統(tǒng)線性方程組系數(shù)矩陣欠定，無法求得唯一解。另外，隨著IP網(wǎng)絡(luò)規(guī)模的擴(kuò)大，線性方程組系數(shù)矩陣的維數(shù)增大，求解中涉及復(fù)雜的求逆計(jì)算，甚至導(dǎo)致算法失效。第二類方法將各E2E探測(cè)路徑及鏈路性能借助 Boolean代數(shù)值進(jìn)行表示[5,9,10]。Nguyen[11]、Padmanabhan[9]和 Duffield[5]等提出借助不相關(guān)的 E2E路徑性能探測(cè)，推理 IP網(wǎng)絡(luò)中最有可能發(fā)生擁塞的鏈路集合，簡(jiǎn)化了鏈路性能推理過程。文獻(xiàn)[11]提出了經(jīng)典的鏈路擁塞推理算法CLINK，較先前不使用先驗(yàn)概率的MCMC(Monte Carlo Markov chain)[9]算法及使用一致先驗(yàn)概率的SCFS (smallest consistent failure set algorithm)[5]算法在推理性能上有較大程度的提高。

文獻(xiàn)[11]同時(shí)指出，IP網(wǎng)絡(luò)的路由改變會(huì)影響推理性能，其認(rèn)為鏈路擁塞會(huì)持續(xù)數(shù)個(gè)小時(shí)，但未考慮路由變化對(duì)當(dāng)前鏈路推理性能帶來的影響。喬焰等[12]將路由變化作為噪聲干擾，通過在擁塞鏈路推理貝葉斯網(wǎng)模型中加入轉(zhuǎn)移概率，提高了推理精度。但是，由于IP網(wǎng)絡(luò)各AS區(qū)域多采用動(dòng)態(tài)路由算法(如OSPF)，對(duì)IP網(wǎng)絡(luò)進(jìn)行擁塞鏈路推理時(shí)，路由將根據(jù)鏈路狀態(tài)發(fā)生動(dòng)態(tài)改變，造成推理過程中IP網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化，從而引起IP網(wǎng)絡(luò)構(gòu)建的貝葉斯網(wǎng)推理模型的結(jié)構(gòu)變化，不僅在參數(shù)上發(fā)生改變。因此，上述方法均不能對(duì)動(dòng)態(tài)路由IP網(wǎng)絡(luò)進(jìn)行準(zhǔn)確建模，擁塞鏈路推理將產(chǎn)生一定誤差。另外，多鏈路擁塞造成的IP網(wǎng)絡(luò)高時(shí)延和高分組丟失現(xiàn)象，還有可能涉及違反 SLA(service-level agreement)等相關(guān)服務(wù)等級(jí)協(xié)定[1]。因此，網(wǎng)絡(luò)管理者需要及時(shí)準(zhǔn)確地定位擁塞鏈路，并采取相應(yīng)的處理。

綜上，研究者大多從靜態(tài)路由入手簡(jiǎn)化對(duì) IP網(wǎng)絡(luò)擁塞鏈路的推理過程，未充分考慮 IP網(wǎng)絡(luò)動(dòng)態(tài)路由算法策略對(duì)算法推理性能造成的影響。針對(duì)此問題，本文建立一種變結(jié)構(gòu)離散動(dòng)態(tài)貝葉斯(VSDDB,variable structure discrete dynamic Bayesian)網(wǎng)模型，通過引入馬爾可夫性假設(shè)及時(shí)齊性假設(shè)簡(jiǎn)化該模型；基于該簡(jiǎn)化模型提出一種 IP網(wǎng)絡(luò)擁塞鏈路推理新算法VSDDB，提高了動(dòng)態(tài)路由算法下IP網(wǎng)絡(luò)擁塞鏈路推理精度。VSDDB算法針對(duì)系統(tǒng)線性方程組系數(shù)矩陣的奇異性及稀疏性問題，通過對(duì)系數(shù)矩陣去相關(guān)、補(bǔ)滿秩，利用逐次超松弛迭代算法求解擁塞鏈路先驗(yàn)概率唯一解；最后，基于貝葉斯最大后驗(yàn)(MAP,maximum a-posterior)準(zhǔn)則，提出一種加權(quán)啟發(fā)式貪心搜索算法推理當(dāng)前IP網(wǎng)絡(luò)中的擁塞鏈路集合。

本文的主要貢獻(xiàn)包括以下3個(gè)方面：1)建立動(dòng)態(tài)路由IP網(wǎng)絡(luò)下的變結(jié)構(gòu)離散動(dòng)態(tài)貝葉斯網(wǎng)模型，通過引入馬爾可夫性假設(shè)及時(shí)齊性假設(shè)簡(jiǎn)化該模型；2)基于該簡(jiǎn)化模型提出一種IP網(wǎng)絡(luò)擁塞鏈路推理新算法VSDDB，有效解決動(dòng)態(tài)路由IP網(wǎng)絡(luò)中的多擁塞鏈路推理問題；3)模擬、仿真及實(shí)測(cè)網(wǎng)絡(luò)實(shí)驗(yàn)比較驗(yàn)證了本文提出新算法VSDDB的推理性能優(yōu)于經(jīng)典CLINK算法。

2 網(wǎng)絡(luò)模型及相關(guān)定義

2.1 貝葉斯網(wǎng)模型

為了方便對(duì)IP網(wǎng)絡(luò)內(nèi)部的擁塞鏈路推理，簡(jiǎn)要描述 IP網(wǎng)絡(luò)擁塞鏈路推理時(shí)需構(gòu)建的貝葉斯網(wǎng)模型。貝葉斯網(wǎng)模型是一種表示因果關(guān)系的有向無環(huán)圖模型 G=(ν,ε)。其中，ν代表節(jié)點(diǎn)，ε代表連接節(jié)點(diǎn)的有向邊。本文基于引言所述的主動(dòng)探測(cè)技術(shù)中的第二類方法，借助Boolean代數(shù)模型對(duì)動(dòng)態(tài)路由IP網(wǎng)絡(luò)進(jìn)行擁塞鏈路推理。首先，對(duì) IP網(wǎng)絡(luò)中各E2E路徑及途經(jīng)鏈路的狀態(tài)變量作出如下定義。

定義1IP網(wǎng)絡(luò)中各E2E路徑的狀態(tài)變量集合為各E2E路徑途經(jīng)鏈路的狀態(tài)變量集合為路徑擁塞時(shí)，yi=1；反之， yi=0。同理，鏈路擁塞時(shí)， xj=1；反之，xj=0。

其中，np為待測(cè)IP網(wǎng)絡(luò)E2E路徑總數(shù)，nc為E2E路徑途經(jīng)鏈路總數(shù)。在構(gòu)建IP網(wǎng)絡(luò)擁塞鏈路推理貝葉斯網(wǎng)模型時(shí)，Y為模型中的觀測(cè)變量(證據(jù)節(jié)點(diǎn))，X為隱藏變量(隱藏節(jié)點(diǎn))，各E2E路徑及途經(jīng)鏈路的連接關(guān)系構(gòu)成模型的有向邊。如探測(cè)出E2E路徑Pi(i=1,2,…,np)擁塞( yi=1)，則對(duì)IP網(wǎng)絡(luò)擁塞路徑途經(jīng)的各鏈路擁塞推理問題可轉(zhuǎn)化為已知貝葉斯網(wǎng)模型中的觀測(cè)變量Y，對(duì)隱藏變量X最有可能的一組取值的選取問題。貝葉斯網(wǎng)模型節(jié)點(diǎn)聯(lián)合概率為

其中， pa(xj)為節(jié)點(diǎn)xj的父節(jié)點(diǎn)。根據(jù)各E2E路徑探測(cè)性能，借助貝葉斯網(wǎng)模型推理出最有可能發(fā)生擁塞的鏈路集合，可利用最大評(píng)分參量(argmax)進(jìn)行求解

其中，P( Y)僅與網(wǎng)絡(luò)狀態(tài)及探測(cè)結(jié)果有關(guān)，與鏈路選取無關(guān)，則式(2)可簡(jiǎn)化為

引理1[13]取最大值時(shí)，當(dāng)滿足如下條件：1)如果 yi=0，且 Dij=1，則 xi=0；2)如果 yi=1，則必然存在至少一個(gè) xi=1，使 Dij=1。

由于E2E路徑性能正常時(shí)，該路徑途經(jīng)各鏈路的性能也正常；路徑擁塞時(shí)，該路徑途經(jīng)各鏈路中至少有一條鏈路發(fā)生了擁塞。故E2E路徑與途經(jīng)各鏈路之間應(yīng)存在如式(4)所示的概率關(guān)系。

因此，在推理IP網(wǎng)絡(luò)內(nèi)部擁塞鏈路時(shí)，正常路徑途經(jīng)的各鏈路必為正常狀態(tài)，不必再進(jìn)行性能推理。即可將正常路徑對(duì)應(yīng)的觀測(cè)變量yi及相關(guān)隱藏變量xj（途經(jīng)鏈路狀態(tài)變量）以及有向邊從IP網(wǎng)絡(luò)構(gòu)建的貝葉斯網(wǎng)推理模型中移除。

定義 2將觀測(cè)變量、相關(guān)隱藏變量及連接有向邊從貝葉斯網(wǎng)模型中移除，剩余的貝葉斯網(wǎng)模型為 IP網(wǎng)絡(luò)擁塞鏈路推理中的擁塞貝葉斯網(wǎng)模型。

2.2 變結(jié)構(gòu)離散動(dòng)態(tài)貝葉斯網(wǎng)模型

為了構(gòu)建動(dòng)態(tài)路由算法下 IP網(wǎng)絡(luò)擁塞鏈路推理的貝葉斯網(wǎng)模型，首先引入如下定義。

定義 3如果組成一個(gè)離散動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)，不同時(shí)刻的離散靜態(tài)貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)或參數(shù)發(fā)生變化，則這類離散動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)稱為變結(jié)構(gòu)離散動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)[14]。

對(duì)待測(cè)IP網(wǎng)絡(luò)各E2E路徑N次snapshots，學(xué)習(xí)鏈路擁塞先驗(yàn)概率的過程中，如IP網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生n次改變，則可得到n個(gè)靜態(tài)貝葉斯網(wǎng)模型，將每個(gè)靜態(tài)貝葉斯網(wǎng)模型對(duì)應(yīng)時(shí)間(snapshots次數(shù))間隔看作一個(gè)時(shí)間片(T)。因此，根據(jù)定義3，對(duì)動(dòng)態(tài)路由 IP網(wǎng)絡(luò)構(gòu)建的擁塞鏈路推理變結(jié)構(gòu)離散動(dòng)態(tài)貝葉斯網(wǎng)模型可由多個(gè)時(shí)間片下的靜態(tài)貝葉斯網(wǎng)模型組成。為了簡(jiǎn)化推理過程，引入 2個(gè)基本假設(shè)[15]。

假設(shè) 1一階馬爾可夫性假設(shè)，即給出當(dāng)前系統(tǒng)狀態(tài)，將來的系統(tǒng)狀態(tài)和過去是獨(dú)立的。

假設(shè) 2時(shí)齊性假設(shè)，即各時(shí)間片中節(jié)點(diǎn)的條件概率與各時(shí)間片間的轉(zhuǎn)移概率不隨時(shí)間發(fā)生變化。

根據(jù)假設(shè)1、2，變結(jié)構(gòu)離散動(dòng)態(tài)貝葉斯網(wǎng)模型可由推理時(shí)刻前N次snapshots對(duì)應(yīng)的初始時(shí)間片T1和推理時(shí)刻時(shí)間片 T2下的靜態(tài)貝葉斯網(wǎng)模型，通過節(jié)點(diǎn)接口(共有鏈路)聯(lián)接而成。簡(jiǎn)化模型如圖1所示。

圖1 變結(jié)構(gòu)離散動(dòng)態(tài)貝葉斯網(wǎng)模型

由圖1可知，鏈路lh，lj，…，lk均存在于時(shí)間片T1和時(shí)間片T2的擁塞E2E路徑中，構(gòu)成兩時(shí)間片的節(jié)點(diǎn)接口，兩時(shí)間片下的路徑擁塞狀態(tài)變量（觀測(cè)變量）、鏈路狀態(tài)變量（隱藏變量）及拓?fù)潢P(guān)系分別構(gòu)成各時(shí)間片下的靜態(tài)貝葉斯網(wǎng)模型，由節(jié)點(diǎn)接口聯(lián)結(jié)構(gòu)成動(dòng)態(tài)路由算法下IP網(wǎng)絡(luò)擁塞鏈路推理模型。

如IP網(wǎng)絡(luò)配置為靜態(tài)路由算法策略，則在進(jìn)行擁塞鏈路推理時(shí)，N次snapshots中路由始終不發(fā)生變化，則推理模型中僅包含一個(gè)時(shí)間片下的靜態(tài)貝葉斯網(wǎng)模型。因此，本文對(duì)動(dòng)態(tài)路由算法下的 IP網(wǎng)絡(luò)構(gòu)建的變結(jié)構(gòu)離散動(dòng)態(tài)貝葉斯網(wǎng)推理模型即簡(jiǎn)化為 CLINK算法中構(gòu)建的靜態(tài)貝葉斯網(wǎng)推理模型。

2.3 IP網(wǎng)絡(luò)選路矩陣模型

IP網(wǎng)絡(luò)選路矩陣模型D的構(gòu)建方法如下定義。

定義4IP網(wǎng)絡(luò)選路矩陣D的各行為E2E路徑 Pi(i=1,2,…,np)，各列為 IP網(wǎng)絡(luò)中所有鏈路lj(j=1,2,…,nc)。按照跳數(shù)(hop)級(jí)別順序從小到大依次排列；當(dāng)某條 E2E路徑 Pi途經(jīng)某條鏈路 lj時(shí)，選路矩陣 D對(duì)應(yīng)位置處的元素值 Dij=1，否則Dij=0。

鏈路擁塞先驗(yàn)概率學(xué)習(xí)過程中，根據(jù)各E2E路徑 traceroute探測(cè)獲取的途經(jīng)鏈路，可構(gòu)建各時(shí)間片下的選路矩陣D。為了減少ping實(shí)際發(fā)分組探測(cè)的路徑數(shù)，根據(jù)矩陣特性，可對(duì)選路矩陣D去相關(guān)化簡(jiǎn)，得到矩陣 ′D，去除線性相關(guān)路徑后并不影響矩陣特性及矩陣列數(shù)(即鏈路覆蓋范圍不變)。對(duì)各E2E路徑通過ping性能探測(cè)后，在 ′D中去除正常路徑及途經(jīng)鏈路對(duì)應(yīng)的矩陣行元素及列元素，即可得到擁塞矩陣Dd，再次去相關(guān)化簡(jiǎn)后，即可得化簡(jiǎn)擁塞矩陣即鏈路擁塞先驗(yàn)概率求解系統(tǒng)線性方程組中的系數(shù)矩陣。

3 VSDDB算法

基于待測(cè) IP網(wǎng)絡(luò)構(gòu)建的變結(jié)構(gòu)離散動(dòng)態(tài)貝葉斯網(wǎng)簡(jiǎn)化模型，本文提出一種動(dòng)態(tài)路由算法下的IP網(wǎng)絡(luò)擁塞鏈路推理算法（VSDDB）。算法原理如圖2所示。

圖2 VSDDB算法設(shè)計(jì)原理

算法主要包括以下2個(gè)方面。1)各鏈路擁塞先驗(yàn)概率求解。首先，根據(jù)N次E2E路徑snapshots中的traceroute獲取到的各E2E路徑途經(jīng)鏈路，可構(gòu)建T1及 T2的選路矩陣D1及D2，通過矩陣化簡(jiǎn)可得出及；然后，根據(jù) N次 E2E路徑snapshots中的ping獲取T1及T2各E2E路徑性能探測(cè)結(jié)果，分別求解出各E2E路徑擁塞概率及并去除正常路徑及途經(jīng)鏈路在矩陣及中的對(duì)應(yīng)的行及列，再次化簡(jiǎn)后得到各擁塞矩陣及，通過去相關(guān)、補(bǔ)滿秩操作獲取及；分別構(gòu)建兩時(shí)間片下鏈路擁塞先驗(yàn)概率求解 Boolean線性方程組，及分別為兩時(shí)間片下線性方程組稀疏系數(shù)矩陣；最后，利用逐次超松弛迭代算法求解鏈路擁塞先驗(yàn)概率唯一解推理當(dāng)前時(shí)刻擁塞鏈路集合。根據(jù)當(dāng)前1次snapshots獲取擁塞路徑；然后，基于貝葉斯MAP準(zhǔn)則，設(shè)計(jì)加權(quán)啟發(fā)式貪心搜索算法，推理擁塞路徑中最有可能發(fā)生擁塞的鏈路集合。

3.1 鏈路擁塞先驗(yàn)概率求解

IP網(wǎng)絡(luò)中，各E2E擁塞路徑的整體傳輸率iΨ與路徑途經(jīng)各鏈路的傳輸率j?之間滿足式(5)關(guān)系[16]。

其中，iΨ為第i條路徑整體傳輸率，j?為該路徑下途經(jīng)的第 j條鏈路的傳輸率。為對(duì)應(yīng)各自時(shí)間片下 IP網(wǎng)絡(luò)構(gòu)建的化簡(jiǎn)擁塞矩陣的元素值。根據(jù)定義4，當(dāng)?shù)趈條鏈路存在于路徑Pi中，否則，為了簡(jiǎn)化推理過程，根據(jù)定義1，對(duì)E2E擁塞路徑及途經(jīng)各鏈路的性能關(guān)系利用Boolean代數(shù)模型進(jìn)行表述，如式(6)所示。

其中，“∨”為Boolean值最大化操作符。為了對(duì)擁塞鏈路先驗(yàn)概率進(jìn)行求解，對(duì)式(6)兩邊取數(shù)學(xué)期望，并轉(zhuǎn)換后可得

其中，nε為擁塞路徑途經(jīng)鏈路數(shù)，為去相關(guān)后的 E2E路徑的擁塞概率可通過 N 次snapshots中ping探測(cè)出的各E2E路徑狀態(tài)Boolean值求和取平均得出，用表示。為便于計(jì)算，對(duì)式(7)兩邊取對(duì)數(shù)，整理后可得

根據(jù)動(dòng)態(tài)路由算法選路策略，當(dāng)IP網(wǎng)絡(luò)中某鏈路截?cái)嗷虺掷m(xù)擁塞達(dá)到一定時(shí)間后，會(huì)重新進(jìn)行E2E路徑途經(jīng)鏈路的選取。因此，在擁塞鏈路先驗(yàn)概率學(xué)習(xí)過程中，N次snapshots中對(duì)IP網(wǎng)絡(luò)構(gòu)建的選路矩陣 D可能會(huì)發(fā)生改變。由此，帶來式(8)中的改變，從而造成鏈路擁塞先驗(yàn)概率pj求解誤差。另外，在借助tomography技術(shù)進(jìn)行擁塞鏈路推理時(shí)，通常利用盡可能少的E2E路徑探測(cè)，覆蓋盡可能多的鏈路，并且通過前述2次去相關(guān)化簡(jiǎn)操作，易造成式(8)中對(duì)應(yīng)的E2E路徑數(shù)小于算法覆蓋的鏈路數(shù)。使式(8)所示Boolean線性方程組系數(shù)矩陣欠定，無法求得唯一解。

因此，需對(duì)式(8)進(jìn)行系數(shù)矩陣擴(kuò)展補(bǔ)滿秩操作。由于系數(shù)矩陣各行代表各線性無關(guān)擁塞路徑。因此，可將兩擁塞路徑視為一條路徑進(jìn)行關(guān)聯(lián)處理，對(duì)兩矩陣行相應(yīng)鏈路進(jìn)行“∨”操作，構(gòu)建的擴(kuò)展路徑行。各擴(kuò)展路徑行對(duì)應(yīng)的擴(kuò)展矩陣各元素用表示。將各元素與與擴(kuò)展矩陣各元素合并，并再次去相關(guān)化簡(jiǎn)后，可構(gòu)造滿秩系數(shù)矩陣其為秩等于nε的方陣，k值大小取決于的值，nε為擁塞路徑途徑鏈路數(shù)，為對(duì)應(yīng)的擁塞路徑數(shù)。

式(11)為 Boolean代數(shù)線性方程組，直接求解存儲(chǔ)量和計(jì)算量均過大，特別是此方程組系數(shù)矩陣各元素為Boolean代數(shù)值0或1，非零值較少，為典型的稀疏矩陣。當(dāng)矩陣主元nε)時(shí)，無法計(jì)算。即使主元但當(dāng)其絕對(duì)值很小時(shí)，的逆矩陣作為除數(shù)，因舍入誤差的存在也會(huì)使計(jì)算帶來較大誤差。本文將稀疏矩陣系數(shù)線性方程組迭代求解逐次超松弛(SOR,successive over-relaxation)方法引入到 IP網(wǎng)絡(luò)鏈路擁塞先驗(yàn)概率Boolean線性方程組求解中。

3.2 當(dāng)前時(shí)刻擁塞鏈路推理

在動(dòng)態(tài)路由算法下的IP網(wǎng)絡(luò)中，基于變結(jié)構(gòu)離散動(dòng)態(tài)貝葉斯網(wǎng)簡(jiǎn)化模型，根據(jù)當(dāng)前1次snapshots獲取到的各E2E路徑性能結(jié)果進(jìn)行擁塞鏈路推理，鏈路擁塞后驗(yàn)概率如式(12)所示。

其中，nε′為推理時(shí)刻擁塞鏈路總數(shù)。對(duì)式(17)取對(duì)數(shù)可得

當(dāng)各 E2E路徑探測(cè)過程中未發(fā)生路由改變，式(19)的推理過程即簡(jiǎn)化為靜態(tài)路由算法下的IP網(wǎng)絡(luò)內(nèi)部擁塞鏈路推理經(jīng)典算法CLINK[11]的擁塞鏈路推理過程。由此可見，本文提出的VSDDB算法是對(duì) IP網(wǎng)絡(luò)內(nèi)部擁塞鏈路推理的一般方法。

3.3 算法步驟及偽代碼

VSDDB算法在擁塞鏈路推理時(shí)，借助加權(quán)啟發(fā)式貪心搜索算法[17]尋找最優(yōu)解，算法偽代碼如下所示。

Pθ//推理時(shí)刻擁塞路徑集合；

Lε//推理時(shí)刻擁塞路徑途經(jīng)鏈路集合；

n(k)//推理時(shí)刻鏈路 lk存在于多少條 E2E路徑中；

plk//包含鏈路lk的所有E2E路徑；

輸出：Ω//擁塞鏈路推理集合。

1)初始化Ω=φ；//初始化擁塞鏈路推理集合

2)初始化P?=Pθ；//初始化推理時(shí)刻擁塞路徑集合

3)計(jì)算 pκ；

6)while (P?≠φ)do

8)Ω=Ω+ {lk|lk∈ Lε}；//添加此lk到擁塞鏈路覆蓋集合Ω

9)更新 Lε=Lε? {lk}；//從集合Lε中去除已推理的鏈路lk

10)更新 P?=P?? { plk|lk∈ plk}；//從集合P?中去除包含lk的所有路徑

11)end while

4 實(shí)驗(yàn)評(píng)價(jià)

為了客觀評(píng)價(jià)VSDDB算法的擁塞鏈路推理性能，分別采用模擬、Emulab仿真及Internet實(shí)測(cè)實(shí)驗(yàn)，比較驗(yàn)證算法推理性能。為了更好地驗(yàn)證提出算法在不同網(wǎng)絡(luò)環(huán)境中的擁塞鏈路推理性能，模擬及仿真實(shí)驗(yàn)中，利用 Brite拓?fù)渖善鱗18]分別生成 3種不同類型、規(guī)模的 IP網(wǎng)絡(luò)拓?fù)淠Ｐ停篧axman、BA及GLP。在Eclipse MARS.1平臺(tái)下導(dǎo)入不同網(wǎng)絡(luò)拓?fù)淠Ｐ?，并利用隨機(jī)數(shù)模型模擬多鏈路擁塞場(chǎng)景。

4.1 參數(shù)設(shè)置及評(píng)價(jià)指標(biāo)

路徑擁塞閾值參數(shù) path-congestion-threshold：默認(rèn)設(shè)置N=30，path-congestion-threshold=0。對(duì)各E2E路徑30次snapshots中，E2E路徑分組丟失率低于設(shè)置閾值(0.05)時(shí)，路徑正常，否則，路徑擁塞。為了驗(yàn)證 IP網(wǎng)絡(luò)擁塞程度不同的情況對(duì)算法性能帶來的影響。模擬實(shí)驗(yàn)中，引入擁塞鏈路數(shù)占待測(cè)IP網(wǎng)絡(luò)鏈路數(shù)之間的比例參數(shù)congestion-link-ratio來仿真網(wǎng)絡(luò)擁塞程度，設(shè)置congestion-link-ratio為0.05～0.6，模擬擁塞鏈路數(shù)由少到多發(fā)生改變；為了模擬 IP網(wǎng)絡(luò)中路由變化頻繁程度對(duì)算法推理性能的影響，引入路由變化參數(shù) route-changingthreshold，以連續(xù)snapshots中鏈路持續(xù)擁塞次數(shù)作為路徑變路由的觸發(fā)條件，默認(rèn)設(shè)置 routechanging-threshold=4。利用檢測(cè)率(DR,detection rate)及誤報(bào)率(FPR,false positive rate)對(duì)算法性能進(jìn)行評(píng)估[11]。DR及FPR均為各參數(shù)不變情況下，連續(xù)實(shí)驗(yàn)10次取平均后結(jié)果。

其中，F(xiàn)為推理時(shí)刻實(shí)際發(fā)生擁塞的鏈路，X為算法推理出的擁塞鏈路。

4.2 模擬實(shí)驗(yàn)評(píng)價(jià)

本文提出的VSDDB算法及重現(xiàn)CLINK算法均采用JAVA語言在Eclipse MARS.1平臺(tái)下進(jìn)行編寫。利用Brite拓?fù)渖善鞣謩e生成150個(gè)節(jié)點(diǎn)的Waxman、BA及 GLP模型文件，導(dǎo)入 Eclipse MARS.1平臺(tái)，搭建IP網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。鏈路擁塞事件利用隨機(jī)數(shù)發(fā)生器以congestion-link-ratio比例在每次snapshots中進(jìn)行模擬，包括鏈路擁塞先驗(yàn)概率學(xué)習(xí)中的30次snapshots以及當(dāng)前時(shí)刻擁塞鏈路推理中的 1次 snapshots。設(shè)置 route-changingthreshold=4作為各 E2E路徑變路由閾值，并模擬OSPF中最短路徑優(yōu)先策略重新選路。在相同的鏈路覆蓋范圍、擁塞鏈路事件場(chǎng)景下，利用本文提出的VSDDB算法與經(jīng)典CLINK算法分別在不同類型及節(jié)點(diǎn)規(guī)模網(wǎng)絡(luò)中進(jìn)行擁塞鏈路推理實(shí)驗(yàn)，比較2種算法的推理性能。其中，VSDDB算法在3種不同 IP網(wǎng)絡(luò)模型中的推理結(jié)果用實(shí)線表示，CLINK算法用虛線表示。

4.2.1 不同擁塞程度下的算法性能比較

設(shè)置 congestion-link-ratio為 0.05～0.6，來模擬待測(cè)IP網(wǎng)絡(luò)不同的鏈路擁塞程度，隨著數(shù)值增大（鏈路擁塞數(shù)目增加），網(wǎng)絡(luò)擁塞程度加重。2種算法的擁塞鏈路推理檢測(cè)率及誤報(bào)率如圖3所示。

圖3 不同擁塞鏈路比例下2種算法推理性能比較

如圖3(a)所示，不同IP網(wǎng)絡(luò)模型下，2種算法的檢測(cè)率均呈下降趨勢(shì)。VSDDB算法的檢測(cè)率明顯高于 CLINK算法。VSDDB算法在 GLP模型下檢測(cè)率最高，其次是BA和Waxman模型。在動(dòng)態(tài)路由IP網(wǎng)絡(luò)下，CLINK算法的推理性能較不變路由時(shí)[11]明顯降低，由于 GLP模型冪率性強(qiáng)，共有鏈路數(shù)多，因此，基于最小鏈路覆蓋理論[11]在 GLP模型下進(jìn)行多鏈路擁塞推理時(shí)，路由變化對(duì)算法的推理性能影響最大。如圖3(b)所示，不同IP網(wǎng)絡(luò)模型下，VSDDB算法的誤報(bào)率較CLINK算法略有降低。由圖3可知，隨著擁塞鏈路比例的增大，VSDDB算法的性能下降趨緩，穩(wěn)定性優(yōu)于CLINK算法。綜合比較2種算法的檢測(cè)率、誤報(bào)率及穩(wěn)定性特征，VSDDB算法的推理性能優(yōu)于CLINK算法。

4.2.2 不同變路由頻率下的算法性能比較

為了驗(yàn)證VSDDB算法在不同IP網(wǎng)絡(luò)環(huán)境下的推理性能，利用鏈路連續(xù)擁塞次數(shù)觸發(fā)路由表更新來模擬 IP網(wǎng)絡(luò)變路由的情況。分別設(shè)置 routechanging-threshold為 1～4代表路由改變的閾值參數(shù)。如 route-changing-threshold=4，表示鏈路在連續(xù)4次snapshots中均為擁塞狀態(tài)時(shí)，途經(jīng)該鏈路的E2E路徑將發(fā)生路由改變；數(shù)字越小表明待推理IP網(wǎng)絡(luò)中各E2E路徑的路由變化頻率越頻繁；反之，路由變化越慢。對(duì)150個(gè)節(jié)點(diǎn)的Waxman、BA及GLP模型 IP網(wǎng)絡(luò)中，分別設(shè)置 congestionlink-ratio=0.1，route-changing-threshold不同的實(shí)驗(yàn)場(chǎng)景，2種算法的擁塞鏈路推理檢測(cè)率及誤報(bào)率如圖4所示。

圖4 不同路由變化閾值參數(shù)下2種算法推理性能比較

如圖4(a)所示，在動(dòng)態(tài)路由IP網(wǎng)絡(luò)中，路由變化頻率越快，2種算法在不同模型下的檢測(cè)率均越低，誤報(bào)率均越高。檢測(cè)率隨路由變化頻率的增大呈線性下降趨勢(shì)。VSDDB算法在GLP模型下的檢測(cè)率最高，BA及Waxman模型下次之，并且相差不大；而CLINK算法在GLP模型下檢測(cè)率最低，BA及Waxman模型下次之，同樣是由于GLP模型的強(qiáng)冪率特性所致。由圖 4(b)可知，2種算法均在GLP模型下的誤報(bào)率最低，其次是BA及Waxman模型。綜合2種算法在不同模型下的檢測(cè)率及誤報(bào)率，VSDDB算法的推理性能優(yōu)于CLINK算法。

4.2.3 不同網(wǎng)絡(luò)規(guī)模下的算法推理性能比較

為了驗(yàn)證本文提出的 VSDDB算法在不同IP網(wǎng)絡(luò)規(guī)模下的擁塞鏈路推理性能。利用Brite拓?fù)渖善饕阅J(rèn)參數(shù)生成節(jié)點(diǎn)數(shù)(nodenumber)從50～350變化的 Waxman、BA及 GLP模型。分別設(shè)置 congestion-link-ratio=0.2，route-changingthreshold=4，2種算法的擁塞鏈路推理檢測(cè)率及誤報(bào)率如圖5所示。

圖5 不同網(wǎng)絡(luò)規(guī)模下2種算法推理性能比較

如圖5(a)所示，2種算法在GLP模型下的檢測(cè)率最高，其次是BA及Waxman模型；如圖5(b)所示，2種算法在GLP模型下的誤報(bào)率最低，其次是BA及Waxman模型。在不同規(guī)模的IP網(wǎng)絡(luò)中，VSDDB算法的檢測(cè)率及誤報(bào)率均較CLINK算法穩(wěn)定。綜合 2種算法在不同模型下的檢測(cè)率、誤報(bào)率及穩(wěn)定性特征，VSDDB算法的推理性能優(yōu)于CLINK算法。

4.3 Emulab仿真實(shí)驗(yàn)評(píng)價(jià)

實(shí)際IP網(wǎng)絡(luò)拓?fù)浯蟛糠址膬缏侍匦裕虼?，在Emulab實(shí)驗(yàn)平臺(tái)上使用Brite拓?fù)渖善饕阅J(rèn)參數(shù)生成20個(gè)節(jié)點(diǎn)，服從強(qiáng)冪率規(guī)則分布的GLP模型Brtie文件；通過導(dǎo)入Brite文件，搭建待測(cè)IP網(wǎng)絡(luò)，并將探針及性能監(jiān)控臺(tái)接入待測(cè)網(wǎng)絡(luò)；由性能監(jiān)控臺(tái)給各發(fā)分組路由器探針下達(dá)探測(cè)任務(wù)，并將測(cè)得數(shù)據(jù)上傳至性能監(jiān)控臺(tái)分別利用VSDDB及CLINK算法進(jìn)行擁塞鏈路推理。

Emulab仿真實(shí)驗(yàn)平臺(tái)設(shè)置如下。1)網(wǎng)絡(luò)拓?fù)洌涸O(shè)置仿真IP網(wǎng)絡(luò)各鏈路帶寬100 Mbit/s，時(shí)延15 ms；2)選路協(xié)議：IP網(wǎng)絡(luò)采用OSPF協(xié)議，E2E路徑服從最短路徑優(yōu)先選路規(guī)則。設(shè)置鏈路擁塞時(shí)延大于8 min后重新選路，各路由器的路由表在2 min內(nèi)可實(shí)現(xiàn)穩(wěn)定，鏈路在2 min內(nèi)可恢復(fù)正常數(shù)據(jù)傳輸；3)鏈路狀態(tài)：采用LM1模型[9]，鏈路擁塞時(shí)分組丟失率服從[0.05,1]均勻分布；鏈路正常時(shí)分組丟失率服從[0,0.01]均勻分布。為每條鏈路賦初始分組丟失率后，鏈路分組丟失服從Gilbert過程，即鏈路狀態(tài)在擁塞與正常之間波動(dòng)。處于正常狀態(tài)時(shí)不分組丟失；處于擁塞狀態(tài)時(shí)全分組丟失。鏈路每隔2 min以congestion-link-ratio比例按照隨機(jī)數(shù)規(guī)律變化產(chǎn)生擁塞事件。本次Emulab仿真實(shí)驗(yàn)僅對(duì)路由器節(jié)點(diǎn)Node6進(jìn)行發(fā)分組探針部署，主動(dòng)發(fā)分組探測(cè) E2E路徑數(shù) 12條，鏈路覆蓋數(shù)18條。鏈路擁塞先驗(yàn)概率學(xué)習(xí)過程中，性能監(jiān)控臺(tái)每隔2 min對(duì)探針發(fā)送1次snapshots指令。設(shè)置congestion-link-ratio=0.1，2種算法的擁塞鏈路推理性能比較如表1所示。

表1 Emulab仿真實(shí)驗(yàn)算法推理性能比較

從表1可以看出，由于CLINK算法未考慮IP網(wǎng)絡(luò)中動(dòng)態(tài)路由對(duì)算法推理性能帶來的影響，導(dǎo)致算法推理性能下降。

4.4 Internet實(shí)測(cè)實(shí)驗(yàn)評(píng)價(jià)

為了驗(yàn)證VSDDB算法在實(shí)際Internet網(wǎng)絡(luò)中擁塞鏈路推理性能，在 50個(gè)節(jié)點(diǎn)組成的某高校局域網(wǎng)中以最大鏈路集合覆蓋方式部署待測(cè)網(wǎng)絡(luò)各路由器探針，主動(dòng)探測(cè)發(fā)分組E2E路徑數(shù)225條。由于實(shí)測(cè) Internet網(wǎng)絡(luò)內(nèi)部各鏈路分組丟失率數(shù)值無法準(zhǔn)確獲知，即在Internet實(shí)測(cè)實(shí)驗(yàn)中，缺少式(20)中的標(biāo)準(zhǔn)答案（Benchmark）F，無法利用檢測(cè)率及誤報(bào)率公式判斷算法的擁塞鏈路推理性能。

因此，為了能夠驗(yàn)證本文提出VSDDB算法在實(shí)測(cè)Internet網(wǎng)絡(luò)中的推理性能，借鑒文獻(xiàn)[11]在實(shí)際 Internet中進(jìn)行路徑性能一致性判斷的方法，對(duì)推理算法進(jìn)行性能評(píng)價(jià)。路徑性能一致性判斷的定義如下：將當(dāng)前擁塞鏈路推理時(shí)刻探測(cè)出的擁塞路徑分成大小相等的2個(gè)集合，即推理集合Ι及驗(yàn)證集合P，根據(jù)集合Ι中各擁塞路徑，利用算法進(jìn)行各途經(jīng)擁塞鏈路的推理；根據(jù)擁塞鏈路所在路徑為擁塞路徑的原理，確定驗(yàn)證集合P中推理出的擁塞路徑，并與驗(yàn)證集合P中的擁塞路徑進(jìn)行對(duì)比，如路徑推理結(jié)果與實(shí)測(cè)路徑擁塞結(jié)果一致，則算法推理結(jié)果準(zhǔn)確。2種算法的擁塞鏈路推理性能比較如表2所示。

表2 Internet實(shí)測(cè)實(shí)驗(yàn)算法推理性能比較

由表2所示，實(shí)測(cè)實(shí)驗(yàn)結(jié)果同樣驗(yàn)證了本文提出的 VSDDB算法擁塞鏈路推理性能優(yōu)于 CLINK算法。

5 結(jié)束語

本文提出了一種動(dòng)態(tài)路由 IP網(wǎng)絡(luò)中的擁塞鏈路推理新方法 VSDDB。通過引入馬爾可夫假設(shè)及時(shí)齊性假設(shè)，對(duì)動(dòng)態(tài)路由 IP網(wǎng)絡(luò)擁塞鏈路推理問題，建立變結(jié)構(gòu)離散動(dòng)態(tài)貝葉斯網(wǎng)簡(jiǎn)化模型；利用逐次超松弛算法迭代求解各鏈路擁塞先驗(yàn)概率，并基于貝葉斯最大后驗(yàn)準(zhǔn)則，提出一種加權(quán)啟發(fā)式貪心搜索方法推理擁塞鏈路集合。模擬、仿真及Internet實(shí)測(cè)實(shí)驗(yàn)比較驗(yàn)證了VSDDB具有更好的推理性能。

[1]潘勝利,張志勇,費(fèi)高雷,等. 網(wǎng)絡(luò)鏈路性能參數(shù)估計(jì)的層析成像方法綜述[J].軟件學(xué)報(bào),2015,26(9):2356-2372.PAN S L,ZHANG Z Y,FEI G L,et al. Survey on network tomography for link performance parameter evaluation[J]. Journal of Software,2015,26(9): 2356-2372.

[2]楊洋,楊家海,王會(huì),等. IP網(wǎng)絡(luò)時(shí)延敏感型業(yè)務(wù)流自適應(yīng)負(fù)載均衡算法[J].通信學(xué)報(bào),2015,36(3):131-141.YANG Y,YANG J H,WANG H,et al. Towards load adaptive routing based on link critical degree for delay-sensitive traffic in IP networks[J]. Jouranl on Communications,2015,36(3): 131-141.

[3]MAO Y Y,KSCHISCHANG F R,LI B H,et al. A factor graph approach to link loss monitoring in wireless sensor networks [J]. IEEE Journal on Selected Areas in Communications,2005,23(4): 820-829.

[4]DUFFIELD N G,PRESTI F L,PAXSON V,et al. Inferring link loss using striped unicast probes[C]//IEEE INFOCOM’01,Anchorage,IEEE Communications Society. c2001: 915-923.

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

[6]COATES M,NOWAK R. Network loss inference using unicast end-to-end measurement[C]//ITC Conf. on IP Traffic,Modeling and Management. Monterey: IEEE Computer Society,c2000: 28.

[7]ADAMS A,BU T,?ACERES R,et al. The use of end-to-end multicast measurements for characterizing internal network behavior[J].IEEE Communications Magazine,2000,38(5): 152-159.

[8]LAWRENCE E,MICHAILIDIS G,NAIR V,et al. Network tomography: a review and recent developments[J]. Fan amp;Koul Editors Frontiers in Statistics,2006:345-364.

[9]PADMANABHAN V N,QIU L L,WANG H J. Server-based inference of internet performance[C]//IEEE INFOCOM’03. San Francisco,CA,c2003: 1-15.

[10]BATSAKIS A,MALIK T,TERZIS A. Practical passive lossy link inference[C]//PAM 2005. Springer Berlin Heidelberg,c2005,3431:362-367.

[11]NGUYEN H X,THIRAN P. The Boolean solution to the congested ip link location problem: theory and practice[C]//IEEE INFOCOM’07.Alaska,USA,c2007: 2117-2125.

[12]喬焰,孟洛明,成璐,等. 動(dòng)態(tài)網(wǎng)絡(luò)中的高效多故障診斷技術(shù)[J].北京郵電大學(xué)學(xué)報(bào),2009,32(6): 1-4.QIAO Y,MENG L M,CHENG L,et al. An efficient approach to multi-fault diagnosis in dynamic networks [J]. Journal of Beijing University of Posts and Telecommunications,2009,32(6): 1-4.

[13]連可,龍兵,王厚軍. 基于貝葉斯最大后驗(yàn)概率準(zhǔn)則的大型復(fù)雜系統(tǒng)故障診斷方法研究[J]. 兵工學(xué)報(bào),2008,29(3): 352-356.LIAN K,LONG B,WANG H J. A fault diagnosis approach of the large complex system based on bayes theory[J].Acta Armamentarii,2008,29(3): 352-356.

[14]高曉光,史建國. 變結(jié)構(gòu)離散動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)及其推理算法[J]. 系統(tǒng)工程學(xué)報(bào),2007,22(1): 9-14.GAO X G,SHI J G. Structure varied discrete dynamic Bayesian network and its inference algorithm[J]. Journal of Systems Engineering,2007,22(1):9-14.

[15]RISH I,BRODIE M. Adaptive diagnosis in distributed systems[J].IEEE Transactions on Neural Networks,2005,16(5): 1088-1109.

[16]SHAVITT Y,SUN X,WOOL A,et al. Computing the unmeasured: an algebraic approach to internet mapping [J]. IEEE Jounal on Selected Areas in Communications,2004,22(1): 67-78.

[17]GAREY M R,JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness[M]. New York: Freeman Press,1979.

[18]MEDINA A,LAKHINA A,MATTA I,et al. BRITE: an approach to universal topology generation[C]//MASCOTS. Washington,c2001:346-353.

IP network congested link inference based on variable structure discrete dynamic Bayesian

CHEN Yu1,2,3,ZHOU Wei1,DUAN Zhe-min1,QIAN Ye-kui4,ZHAO Xin5

(1. School of Electronic Information,Northwestern Polytechnical University,Xi’an 710072,China;2. School of Electronics and Communication Engineering,Zhengzhou University of Aeronautics,Zhengzhou 450015,China;3. Science and Technology on Information Transmission and Dissemination in Communication Networks Laboratory,Shijiazhuang 050000,China;4. Department of Missile,Air Defence Forces Academy of PLA,Zhengzhou 450052,China;5. Department of Antiaircraft Gun-Missile System,Air Defense Forces Academy of PLA,Zhengzhou 450052,China)

Aiming at the inference performance descending of CLINK algorithm in dynamic routing IP network,a kind of variable structure discrete dynamic Bayesian network model was established. Based on the simple model after introducing assumptions of Markov property and time-homogeneity,a kind of congested link inference algorithm VSDDB was proposed.Successive over relaxation iterative algorithm was introduced to solve the link congested prior probabilities,based on the Bayesian maximum a-posterior criterion,a kind of weighted heuristic greedy algorithm was used to infer the set of congested links.The experimental results have shown that the VSDDB algorithm has better inference performance.

IP network,variable structure discrete dynamic Bayesian,congestion link inference,Boolean model

s:The National Basic Research Program of China (973 Program)(No.2013CB329104),The National Natural Science Foundation of China (No.61103225),The Science and Technology on Information Transmission and Dissemination in Communication Networks Laboratory Research Fund

TP393

A

2016-01-11；

2016-07-09

國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（“973”計(jì)劃）基金資助項(xiàng)目（No.2013CB329104）；國家自然科學(xué)基金資助項(xiàng)目(No.61103225)；通信網(wǎng)信息傳輸與分發(fā)技術(shù)重點(diǎn)實(shí)驗(yàn)室基金資助項(xiàng)目

10.11959/j.issn.1000-436x.2016151

陳宇（1978-），男，河南鄭州人，鄭州航空工業(yè)管理學(xué)院副教授，主要研究方向?yàn)閿?shù)據(jù)采集與信號(hào)處理、網(wǎng)絡(luò)安全。

周?。?980-），男，山東泰安人，博士，西北工業(yè)大學(xué)副教授，主要研究方向?yàn)橐曨l信息處理及其VLSI設(shè)計(jì)。

段哲民（1953-），男，陜西白水人，西北工業(yè)大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)閿?shù)據(jù)采集與信號(hào)處理。

錢葉魁（1980-），男，安徽樅陽人，博士，解放軍防空兵學(xué)院副教授，主要研究方向?yàn)榫W(wǎng)絡(luò)測(cè)量、網(wǎng)絡(luò)安全。

趙鑫（1978-），男，山西長治人，博士，解放軍防空兵學(xué)院講師，主要研究方向?yàn)榫W(wǎng)絡(luò)安全。