基于最大公共路徑匹配的拓?fù)渫茢嗨惴?/h1>

2016-11-25 08:16:41姜守達(dá)尹文濤楊京禮魏長(zhǎng)安

電子學(xué)報(bào)訂閱 2016年9期 收藏

關(guān)鍵詞：加性網(wǎng)絡(luò)拓?fù)?/a>三明治

姜守達(dá),尹文濤,楊京禮,魏長(zhǎng)安

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

?

基于最大公共路徑匹配的拓?fù)渫茢嗨惴?/p>

姜守達(dá),尹文濤,楊京禮,魏長(zhǎng)安

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

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

網(wǎng)絡(luò)測(cè)量;網(wǎng)絡(luò)層析成像;拓?fù)渫茰y(cè);最大公共路徑匹配

1 引言

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

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

針對(duì)上述問(wèn)題,為提高網(wǎng)絡(luò)層析成像框架下的網(wǎng)絡(luò)拓?fù)渫茢鄿?zhǔn)確性和效率,本文提出一種基于最大公共路徑匹配的拓?fù)渫茢嗨惴?Maximum Common Path Matching,MCPM).首先,對(duì)基于“三明治”包時(shí)延差的加性特征量的原理和背景流量對(duì)探測(cè)包時(shí)延的影響進(jìn)行分析,提出了一種基于探測(cè)包重組的節(jié)點(diǎn)對(duì)相似度估計(jì)方法,對(duì)節(jié)點(diǎn)對(duì)相似度的估計(jì)精度進(jìn)行提升,以提高拓?fù)渫茢嗟臏?zhǔn)確性.在此基礎(chǔ)上,分析了節(jié)點(diǎn)對(duì)相似度與最近公共祖先節(jié)點(diǎn)位置的關(guān)系,提出了一種直接按公共路徑長(zhǎng)度進(jìn)行匹配的節(jié)點(diǎn)插入位置搜索方法,提高拓?fù)渫茢嗟男?

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

2.1 網(wǎng)絡(luò)模型

與現(xiàn)有大多數(shù)基于網(wǎng)絡(luò)層析成像技術(shù)的拓?fù)渫茢嗨惴ǖ奈墨I(xiàn)[3～12]類(lèi)似,本文僅考慮樹(shù)狀邏輯拓?fù)浣Y(jié)構(gòu),一般網(wǎng)絡(luò)拓?fù)淇梢酝ㄟ^(guò)多個(gè)樹(shù)狀拓?fù)淙诤系玫絒13,14].用T=(V,L)表示樹(shù)狀邏輯網(wǎng)絡(luò)拓?fù)淠Ｐ?其中V為網(wǎng)絡(luò)節(jié)點(diǎn)集合,代表網(wǎng)絡(luò)中的路由器和主機(jī),L為連接節(jié)點(diǎn)的鏈路集合.節(jié)點(diǎn)O∈V為T(mén)的根節(jié)點(diǎn).從根節(jié)點(diǎn)O到節(jié)點(diǎn)i之間的路徑用pi表示.節(jié)點(diǎn)集合R?V(無(wú)子節(jié)點(diǎn)的節(jié)點(diǎn))表示所有的葉節(jié)點(diǎn),即探測(cè)報(bào)文接收節(jié)點(diǎn),|R|為葉節(jié)點(diǎn)個(gè)數(shù).每一個(gè)非葉節(jié)點(diǎn)k都至少有一個(gè)子節(jié)點(diǎn),用c(k)表示節(jié)點(diǎn)k的子節(jié)點(diǎn)集合.每一個(gè)非根節(jié)點(diǎn)k有且僅有一個(gè)父節(jié)點(diǎn),用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é)點(diǎn)k的祖先節(jié)點(diǎn).對(duì)任意兩個(gè)葉節(jié)點(diǎn)i和j,用a(i,j)表示他們的最近公共祖先節(jié)點(diǎn).用集合U=V{O}表示非根節(jié)點(diǎn)集合.網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)集合,即非葉節(jié)點(diǎn)非根節(jié)點(diǎn)集合,用I=UR表示.以節(jié)點(diǎn)k為根節(jié)點(diǎn),葉節(jié)點(diǎn)集合D為目的節(jié)點(diǎn)的子樹(shù)用T(k,D)表示.

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

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

