姜守達,尹文濤,楊京禮,魏長安

(哈爾濱工業(yè)大學自動化測試與控制系,黑龍江哈爾濱 150080)

?

基于最大公共路徑匹配的拓撲推斷算法

姜守達,尹文濤,楊京禮,魏長安

(哈爾濱工業(yè)大學自動化測試與控制系,黑龍江哈爾濱 150080)

針對存在節(jié)點動態(tài)加入和退出的網(wǎng)絡,提出了一種基于最大公共路徑匹配的拓撲推斷算法.該算法根據(jù)背景流量影響對“三明治”包中兩個小包進行排序重組,利用重組后的“三明治”包對節(jié)點對相似度進行計算,以提高節(jié)點對相似度的估計精度；利用TTL跳數(shù)信息選擇匹配路徑,按照公共路徑長度匹配搜索新加入節(jié)點的插入位置,減少測量過程中所需的探測次數(shù),提高拓撲推斷的效率.仿真結果表明,該算法能提高網(wǎng)絡拓撲結構推斷的準確性和效率.

網(wǎng)絡測量;網(wǎng)絡層析成像;拓撲推測;最大公共路徑匹配

1 引言

隨著計算機網(wǎng)絡規(guī)模的不斷擴大,網(wǎng)絡拓撲信息在網(wǎng)絡資源的管理和維護、網(wǎng)絡協(xié)議的設計,以及網(wǎng)絡結構的優(yōu)化等方面具有越來越重要的意義.傳統(tǒng)網(wǎng)絡拓撲測量方法需要網(wǎng)絡內部節(jié)點之間的協(xié)作.由于許多單位和組織基于安全或商業(yè)利益方面的考慮,不愿共享其內部網(wǎng)絡信息,使得現(xiàn)有網(wǎng)絡系統(tǒng)和設備具有非協(xié)作性的特點[1],傳統(tǒng)的基于路由器協(xié)作的拓撲測量方法的可行性越來越低.

網(wǎng)絡層析成像技術將醫(yī)學上的計算機層析成像思想引入到網(wǎng)絡測量中,根據(jù)端到端的觀測數(shù)據(jù)采用統(tǒng)計方法來分析和推斷網(wǎng)絡拓撲和性能參數(shù)[2].基于網(wǎng)絡層析成像技術的拓撲測量方法,可以在無需內部節(jié)點協(xié)作的條件下推斷網(wǎng)絡拓撲,克服了傳統(tǒng)方法的不足.文獻[3]最早提出基于節(jié)點對融合的二叉樹拓撲推斷算法,文獻[4,5]分別提出采用判決門限和雙樣本t檢驗對二叉樹進行修剪,將節(jié)點對融合算法擴展到一般樹拓撲模型.文獻[6～8]提出基于極大似然估計的網(wǎng)絡拓撲推斷算法.上述算法主要針對網(wǎng)絡節(jié)點集合相對穩(wěn)定的情況,而在一些實際應用中,如基于P2P的應用,與一個源節(jié)點通信的目標節(jié)點是隨時間不斷變化的,即存在節(jié)點動態(tài)加入和退出的情況.當新的網(wǎng)絡節(jié)點加入后,該類算法需要重新推斷網(wǎng)絡拓撲,因而效率較低.針對該問題,文獻[9]首先提出一種序列化的拓撲推斷算法(Sequential Topology Inference Algorithm,STI),當節(jié)點加入或退出網(wǎng)絡后,只需在原有網(wǎng)絡拓撲的基礎上,推測更新后的拓撲,有效地提高了拓撲推斷效率.對于新加入節(jié)點,STI算法從根節(jié)點開始,自頂向下逐層搜索新加入節(jié)點在原有網(wǎng)絡拓撲中的插入位置.由于該算法對于新加入節(jié)點都需要從根節(jié)點開始逐層搜索,影響了拓撲推斷的效率.文獻[10]提出TSP(Traceroute with Sandwich Probe)算法,將Traceroute網(wǎng)絡測量工具的測量原理引入到基于“三明治”探測包的探測方法中,通過設置“三明治”包中間大數(shù)據(jù)包的TTL值,獲取從源節(jié)點到目的節(jié)點指定跳數(shù)的路徑的加性特征量.該方法能獲取更多的網(wǎng)絡內部信息,因而具有更高的測量精度,但該算法通過窮舉搜索新加入節(jié)點在網(wǎng)絡中的插入位置,故效率較低.

