吳辰文，茹俊年，劉香麗，李志昌

蘭州交通大學(xué)電子與信息工程學(xué)院，蘭州730070

1 引言

本文基于丟包率的多播網(wǎng)絡(luò)拓?fù)渫茢嗨惴ǎ壳八谢趤G包率的多播網(wǎng)絡(luò)拓?fù)渫茢嗨惴ǘ家杂芯€網(wǎng)絡(luò)為基礎(chǔ)。文獻(xiàn)[1-2]描述了一種利用探測(cè)包丟包狀況推斷二叉樹拓?fù)浣Y(jié)構(gòu)的BLT（Binary Loss Tree）算法，在判斷兄弟節(jié)點(diǎn)的過程中引入了靜態(tài)判決門限值ε，將BLT算法從二叉樹拓?fù)渫茝V到一般樹，提出了通用樹拓?fù)渫茢嗨惴℅LT（General Loss Tree）。但是BLT和GLT算法都不能夠準(zhǔn)確地識(shí)別出只有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)。針對(duì)該問題，文獻(xiàn)[3]對(duì)BLT算法加以改進(jìn)，提出BHC（Binary Hamm ing Count）算法，該算法根據(jù)測(cè)量端到端的探測(cè)包丟包情況，結(jié)合節(jié)點(diǎn)的層次信息計(jì)算節(jié)點(diǎn)之間的海明距離，能夠快速準(zhǔn)確地推測(cè)出網(wǎng)絡(luò)拓?fù)洹５?dāng)網(wǎng)絡(luò)中某些鏈路出現(xiàn)丟包較為嚴(yán)重時(shí)，BHC算法將失效。為了解決BHC算法失效問題，提出BFHC，通過比較與分析，證明了本文算法能有效提高拓?fù)渫茢嗟臏?zhǔn)確性。

2 算法描述

2.1 BHC算法描述

利用多播丟包模型[1]，假設(shè)源節(jié)點(diǎn)0發(fā)送n個(gè)探測(cè)包，n(u1)表示節(jié)點(diǎn)u1收到的探測(cè)包數(shù)，nu1u2表示節(jié)點(diǎn)u1、u2同時(shí)收到的探測(cè)包數(shù)，同理，nu1u2…um表示節(jié)點(diǎn)u1，u2，…，um同時(shí)收到的探測(cè)包數(shù)。求鏈路丟包率有如下推導(dǎo)公式，若u1，u2，…，um是兄弟節(jié)點(diǎn)，則u1對(duì)應(yīng)的鏈路丟包率的估計(jì)值au1為：

BHC算法提出可以通過讀取探測(cè)包的TTL值來獲取節(jié)點(diǎn)u的跳數(shù)值u.hop。探測(cè)包經(jīng)過的路由數(shù)越多，其跳數(shù)值越大，由此引入了節(jié)點(diǎn)的層次信息。已知0為發(fā)送節(jié)點(diǎn)，R為接收節(jié)點(diǎn)集合，根據(jù)跳數(shù)值對(duì)接收節(jié)點(diǎn)集進(jìn)行分類，從跳數(shù)值最大為h=maxu∈R(u.hop)的節(jié)點(diǎn)集Lm(m=k)開始，從Lm中選擇海明碼距[4]最小的兩個(gè)節(jié)點(diǎn)u，v作為兄弟節(jié)點(diǎn)，節(jié)點(diǎn)u，v間的海明碼距表示為：

其中，n代表源節(jié)點(diǎn)發(fā)送的探測(cè)包數(shù)；⊕代表異或操作。

根據(jù)

判斷v′是否為u，v的兄弟節(jié)點(diǎn)，用a(r)表示它們的父節(jié)點(diǎn)，且將r加入跳數(shù)值為r.hop=m-1的節(jié)點(diǎn)集。令m=m-1，然后重復(fù)上述過程自底向上組織兄弟節(jié)點(diǎn)，直至根節(jié)點(diǎn)。在多數(shù)情況下，BHC算法推斷出的拓?fù)淠軌蜉^好地收斂于真實(shí)拓?fù)?。但是?dāng)網(wǎng)絡(luò)中某些鏈路丟包較為嚴(yán)重時(shí)，BHC算法的準(zhǔn)確度會(huì)明顯下降。多播網(wǎng)絡(luò)拓?fù)涫纠鐖D1所示。其中，4、5為兄弟節(jié)點(diǎn)；7為其非兄弟節(jié)點(diǎn)。若l→4對(duì)應(yīng)的路徑與1→5對(duì)應(yīng)的路徑丟包情況相似，而1→7對(duì)應(yīng)的鏈路丟包特別嚴(yán)重時(shí)，兄弟節(jié)點(diǎn)間的海明碼距Hd(u4，u5)就很可能比非兄弟節(jié)點(diǎn)間的海明碼距Hd(u5，u7)大（如表2），此時(shí)BHC方法失效。

圖1 待推測(cè)的二叉拓?fù)鋱D

2.2 HGLT算法描述