(1)0

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

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

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

3 基于最大公共路徑匹配的拓?fù)渫茢嗨惴?/h2>

3.1 節(jié)點(diǎn)對(duì)相似度估計(jì)

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

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

(1)

(2)

無(wú)背景流量時(shí),在節(jié)點(diǎn)j觀測(cè)到的探測(cè)包A1和A2的時(shí)延差Δt0為公共路徑上各鏈路的時(shí)延差之和,即探測(cè)包A1和A2的排隊(duì)時(shí)延差之和:

(3)

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

(4)

(5)

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

(6)

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

(7)

當(dāng)向每個(gè)節(jié)點(diǎn)對(duì)發(fā)送的“三明治”包數(shù)目較多時(shí),探測(cè)包發(fā)送時(shí)間較長(zhǎng),時(shí)鐘漂移會(huì)導(dǎo)致節(jié)點(diǎn)對(duì)相似度估計(jì)精度降低.從本文仿真實(shí)驗(yàn)結(jié)果來(lái)看,本文算法僅需向每個(gè)節(jié)點(diǎn)對(duì)發(fā)送少量探測(cè)包即可達(dá)到較高精度,當(dāng)發(fā)送探測(cè)包較少時(shí),探測(cè)包發(fā)送時(shí)間較短,故時(shí)鐘漂移對(duì)節(jié)點(diǎn)對(duì)相似度估計(jì)精度影響較小.基于“三明治”探測(cè)包重組的節(jié)點(diǎn)對(duì)相似度估計(jì)過(guò)程詳見(jiàn)算法1.

算法1 基于“三明治”探測(cè)包重組的節(jié)點(diǎn)對(duì)相似度估計(jì)算法

步驟3 對(duì)排序后的探測(cè)包A1和A2進(jìn)行重組,得到N個(gè)新的“三明治”包:

3.2 拓?fù)渫茢?/p>

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

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

(1)當(dāng)ρ(k)

(2)當(dāng)d(i,j)=ρ(k),k∈pi時(shí),a(i,j)為節(jié)點(diǎn)k.

假設(shè)當(dāng)前拓?fù)錇門(mén)=(V,L),新加入節(jié)點(diǎn)為節(jié)點(diǎn)j.本文通過(guò)節(jié)點(diǎn)j與當(dāng)前拓?fù)淙~節(jié)點(diǎn)進(jìn)行公共路徑長(zhǎng)度匹配,搜索節(jié)點(diǎn)j的插入位置.

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

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

ρ(f(i))

(8)

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

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

d(r,j)=ρ(i)

(9)

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

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

算法2 拓?fù)涓滤惴ˋddLeafNode(T,j,δ)

輸入 當(dāng)前拓?fù)銽=(V,L),新加入節(jié)點(diǎn)j,判定閾值δ

初始化k=O,D=R

①I(mǎi)fi==k,thenD′=DR(c)；ElseD′=R(i)R(c)；

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

輸出 加入節(jié)點(diǎn)j后新的拓?fù)銽=(V,L)

定理2 算法2將節(jié)點(diǎn)j插入到拓?fù)渲姓_位置的充分條件為節(jié)點(diǎn)對(duì)相似度的估計(jì)誤差小于δ/2,即

(10)

證明 當(dāng)算法2每次進(jìn)行最大公共路徑匹配都能找出正確的分叉節(jié)點(diǎn)時(shí),能將節(jié)點(diǎn)j插入到拓?fù)渲姓_位置.

(11)

由式(11)右半部分可得

(12)

由節(jié)點(diǎn)對(duì)相似度估計(jì)誤差小于δ/2,可得

進(jìn)一步可得到

(13)

(14)

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

d(r,j)<ρ(i)

(15)

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

ρ(f(i))

(16)

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

=2δ

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

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

(17)

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

綜上可得,算法2每次進(jìn)行最大公共路徑匹配都能找出正確的分叉節(jié)點(diǎn),能將節(jié)點(diǎn)j插入到拓?fù)渲姓_位置.故式(10)為算法2將節(jié)點(diǎn)j插入到拓?fù)渲姓_位置的充分條件.

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