針對上述問題,為提高網(wǎng)絡層析成像框架下的網(wǎng)絡拓撲推斷準確性和效率,本文提出一種基于最大公共路徑匹配的拓撲推斷算法(Maximum Common Path Matching,MCPM).首先,對基于“三明治”包時延差的加性特征量的原理和背景流量對探測包時延的影響進行分析,提出了一種基于探測包重組的節(jié)點對相似度估計方法,對節(jié)點對相似度的估計精度進行提升,以提高拓撲推斷的準確性.在此基礎上,分析了節(jié)點對相似度與最近公共祖先節(jié)點位置的關系,提出了一種直接按公共路徑長度進行匹配的節(jié)點插入位置搜索方法,提高拓撲推斷的效率.

2 網(wǎng)絡模型與加性特征量

2.1 網(wǎng)絡模型

與現(xiàn)有大多數(shù)基于網(wǎng)絡層析成像技術的拓撲推斷算法的文獻[3～12]類似,本文僅考慮樹狀邏輯拓撲結構,一般網(wǎng)絡拓撲可以通過多個樹狀拓撲融合得到[13,14].用T=(V,L)表示樹狀邏輯網(wǎng)絡拓撲模型,其中V為網(wǎng)絡節(jié)點集合,代表網(wǎng)絡中的路由器和主機,L為連接節(jié)點的鏈路集合.節(jié)點O∈V為T的根節(jié)點.從根節(jié)點O到節(jié)點i之間的路徑用pi表示.節(jié)點集合R?V(無子節(jié)點的節(jié)點)表示所有的葉節(jié)點,即探測報文接收節(jié)點,|R|為葉節(jié)點個數(shù).每一個非葉節(jié)點k都至少有一個子節(jié)點,用c(k)表示節(jié)點k的子節(jié)點集合.每一個非根節(jié)點k有且僅有一個父節(jié)點,用f(k)表示.鏈路(f(k),k)∈L記為ek.定義f1=f且fn(k)=f(fn-1(k)),其中n為正整數(shù).用集合a(k)={i∈V|?n>0,i=fn(k)}表示節(jié)點k的祖先節(jié)點.對任意兩個葉節(jié)點i和j,用a(i,j)表示他們的最近公共祖先節(jié)點.用集合U=V{O}表示非根節(jié)點集合.網(wǎng)絡內部節(jié)點集合,即非葉節(jié)點非根節(jié)點集合,用I=UR表示.以節(jié)點k為根節(jié)點,葉節(jié)點集合D為目的節(jié)點的子樹用T(k,D)表示.

2.2 基于“三明治”包時延差的加性特征量

定義d為樹T=(V,L)的加性特征量[9],當d滿足:

(1)0

其中,d(e)為鏈路的長度,d(i,j)為葉節(jié)點對(i,j)的相似度,用該節(jié)點對的公共路徑的長度表示.定義加性特征量d后,從根節(jié)點到葉節(jié)點i的路徑pi的長度用ρ(i)表示.

現(xiàn)有算法中,常用的加性特征量有,基于丟包率的加性特征量[4]、基于時延協(xié)方差的加性特征[11]和基于“三明治”包時延差[6,8]的加性特征量.由于采用基于“三明治”包時延差的加性特征量的探測方案不需要時鐘同步,且加性特征量由探測包排隊時延自引入,本文采用該方案,其基本原理如圖1所示.每個“三明治”包由三個探測包組成,其中第1個探測包A1和第3個探測包A2長度相同,第2個探測包B長度遠大于第1個和第3個探測包.每次探測過程中,探測包A1和A2發(fā)往相同的目的地址(圖中節(jié)點j),探測包B發(fā)往另一目的地址(圖中節(jié)點i).三個探測包先經(jīng)過一段共享路徑后,到達節(jié)點i和j的最近公共祖先節(jié)點k,然后分別發(fā)往各自目的節(jié)點.