在HGLT[5-6]算法中，通過計(jì)算比較兄弟節(jié)點(diǎn)的最近父節(jié)點(diǎn)與非兄弟節(jié)點(diǎn)的最近父節(jié)點(diǎn)的估計(jì)值來區(qū)分兄弟節(jié)點(diǎn)是否為兄弟節(jié)點(diǎn)。如圖1所示，4、5節(jié)點(diǎn)的最近父節(jié)點(diǎn)為2，而4、5、7的最近父節(jié)點(diǎn)為1，計(jì)算n(1)(1-ε)＜n(2)來區(qū)分7是否為4、5的兄弟節(jié)點(diǎn)。

2.3 改進(jìn)的BFHC算法描述

在BFHC[7-9]算法中需要推斷出4、5、7的最近共同父節(jié)點(diǎn)，如無法推斷出4、5、7父節(jié)點(diǎn)的情況，并且在鏈路丟包率嚴(yán)重的情況下也能正確推斷出真實(shí)的網(wǎng)絡(luò)拓?fù)洌瑸榇颂岢龈倪M(jìn)的BFHC算法步驟如下：

（1）利用公式（1）計(jì)算各接收節(jié)點(diǎn)的丟包率。

（2）在Lm集合中，利用公式（2）計(jì)算Lm集合中具有最小海明碼距的節(jié)點(diǎn)；如果接收點(diǎn)的丟包率相近，則可判斷u，v為兄弟節(jié)點(diǎn)，否則，轉(zhuǎn)（3）。

（3）此時(shí)，有一條鏈路的丟包率相對(duì)于其他節(jié)點(diǎn)的丟包率過大（丟包率嚴(yán)重的情況下）時(shí)，利用公式（3）計(jì)算v′是否為u、v的兄弟節(jié)點(diǎn)已失效，所以改進(jìn)的算法是通過式（2）計(jì)算結(jié)果判斷u、v為兄弟節(jié)點(diǎn)，并計(jì)算出u、v的父節(jié)點(diǎn)為a(r)。

（4）根據(jù)兄弟節(jié)點(diǎn)對(duì)父節(jié)點(diǎn)的貢獻(xiàn)大于非兄弟節(jié)點(diǎn)對(duì)父節(jié)點(diǎn)的貢獻(xiàn)，可以采用公式（4）判斷v′是否為u、v的兄弟節(jié)點(diǎn)，公式為：

以待推測(cè)的二叉拓?fù)鋱D1為例。其中，4、5為兄弟節(jié)點(diǎn)；7為其非兄弟節(jié)點(diǎn)。若l→4對(duì)應(yīng)的路徑與1→5對(duì)應(yīng)的路徑丟包情況相似，而1→7對(duì)應(yīng)的鏈路丟包特別嚴(yán)重時(shí)，通過計(jì)算Hd(2，7)(1-ε0)＜Hd(2，5)來區(qū)別7是否為4、5的兄弟節(jié)點(diǎn)。

2.4 結(jié)果分析

通過表1計(jì)算可知，當(dāng)所有接收節(jié)點(diǎn)鏈路丟包率相近時(shí)，BHC算法可以推斷出網(wǎng)絡(luò)拓?fù)?；由?計(jì)算可知，當(dāng)某一條鏈路出現(xiàn)丟包嚴(yán)重時(shí)，BHC算法將失效；由表3計(jì)算可知，當(dāng)某一節(jié)點(diǎn)出現(xiàn)丟包率嚴(yán)重時(shí)，非兄弟節(jié)點(diǎn)與父節(jié)點(diǎn)接收探包數(shù)的估計(jì)值要大于兄弟節(jié)點(diǎn)。因此，通過比較節(jié)點(diǎn)集中的接收節(jié)點(diǎn)與父節(jié)點(diǎn)所接收探包數(shù)的估計(jì)值來區(qū)分兄弟節(jié)點(diǎn)是可行的。

表1 BHC算法計(jì)算值

表2 BHC算法失效計(jì)算值

表3 BFHC算法計(jì)算值

在BFHC算法中，以圖1為例，4、5為兄弟節(jié)點(diǎn)，根據(jù)4、5可知其父節(jié)點(diǎn)為2，當(dāng)7節(jié)點(diǎn)丟包率嚴(yán)重時(shí)，利用式（4）判斷7是否為節(jié)點(diǎn)4、5的兄弟節(jié)點(diǎn)。另外，本文算法可給定初始化區(qū)間讓其選擇一個(gè)判決門限初值ε0，此時(shí)ε0不一定小于所有內(nèi)部鏈路的丟包率，然后在每一次判斷出兄弟節(jié)點(diǎn)的同時(shí)，由式（1）估算出該節(jié)點(diǎn)對(duì)應(yīng)的鏈路丟包率，再根據(jù)式（3）、（4）計(jì)算海明碼距，并動(dòng)態(tài)地調(diào)整ε值，從而可以提高拓?fù)渫茢嗟臏?zhǔn)確率。

3 仿真實(shí)驗(yàn)與性能分析

