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

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

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

基于變結(jié)構(gòu)離散動態(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ù)重點實驗室，河北 石家莊050000；4. 解放軍防空兵學(xué)院導(dǎo)彈系，河南 鄭州 450052；5. 解放軍防空后學(xué)院彈炮一體系，河南 鄭州 450052)

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如IP網(wǎng)絡(luò)配置為靜態(tài)路由算法策略，則在進行擁塞鏈路推理時，N次snapshots中路由始終不發(fā)生變化，則推理模型中僅包含一個時間片下的靜態(tài)貝葉斯網(wǎng)模型。因此，本文對動態(tài)路由算法下的 IP網(wǎng)絡(luò)構(gòu)建的變結(jié)構(gòu)離散動態(tài)貝葉斯網(wǎng)推理模型即簡化為 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)級別順序從小到大依次排列；當(dāng)某條 E2E路徑 Pi途經(jīng)某條鏈路 lj時，選路矩陣 D對應(yīng)位置處的元素值 Dij=1，否則Dij=0。

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

3 VSDDB算法

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

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

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

3.1 鏈路擁塞先驗概率求解

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

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

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

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

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

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

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

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

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

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

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

3.3 算法步驟及偽代碼

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

Pθ//推理時刻擁塞路徑集合；

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

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

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

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

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

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

3)計算 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 實驗評價

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

4.1 參數(shù)設(shè)置及評價指標(biāo)

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

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

4.2 模擬實驗評價

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

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

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

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

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

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

為了驗證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)時，途經(jīng)該鏈路的E2E路徑將發(fā)生路由改變；數(shù)字越小表明待推理IP網(wǎng)絡(luò)中各E2E路徑的路由變化頻率越頻繁；反之，路由變化越慢。對150個節(jié)點的Waxman、BA及GLP模型 IP網(wǎng)絡(luò)中，分別設(shè)置 congestionlink-ratio=0.1，route-changing-threshold不同的實驗場景，2種算法的擁塞鏈路推理檢測率及誤報率如圖4所示。

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

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

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

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

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

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

4.3 Emulab仿真實驗評價

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

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

表1 Emulab仿真實驗算法推理性能比較

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

4.4 Internet實測實驗評價

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

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

表2 Internet實測實驗算法推理性能比較

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

5 結(jié)束語

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

[1]潘勝利,張志勇,費高雷,等. 網(wǎng)絡(luò)鏈路性能參數(shù)估計的層析成像方法綜述[J].軟件學(xué)報,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]楊洋,楊家海,王會,等. IP網(wǎng)絡(luò)時延敏感型業(yè)務(wù)流自適應(yīng)負(fù)載均衡算法[J].通信學(xué)報,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]喬焰,孟洛明,成璐,等. 動態(tài)網(wǎng)絡(luò)中的高效多故障診斷技術(shù)[J].北京郵電大學(xué)學(xué)報,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]連可,龍兵,王厚軍. 基于貝葉斯最大后驗概率準(zhǔn)則的大型復(fù)雜系統(tǒng)故障診斷方法研究[J]. 兵工學(xué)報,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)離散動態(tài)貝葉斯網(wǎng)絡(luò)及其推理算法[J]. 系統(tǒng)工程學(xué)報,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

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

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

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

周巍（1980-），男，山東泰安人，博士，西北工業(yè)大學(xué)副教授，主要研究方向為視頻信息處理及其VLSI設(shè)計。

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

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

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