假設網(wǎng)絡中無背景流,在公共路徑上,由于探測包B較大,發(fā)送時間較長,導致探測包A2的排隊時延較長.在每條共享鏈路上,探測包A1和A2之間的時間間隔都會增加.在非公共路徑上,由于探測包B發(fā)往另一目的節(jié)點,不再影響探測包A2的排隊時延,故探測包A1和A2之間的時間間隔保持不變.設探測包A1和A2的發(fā)送時間間隔為ts,在節(jié)點j的接收時間間隔為tr,則其時延差為Δt=tr-ts.對葉節(jié)點i和j,其公共路徑為從根節(jié)點到其最近公共祖先節(jié)點a(i,j)之間的路徑.定義葉節(jié)點對(i,j)的相似度d(i,j)為探測包A1和A2的時延差,則d(e)為探測包A1和A2在經(jīng)過鏈路e時產(chǎn)生的時延差.葉節(jié)點對(i,j)的共享路徑越長,即“三明治”包所經(jīng)歷的共享路徑越長,則探測包A1和A2的時延差越大,葉節(jié)點對(i,j)的相似度d(i,j)越大.

3 基于最大公共路徑匹配的拓撲推斷算法

3.1 節(jié)點對相似度估計

文獻[6,8]將背景流量對測量結果的影響視為零均值的隨機過程,用探測包A1和A2的時延差的觀測樣本均值作為節(jié)點對相似度的估計值.文獻[12]通過選取受背景流量影響較小的探測包計算時延差觀測樣本均值作為節(jié)點對相似度的估計值.本文通過分析背景流量對探測包的影響,提出一種基于探測包重組的節(jié)點對相似度估計方法,以提高節(jié)點對相似度的估計精度.

探測包在每條鏈路上的經(jīng)歷的時延由處理時延、傳輸時延、傳播時延和排隊時延四部分組成,其中前三部分時延主要由路由特征和探測包長度決定.探測包A1和A2的長度相同,在經(jīng)過同一鏈路時,經(jīng)歷的傳輸時延、傳播時延和處理時延近似相等,故在該鏈路上引入的時延差為兩個探測包的排隊時延差.

(1)

(2)

無背景流量時,在節(jié)點j觀測到的探測包A1和A2的時延差Δt0為公共路徑上各鏈路的時延差之和,即探測包A1和A2的排隊時延差之和:

(3)

當網(wǎng)絡中存在背景流時,由于背景流對探測包A1和A2的影響均為使其排隊時延增大,背景流對探測包的影響越大,其排隊時延增大的越多.又由于探測包A1和A2在經(jīng)過同一鏈路時,經(jīng)歷的傳輸時延、傳播時延和處理時延近似相等,故可以根據(jù)探測包A1和A2在公共路徑上經(jīng)歷的總的時延大小,判斷其受背景流影響的程度大小.

(4)

(5)

即可得到N個“三明治”包中探測包A1經(jīng)歷的時延受背景流量影響的相對大小.

(6)

根據(jù)上面的分析,“三明治”包中探測包A1的作用僅為提供時間參考(使探測過程不需要時鐘同步),故可將N個“三明治”包的探測包A1和A2視為獨立的部分,按照重新排列后的順序進行重組,得到:

(7)

當向每個節(jié)點對發(fā)送的“三明治”包數(shù)目較多時,探測包發(fā)送時間較長,時鐘漂移會導致節(jié)點對相似度估計精度降低.從本文仿真實驗結果來看,本文算法僅需向每個節(jié)點對發(fā)送少量探測包即可達到較高精度,當發(fā)送探測包較少時,探測包發(fā)送時間較短,故時鐘漂移對節(jié)點對相似度估計精度影響較小.基于“三明治”探測包重組的節(jié)點對相似度估計過程詳見算法1.

算法1 基于“三明治”探測包重組的節(jié)點對相似度估計算法

步驟3 對排序后的探測包A1和A2進行重組,得到N個新的“三明治”包:

3.2 拓撲推斷

由于“三明治”包在公共路徑上每條鏈路的時延差均大于0,故基于“三明治”包時延差的加性特征量在每條鏈路的取值均大于0,即d(e)>0,?e∈L,結合2.2節(jié)加性特征量的定義,容易得到下面的定理:

定理1 節(jié)點對(i,j)相似度d(i,j)與其最近公共祖先節(jié)點a(i,j)的位置有如下關系:

(1)當ρ(k)

(2)當d(i,j)=ρ(k),k∈pi時,a(i,j)為節(jié)點k.

假設當前拓撲為T=(V,L),新加入節(jié)點為節(jié)點j.本文通過節(jié)點j與當前拓撲葉節(jié)點進行公共路徑長度匹配,搜索節(jié)點j的插入位置.

如圖2所示,新加入節(jié)點j與葉節(jié)點為r進行公共路徑長度匹配,有以下幾種可能情況:

(1)當在路徑pr上存在節(jié)點i,使得節(jié)點對(r,j)的相似度d(r,j)滿足

ρ(f(i))

(8)

根據(jù)定理1,可得節(jié)點對(r,j)的最近公共祖先節(jié)點a(r,j)在節(jié)點f(i)與節(jié)點i之間的路徑上,即鏈路(f(i),i)上.故從根節(jié)點到節(jié)點對(r,j)的路徑的分叉節(jié)點在鏈路(f(i),i)上,即插入位置為鏈路(f(i),i)上,如圖2(a)所示.

(2)當在路徑pr上存在節(jié)點i,使得d(r,j)滿足

d(r,j)=ρ(i)

(9)

根據(jù)定理1,可得節(jié)點對(r,j)的最近公共祖先節(jié)點a(r,j)為節(jié)點i,即節(jié)點對(r,j)的公共路徑為pi,則從根節(jié)點到節(jié)點對(r,j)的分叉節(jié)點為節(jié)點i,可以確定節(jié)點j為節(jié)點i的子孫節(jié)點,節(jié)點j的插入位置在節(jié)點i上(如圖2(b)所示),或節(jié)點i的除去節(jié)點c所在分支的子孫節(jié)點或子孫鏈路上(如圖2(c)所示).

利用探測包的TTL(Time-To-Live)域,可以獲取從根節(jié)點到葉節(jié)點經(jīng)過的路由跳數(shù),即從根節(jié)點到葉節(jié)點包含的鏈路個數(shù).由于TTL跳數(shù)信息較大的葉節(jié)點與新加入節(jié)點具有更大的公共路徑長度的可能性較大,故每次匹配選取目的節(jié)點中TTL跳數(shù)信息最大的節(jié)點,能提高算法效率.節(jié)點j加入網(wǎng)絡時,本文根據(jù)以上分析設計了如算法2所示的拓撲更新算法,其中判定閾值δ=1/2mine∈Ld(e).

算法2 拓撲更新算法AddLeafNode(T,j,δ)

輸入 當前拓撲T=(V,L),新加入節(jié)點j,判定閾值δ

初始化k=O,D=R

①Ifi==k,thenD′=DR(c)；ElseD′=R(i)R(c)；

Else 節(jié)點j為節(jié)點i的子孫節(jié)點,其插入位置在子樹T(i,D′)上.更新k和D:k=i,D=D′,跳轉到步驟1；

輸出 加入節(jié)點j后新的拓撲T=(V,L)

定理2 算法2將節(jié)點j插入到拓撲中正確位置的充分條件為節(jié)點對相似度的估計誤差小于δ/2,即

(10)

證明 當算法2每次進行最大公共路徑匹配都能找出正確的分叉節(jié)點時,能將節(jié)點j插入到拓撲中正確位置.

(11)

由式(11)右半部分可得

(12)

由節(jié)點對相似度估計誤差小于δ/2,可得

進一步可得到

(13)

(14)

由式(12)、(13)和(14)可到

d(r,j)<ρ(i)

(15)

同理,由式(11)左半部分可得

ρ(f(i))

(16)

由式(15)和(16)可得式(8)成立,即從根節(jié)點到節(jié)點對(r,j)的路徑的分叉節(jié)點在鏈路(f(i),i)上,即插入位置為鏈路(f(i),i)上,進入算法步驟2執(zhí)行,如圖2(a)所示.

=2δ

由δ=1/2mine∈Ld(e),可得2δ≤d(e),?e∈L,代入上式即得

|ρ(i)-d(r,j)|

(17)

即節(jié)點對(r,j)的公共路徑長度與路徑pi長度的差值小于最小路徑的長度,故d(r,j)=ρ(i).即式(9)成立,節(jié)點對(r,j)的最大公共路徑為pi,則從根節(jié)點到節(jié)點對(r,j)的分叉節(jié)點為節(jié)點i,進入算法步驟3執(zhí)行.設節(jié)點c為路徑Pr上節(jié)點i的子節(jié)點.當節(jié)點c為當前搜索子樹T(k,D)上唯一子節(jié)點時,新插入節(jié)點j為節(jié)點i的子節(jié)點,如圖2(b)所示；當T(k,D)上節(jié)點i存在多個子節(jié)點時,節(jié)點j的插入位置在節(jié)點i的除去節(jié)點c所在分支的子孫節(jié)點或子孫鏈路上,如圖2(c)所示.