HGLT算法在葉節(jié)點(diǎn)無法識(shí)別其父節(jié)點(diǎn)時(shí)，將無法識(shí)別其最近的共同祖先節(jié)點(diǎn)，此時(shí)HGLT算法也會(huì)失效。本文以BHC算法為基礎(chǔ)，利用NS2仿真平臺(tái)，通過BHC算法與BFHC比較與分析，來驗(yàn)證BFHC算法的有效性。如圖1所示。為了能夠正確推斷出網(wǎng)絡(luò)拓?fù)?，NS2仿真環(huán)境設(shè)置如下：邊緣鏈路參數(shù)為帶寬10M b/s，延遲10 m s；內(nèi)部鏈路參數(shù)為帶寬5 M b/s，延遲10 ms。每個(gè)路由傳輸?shù)木彌_區(qū)大小為10個(gè)數(shù)據(jù)包，并且支持多播路由，采用Droptail丟包策略。背景流量以TCP為主，同時(shí)包含適當(dāng)?shù)腢DP，UDP流量采用符合Pareto分布的開關(guān)型模型；探包產(chǎn)生過程符合Poisson分布。在數(shù)據(jù)采集過程中，統(tǒng)計(jì)的數(shù)據(jù)是不完全數(shù)據(jù)，采集頻率越小，統(tǒng)計(jì)數(shù)據(jù)的誤差就越大；反之，誤差越小，為了使數(shù)據(jù)更加精確，根據(jù)上面設(shè)置的仿真環(huán)境，采集100次不同時(shí)間段的觀測(cè)數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析。

從圖2可看出，當(dāng)各鏈路丟包率相似時(shí)，隨著發(fā)送探測(cè)包數(shù)的增加，兩種算法的性能幾乎一致。

圖2 丟包率相似時(shí)拓?fù)渫茢鄿?zhǔn)確率隨發(fā)包發(fā)送數(shù)量的變化

如圖3所示，在鏈路丟包較為嚴(yán)重時(shí)，BHC算法達(dá)到的最高準(zhǔn)確率為85%，即使發(fā)送包的數(shù)量不斷增加，拓?fù)渫茰y(cè)準(zhǔn)確率也不會(huì)上升；而在BFHC中，當(dāng)發(fā)送包數(shù)量增加時(shí)，推斷拓?fù)湓浇咏鎸?shí)拓?fù)洹?/p>

圖3 丟包率嚴(yán)重時(shí)拓?fù)渫茢鄿?zhǔn)確率隨發(fā)包發(fā)送數(shù)量的變化

綜上所述，BFHC的整體性能明顯優(yōu)于BHC算法，能夠有效地改善拓?fù)渫茢嗟臏?zhǔn)確性。

4 結(jié)束語

為了克服BHC算法在某些鏈路丟包嚴(yán)重時(shí)拓?fù)渫茢嗾`差較大的缺點(diǎn)，本文提出BFHC算法，根據(jù)非兄弟節(jié)點(diǎn)與父節(jié)點(diǎn)接收探包數(shù)的估計(jì)值要大于兄弟節(jié)點(diǎn)這一特性，利用它們之間的海明碼距Hd，并在計(jì)算中動(dòng)態(tài)地調(diào)整門限值ε，可有效地推斷出網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

[1]Duffield N G，Horow itz J，Presti F L，et a1.Multicast topology inference from measured end-to-end loss[J].IEEE Transactions on Information Theory，2002，48（1）：26-45.

[2]李勇軍，蔡皖東，王偉，等.基干端到端報(bào)文丟失的網(wǎng)絡(luò)拓?fù)渫茰y(cè)算法研究[J].通信學(xué)報(bào)，2007，28（10）：85-91.

[3]Tian Hui，Shen Hong.Multicast-based inference for topology and network：internal loss performance from end-to-end measure[J].Computer Communications，2006，29（11）：1936-1947.

[4]趙濤，蔡皖東，李惠賢.基于漢明距離的傳感器網(wǎng)絡(luò)分層拓?fù)浒l(fā)現(xiàn)算法[J].華中科技大學(xué)學(xué)報(bào)，2008（10）：82-86.

[5]吳文佳，張建中，張?jiān)i.基于丟包率的多播網(wǎng)絡(luò)拓?fù)渫茢嗨惴╗J].計(jì)算機(jī)工程，2010，36（1）：124-126.

[6]Rabbat M，Nowak R，Coates M.Multiple source，multiple destination network tomography[C]//Proc of IEEE INFO Com’04，Hong Kong，China.New York：IEEE Press，2004.

[7]Bu Tian，Duffield N，Presti F L，et al.Network tomography on general topologies[C]//Proc of ACM SIGMETRICS.New York：ACM，2010：21-30.

[8]Wu Chenwen.Study on topology inference method based on clustering and NT technology[C]//Proceedings of ICCSE2010，2010：977-980.

[9]吳辰文，閆毅郎.基于時(shí)間閾值丟包率估計(jì)的網(wǎng)絡(luò)斷層掃描技術(shù)[J].計(jì)算機(jī)工程，2011，37（9）：130-132.