算法3 拓?fù)渫茢嗨惴?/p>

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

步驟1 按TTL跳數(shù)信息從大到小的順序?qū)θ~節(jié)點(diǎn)進(jìn)行排序,得到:r1,r2,…rn；

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

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

AddLeafNode(T,ri,δ)；

輸出 拓?fù)銽=(V,L)

4 仿真

為對(duì)MCPM算法進(jìn)行綜合評(píng)價(jià),本文采用MATLAB模型仿真和NS 2仿真,分別對(duì)該算法拓?fù)渫茢嘈屎蜏?zhǔn)確性進(jìn)行評(píng)估,并與目前算法中性能較好的STI算法[9]和TSP算法[10]進(jìn)行比較.

4.1 MATLAB模型仿真

為對(duì)算法拓?fù)渫茢嘈蔬M(jìn)行評(píng)價(jià),本文采用BRITE拓?fù)渖晒ぞ呱梢幌盗泄?jié)點(diǎn)個(gè)數(shù)分別為100,200,…,1000的網(wǎng)絡(luò)拓?fù)?每種規(guī)模的拓?fù)渚?00個(gè).網(wǎng)絡(luò)拓?fù)淠Ｐ筒捎肳axman和BA兩種經(jīng)典模型,模型參數(shù)選擇為:α=0.15,β=0.2,m=2,MaxBw=1024,MinBw=2.選取網(wǎng)絡(luò)拓?fù)渲泄?jié)點(diǎn)度數(shù)較小的節(jié)點(diǎn)作為端節(jié)點(diǎn),在端節(jié)點(diǎn)中任選一節(jié)點(diǎn)作為源節(jié)點(diǎn),其余全部端節(jié)點(diǎn)作為目的節(jié)點(diǎn),即可構(gòu)成邏輯樹(shù)型拓?fù)?假設(shè)加性特征量測(cè)量過(guò)程中無(wú)噪聲干擾,即加性特征量的測(cè)量誤差為0.為每個(gè)鏈路隨機(jī)分配一個(gè)取值服從0.1至0.4上均勻分布的加性特征量.每次探測(cè)的節(jié)點(diǎn)對(duì)相似度為公共路徑上各鏈路加性特征量之和.

測(cè)量一個(gè)節(jié)點(diǎn)對(duì)相似度值需要向節(jié)點(diǎn)對(duì)發(fā)送一組指定數(shù)目的“三明治”包.將向一個(gè)葉節(jié)點(diǎn)對(duì)發(fā)送一組指定數(shù)目的探測(cè)包測(cè)量該節(jié)點(diǎn)對(duì)相似度視為一次探測(cè),則推斷拓?fù)渌铚y(cè)量的節(jié)點(diǎn)對(duì)相似度個(gè)數(shù)即為所需探測(cè)次數(shù).本文采用推斷網(wǎng)絡(luò)拓?fù)渌杼綔y(cè)次數(shù)作為算法效率的評(píng)價(jià)指標(biāo).對(duì)每個(gè)拓?fù)?先選取2個(gè)目的節(jié)點(diǎn)與源節(jié)點(diǎn)構(gòu)成一個(gè)二叉樹(shù)拓?fù)?然后分別采用MCPM、STI和TSP三種算法將其余目的節(jié)點(diǎn)逐個(gè)插入到二叉樹(shù)拓?fù)渲?比較各種算法所需的探測(cè)次數(shù).

圖3和圖4分別給出了Waxman和BA拓?fù)淠Ｐ拖?三種算法所需探測(cè)次數(shù)隨網(wǎng)絡(luò)拓?fù)涔?jié)點(diǎn)個(gè)數(shù)的變化情況,圖中數(shù)據(jù)為仿真100次取平均的結(jié)果.從圖中可以看出,三種算法所需探測(cè)次數(shù)都隨著網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)的增加而增加,其中TSP算法增加的最快,本文算法增加的最慢.在Waxman拓?fù)淠Ｐ拖?本文算法所需探測(cè)次數(shù)較STI算法減少51.35%至55.03%,較TSP算法減少85.46%至97.11%；在BA拓?fù)淠Ｐ拖?本文算法所需探測(cè)次數(shù)較STI算法減少50.41%至55.30%,較TSP算法減少78.56%至94.53%.在Waxman和BA拓?fù)淠Ｐ拖?本文算法拓?fù)渫茢嘈瘦^STI和TSP算法都有明顯提升.