綜上可得,算法2每次進行最大公共路徑匹配都能找出正確的分叉節(jié)點,能將節(jié)點j插入到拓撲中正確位置.故式(10)為算法2將節(jié)點j插入到拓撲中正確位置的充分條件.

對于給定源節(jié)點和目的節(jié)點的網(wǎng)絡,可以先在目的節(jié)點中選取TTL跳數(shù)最大的2個葉節(jié)點構建一個4個節(jié)點3條鏈路的簡單二叉樹,然后運用算法2將目的節(jié)點逐個插入到該二叉樹中,具體詳見算法3.當節(jié)點離開網(wǎng)絡時,直接將相關節(jié)點和鏈路刪除即可.

算法3 拓撲推斷算法

輸入 源節(jié)點O,目的節(jié)點集合R,判斷閾值δ

步驟1 按TTL跳數(shù)信息從大到小的順序對葉節(jié)點進行排序,得到:r1,r2,…rn；

步驟2 選取目的節(jié)點r1、r2與源節(jié)點構造一個節(jié)點數(shù)目為4的簡單初始二叉樹T=(V,L):V={O,v1,r1,r2},L={(O,v1),(v1,r1),(v1,r2)}；

步驟4 fori=1,2,…,n:

AddLeafNode(T,ri,δ)；

輸出 拓撲T=(V,L)

4 仿真

為對MCPM算法進行綜合評價,本文采用MATLAB模型仿真和NS 2仿真,分別對該算法拓撲推斷效率和準確性進行評估,并與目前算法中性能較好的STI算法[9]和TSP算法[10]進行比較.

4.1 MATLAB模型仿真

為對算法拓撲推斷效率進行評價,本文采用BRITE拓撲生成工具生成一系列節(jié)點個數(shù)分別為100,200,…,1000的網(wǎng)絡拓撲,每種規(guī)模的拓撲均生成100個.網(wǎng)絡拓撲模型采用Waxman和BA兩種經(jīng)典模型,模型參數(shù)選擇為:α=0.15,β=0.2,m=2,MaxBw=1024,MinBw=2.選取網(wǎng)絡拓撲中節(jié)點度數(shù)較小的節(jié)點作為端節(jié)點,在端節(jié)點中任選一節(jié)點作為源節(jié)點,其余全部端節(jié)點作為目的節(jié)點,即可構成邏輯樹型拓撲.假設加性特征量測量過程中無噪聲干擾,即加性特征量的測量誤差為0.為每個鏈路隨機分配一個取值服從0.1至0.4上均勻分布的加性特征量.每次探測的節(jié)點對相似度為公共路徑上各鏈路加性特征量之和.

測量一個節(jié)點對相似度值需要向節(jié)點對發(fā)送一組指定數(shù)目的“三明治”包.將向一個葉節(jié)點對發(fā)送一組指定數(shù)目的探測包測量該節(jié)點對相似度視為一次探測,則推斷拓撲所需測量的節(jié)點對相似度個數(shù)即為所需探測次數(shù).本文采用推斷網(wǎng)絡拓撲所需探測次數(shù)作為算法效率的評價指標.對每個拓撲,先選取2個目的節(jié)點與源節(jié)點構成一個二叉樹拓撲,然后分別采用MCPM、STI和TSP三種算法將其余目的節(jié)點逐個插入到二叉樹拓撲中,比較各種算法所需的探測次數(shù).

圖3和圖4分別給出了Waxman和BA拓撲模型下,三種算法所需探測次數(shù)隨網(wǎng)絡拓撲節(jié)點個數(shù)的變化情況,圖中數(shù)據(jù)為仿真100次取平均的結果.從圖中可以看出,三種算法所需探測次數(shù)都隨著網(wǎng)絡節(jié)點個數(shù)的增加而增加,其中TSP算法增加的最快,本文算法增加的最慢.在Waxman拓撲模型下,本文算法所需探測次數(shù)較STI算法減少51.35%至55.03%,較TSP算法減少85.46%至97.11%；在BA拓撲模型下,本文算法所需探測次數(shù)較STI算法減少50.41%至55.30%,較TSP算法減少78.56%至94.53%.在Waxman和BA拓撲模型下,本文算法拓撲推斷效率較STI和TSP算法都有明顯提升.

4.2 NS 2仿真

