国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

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

2016-11-24 07:28陳宇周巍段哲民錢葉魁趙鑫
通信學報 2016年8期
關鍵詞:貝葉斯路由鏈路

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

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

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

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

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

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

IP網(wǎng)絡;變結構離散動態(tài)貝葉斯;擁塞鏈路推理;Boolean模型

1 引言

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

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

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

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

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

2 網(wǎng)絡模型及相關定義

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

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

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

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

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

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

引理1[13]取最大值時,當滿足如下條件:1)如果 yi=0,且 Dij=1,則 xi=0;2)如果 yi=1,則必然存在至少一個 xi=1,使 Dij=1。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 VSDDB算法

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

圖2 VSDDB算法設計原理

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

3.1 鏈路擁塞先驗概率求解

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

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

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

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

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

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

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

3.2 當前時刻擁塞鏈路推理

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

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

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

3.3 算法步驟及偽代碼

VSDDB算法在擁塞鏈路推理時,借助加權啟發(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)絡環(huán)境中的擁塞鏈路推理性能,模擬及仿真實驗中,利用 Brite拓撲生成器[18]分別生成 3種不同類型、規(guī)模的 IP網(wǎng)絡拓撲模型:Waxman、BA及GLP。在Eclipse MARS.1平臺下導入不同網(wǎng)絡拓撲模型,并利用隨機數(shù)模型模擬多鏈路擁塞場景。

4.1 參數(shù)設置及評價指標

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

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

4.2 模擬實驗評價

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

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

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

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

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

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

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

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

如圖4(a)所示,在動態(tài)路由IP網(wǎng)絡中,路由變化頻率越快,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)絡規(guī)模下的算法推理性能比較

為了驗證本文提出的 VSDDB算法在不同IP網(wǎng)絡規(guī)模下的擁塞鏈路推理性能。利用Brite拓撲生成器以默認參數(shù)生成節(jié)點數(shù)(nodenumber)從50~350變化的 Waxman、BA及 GLP模型。分別設置 congestion-link-ratio=0.2,route-changingthreshold=4,2種算法的擁塞鏈路推理檢測率及誤報率如圖5所示。

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

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

4.3 Emulab仿真實驗評價

實際IP網(wǎng)絡拓撲大部分服從冪率特性,因此,在Emulab實驗平臺上使用Brite拓撲生成器以默認參數(shù)生成20個節(jié)點,服從強冪率規(guī)則分布的GLP模型Brtie文件;通過導入Brite文件,搭建待測IP網(wǎng)絡,并將探針及性能監(jiān)控臺接入待測網(wǎng)絡;由性能監(jiān)控臺給各發(fā)分組路由器探針下達探測任務,并將測得數(shù)據(jù)上傳至性能監(jiān)控臺分別利用VSDDB及CLINK算法進行擁塞鏈路推理。

Emulab仿真實驗平臺設置如下。1)網(wǎng)絡拓撲:設置仿真IP網(wǎng)絡各鏈路帶寬100 Mbit/s,時延15 ms;2)選路協(xié)議:IP網(wǎng)絡采用OSPF協(xié)議,E2E路徑服從最短路徑優(yōu)先選路規(guī)則。設置鏈路擁塞時延大于8 min后重新選路,各路由器的路由表在2 min內可實現(xiàn)穩(wěn)定,鏈路在2 min內可恢復正常數(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條。鏈路擁塞先驗概率學習過程中,性能監(jiān)控臺每隔2 min對探針發(fā)送1次snapshots指令。設置congestion-link-ratio=0.1,2種算法的擁塞鏈路推理性能比較如表1所示。

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

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

4.4 Internet實測實驗評價

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

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

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

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

5 結束語

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

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

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

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

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

周?。?980-),男,山東泰安人,博士,西北工業(yè)大學副教授,主要研究方向為視頻信息處理及其VLSI設計。

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

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

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

猜你喜歡
貝葉斯路由鏈路
天空地一體化網(wǎng)絡多中繼鏈路自適應調度技術
基于貝葉斯解釋回應被告人講述的故事
基于星間鏈路的導航衛(wèi)星時間自主恢復策略
鐵路數(shù)據(jù)網(wǎng)路由匯聚引發(fā)的路由迭代問題研究
多點雙向路由重發(fā)布潛在問題研究
一種基于虛擬分扇的簇間多跳路由算法
路由重分發(fā)時需要考慮的問題
基于貝葉斯估計的軌道占用識別方法
基于互信息的貝葉斯網(wǎng)絡結構學習
基于3G的VPDN技術在高速公路備份鏈路中的應用
电白县| 惠州市| 榆林市| 金昌市| 温州市| 巧家县| 卢湾区| 白朗县| 偏关县| 巫山县| 清水县| 磐安县| 舞钢市| 深水埗区| 霍山县| 沂源县| 延长县| 册亨县| 青海省| 景泰县| 武穴市| 通化市| 特克斯县| 桐梓县| 蓬安县| 永州市| 巴彦县| 吴忠市| 池州市| 沿河| 郑州市| 奇台县| 黎川县| 临西县| 铜鼓县| 屯门区| 黄石市| 临沧市| 尼木县| 石屏县| 商城县|