4.2 NS 2仿真

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

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

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

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

5 結(jié)論

本文首先分析了基于“三明治”包時(shí)延差的加性特征量的原理和背景流量對(duì)探測(cè)包時(shí)延的影響,提出了一種基于探測(cè)包重組的節(jié)點(diǎn)對(duì)相似度估計(jì)方法.然后,在此基礎(chǔ)上通過(guò)對(duì)節(jié)點(diǎn)對(duì)相似度與最近公共祖先節(jié)位置的關(guān)系進(jìn)行分析,提出了一種基于最大公共路徑長(zhǎng)度匹配的拓?fù)渫茢嗨惴?仿真結(jié)果表明,本文提出的MCPM算法較STI算法和TSP算法在拓?fù)渫茢鄿?zhǔn)確性和效率方面都有明顯提高.

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

[2]趙洪華,陳鳴.基于網(wǎng)絡(luò)層析成像技術(shù)的拓?fù)渫茢郲J].軟件學(xué)報(bào),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.

姜守達(dá) 男,1964年出生黑龍江伊春,哈爾濱工業(yè)大學(xué)自動(dòng)化測(cè)試與控制系教授.主要研究方向?yàn)樘摂M試驗(yàn)技術(shù),網(wǎng)絡(luò)測(cè)量技術(shù),數(shù)字信號(hào)處理等.

E-mail:jsd@hit.edu.cn

尹文濤 男,1983年生于湖北孝感,哈爾濱工業(yè)大學(xué)自動(dòng)化測(cè)試與控制系博士研究生.主要研究方向?yàn)榫W(wǎng)絡(luò)測(cè)量與網(wǎng)絡(luò)層析成像技術(shù).

E-mail:huayichu@163.com

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

魏長(zhǎng)安 男,1981年生于河北承德,哈爾濱工業(yè)大學(xué)自動(dòng)化測(cè)試與控制系講師.主要研究方向?yàn)樘摂M試驗(yàn)技術(shù),自動(dòng)測(cè)試技術(shù)等.

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；責(zé)任編輯:梅志強(qiáng)

國(guó)家自然科學(xué)基金(No.61501135)

TP393

A

0372-2112 (2016)09-2189-08

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.09.025

猜你喜歡

加性網(wǎng)絡(luò)拓?fù)?/a>三明治

基于通聯(lián)關(guān)系的通信網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法

網(wǎng)絡(luò)安全與數(shù)據(jù)管理(2022年2期)2022-05-23 13:25:46

?2?4[u]-加性循環(huán)碼

阜陽(yáng)師范大學(xué)學(xué)報(bào)(自然科學(xué)版)(2022年1期)2022-04-02 12:35:16

三明治

中老年保健(2021年2期)2021-08-22 07:29:38

不同形狀的三明治

幼兒園(2019年8期)2019-09-09 16:04:00

電子制作(2018年23期)2018-12-26 01:01:16

企業(yè)家多重政治聯(lián)系與企業(yè)績(jī)效關(guān)系：超可加性、次可加性或不可加性

系統(tǒng)管理學(xué)報(bào)(2018年3期)2018-08-13 01:05:28

企業(yè)家多重政治聯(lián)系與企業(yè)績(jī)效關(guān)系：超可加性、次可加性或不可加性

系統(tǒng)管理學(xué)報(bào)(2018年2期)2018-08-13 01:04:38

勞斯萊斯古斯特與魅影網(wǎng)絡(luò)拓?fù)鋱D

汽車(chē)維修技師(2017年10期)2017-03-17 02:25:01

紐約市最著名的三明治

海外星云(2016年15期)2016-12-01 04:18:27

電測(cè)與儀表(2016年5期)2016-04-22 01:13:46