為對算法拓撲推斷準確性進行評價,本文采用NS 2網(wǎng)絡仿真工具構建如圖5所示網(wǎng)絡,該網(wǎng)絡包含15個節(jié)點和14條鏈路.所有邊緣鏈路的帶寬均為5Mbps,物理傳播時延為5ms.所有內部鏈路帶寬均為2Mbps,物理傳播時延為2ms.所有鏈路隊列長度均為50,排隊模型為 FIFO(First In First Out),擁塞避免算法采用尾部丟棄(Drop-tail).探測包為根節(jié)點向葉節(jié)點對發(fā)送的“三明治”包.“三明治”包的大數(shù)據(jù)包長度為500Byte,小數(shù)據(jù)包長度為10Byte.背景流量為服從Pareto分布的On/Off模型的UDP流和TCP流.所有的UDP流和TCP流的發(fā)送節(jié)點和接收節(jié)點在網(wǎng)絡節(jié)點中隨機選擇.UDP流和TCP流的速率分別為0.01Mbps和0.02Mbps.為在不同網(wǎng)絡負載情況下對算法性能進行比較,本文進行2組仿真實驗,第1組實驗網(wǎng)絡負載較輕,背景UDP流和TCP流數(shù)目個數(shù)為100和200,第2組實驗網(wǎng)絡負載較重,背景UDP流和TCP流數(shù)目分別為150和300.

向每個葉節(jié)點對發(fā)送的“三明治”包數(shù)目分別取50,100,…,300,對每個給定的探測包數(shù)目均進行100次仿真.每次仿真,先選取2個葉節(jié)點與根節(jié)點構成一個二叉樹拓撲,然后分別采用MCPM、STI和TSP三種算法將剩余葉節(jié)點逐個插入到二叉樹拓撲中,比較最終生成的拓撲準確率.

圖6給出了第1組實驗的結果,三種算法拓撲推斷準確率都隨“三明治”探測包個數(shù)的增加而增加.本文提出的MCPM算法準確性最高,且在探測包較少時,這種優(yōu)勢更加明顯.當發(fā)送到每個節(jié)點對的探測包數(shù)目為300時,MCPM算法拓撲推斷準確率為98%,較STI算法(65%)提高約50.77%,較TSP算法(95%)提高約3.16%.當發(fā)送到每個節(jié)點對的探測包數(shù)目為50時,MCPM算法拓撲推斷準確率為95%,較STI算法(32%)提高約1.97倍,較TSP算法(66%)提高約43.94%.

圖7給出了第2組實驗的結果,由于網(wǎng)絡負載較重,“三明治”探測包受背景流干擾增大,三種算法準確率較第1組實驗都有不同程度的降低.其中STI算法和TSP算法準確率顯著降低,而MCPM算法仍能保持較高的準確率,這是由于MCPM算法通過基于探測包重組的節(jié)點對相似度估計方法提高節(jié)點對相似度估計精度,從而提高拓撲推斷準確率.當發(fā)送到每個節(jié)點對的探測包數(shù)目為300時,MCPM算法拓撲推斷準確率為93%,較STI算法(28%)提高約2.32倍,較TSP算法(80%)提高約16.25%.當發(fā)送到每個節(jié)點對的探測包數(shù)目為50時,MCPM算法拓撲推斷準確率為74%,較STI算法(5%)提高約13.80倍,較TSP算法(34%)提高約1.18倍.

5 結論

本文首先分析了基于“三明治”包時延差的加性特征量的原理和背景流量對探測包時延的影響,提出了一種基于探測包重組的節(jié)點對相似度估計方法.然后,在此基礎上通過對節(jié)點對相似度與最近公共祖先節(jié)位置的關系進行分析,提出了一種基于最大公共路徑長度匹配的拓撲推斷算法.仿真結果表明,本文提出的MCPM算法較STI算法和TSP算法在拓撲推斷準確性和效率方面都有明顯提高.

[1]Donnet B,Friedman T.Internet topology discovery:a survey[J].IEEE Communications Surveys and Tutorials,2007,9(4):56-69.

[2]趙洪華,陳鳴.基于網(wǎng)絡層析成像技術的拓撲推斷[J].軟件學報,2010,21(1):133-146.

Zhao Hong-hua,Chen Ming.Topology inference based on network tomography[J].Journal of Software,2010,21(1):133-146.(in Chinese)

[3]Duffield N G,Horowitz J,Presti F L,et al.Multicast topology inference from end-to-end measurements[A].ITC Seminar on IP Traffic,Measurement and Modelling[C].Monterey,CA:ITC,2000.1-10.

[4]Duffield N,Horowitz J,et al.Multicast topology inference from measured end-to-end loss[J].IEEE Transactions on Information Theory,2002,48(1):26-45.

[5]Zhang Runsheng,Li Yanbin,Li Xiaotian.Topology inference with network tomography based on t-test[J].IEEE Communications Letters,2014,18(6):921-924.

[6]Coates M,Castro R,Nowak R.Maximum likelihood network topology identification from edge-based unicast measurements[A].International Conference on Measurement and Modeling of Computer Systems[C].Marina Del Rey:ACM,2002.11-20.

[7]Castro R M,Coates M J,Nowak R D.Likelihood based hierarchical clustering[J].IEEE Transactions on Signal Processing,2004,52(8):2308-2321.

[8]Shih M F,Hero A O.Hierarchical inference of unicast network topologies based on end-to-end measurements[J].IEEE Transactions on Signal Processing,2007,55(5):1708-1718.

[9]Ni J,Xie H,Tatikonda S,et al.Efficient and dynamic routing topology inference from end-to-end measurements[J].IEEE/ACM Transactions on Networking,2010,18(1):123-135.

[10]Malekzadeh A,MacGregor M H.Network topology inference from end-to-end unicast measurements[A].27th International Conference on Advanced Information Networking and Applications Workshops[C].Barcelona:IEEE,2013.1101-1106.

[11]Duffield N G,Presti F L.Network tomography from measured end-to-end delay covariance[J].IEEE/ACM Transactions on Networking,2004,12(6):978-992.

[12]Di Pietro A,Ficara D,Giordano S,et al.Noise reduction techniques for network topology discovery[A].IEEE 18th International Symposium on Personal,Indoor and Mobile Radio Communications[C].Athens:IEEE,2007.1-5.

[13]Coates M,Rabbat M,Nowak R.Merging logical topologies using end-to-end measurements[A].Proceedings of the 3rd ACM SIGCOMM Conference on Internet Measurement[C].New York:ACM,2003.192-203.

[14]Di Pietro A,Ficara D,Giordano S,et al.Merging spanning trees in tomographic network topology discovery[A].IEEE International Conference on Communications[C].Dresden:IEEE,2009.1-5.

姜守達 男,1964年出生黑龍江伊春,哈爾濱工業(yè)大學自動化測試與控制系教授.主要研究方向為虛擬試驗技術,網(wǎng)絡測量技術,數(shù)字信號處理等.

E-mail:jsd@hit.edu.cn

尹文濤 男,1983年生于湖北孝感,哈爾濱工業(yè)大學自動化測試與控制系博士研究生.主要研究方向為網(wǎng)絡測量與網(wǎng)絡層析成像技術.

E-mail:huayichu@163.com

楊京禮(通信作者) 男,1984年生于山東日照,哈爾濱工業(yè)大學自動化測試與控制系講師.主要研究方向為網(wǎng)絡測量與網(wǎng)絡層析成像技術.E-mail:icehit0615@163.com

魏長安 男,1981年生于河北承德,哈爾濱工業(yè)大學自動化測試與控制系講師.主要研究方向為虛擬試驗技術,自動測試技術等.

Topology Inference Based on Maximum Common Path Matching

JIANG Shou-da,YIN Wen-tao,YANG Jing-li,WEI Chang-an

(AutomaticTestandControlInstitute,HarbinInstituteofTechnology,Harbin,Heilongjiang150080,China)

For network with nodes joining and leaving dynamically,a topology inference algorithm based on maximum common path matching is proposed.In this algorithm,in order to improve the estimating precision of similarity metric,two small packets of sandwich probes are rearranged in accordance with cross-traffic effects,and the similarity metric is estimated according to the new rearranged sandwich probes.The new joined nodes are directly added into the existing topology by matching the length of common path.By using the information of TTL hop count to select match path,the efficiency of topology inference is improved.The simulating results show that this algorithm can effectively improve the accuracy and efficiency of topology inference.

network measurement; network tomography; topology inference; maximum common path matching

2014-12-02；

2015-01-23；責任編輯:梅志強

國家自然科學基金(No.61501135)

TP393

A

0372-2112 (2016)09-2189-08

??學報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.09.025