基于丟包率的多播網(wǎng)絡(luò)拓撲推斷算法

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

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

1 引言

本文基于丟包率的多播網(wǎng)絡(luò)拓撲推斷算法，目前所有基于丟包率的多播網(wǎng)絡(luò)拓撲推斷算法都以有線網(wǎng)絡(luò)為基礎(chǔ)。文獻[1-2]描述了一種利用探測包丟包狀況推斷二叉樹拓撲結(jié)構(gòu)的BLT（Binary Loss Tree）算法，在判斷兄弟節(jié)點的過程中引入了靜態(tài)判決門限值ε，將BLT算法從二叉樹拓撲推廣到一般樹，提出了通用樹拓撲推斷算法GLT（General Loss Tree）。但是BLT和GLT算法都不能夠準(zhǔn)確地識別出只有一個子節(jié)點的節(jié)點。針對該問題，文獻[3]對BLT算法加以改進，提出BHC（Binary Hamm ing Count）算法，該算法根據(jù)測量端到端的探測包丟包情況，結(jié)合節(jié)點的層次信息計算節(jié)點之間的海明距離，能夠快速準(zhǔn)確地推測出網(wǎng)絡(luò)拓撲。但當(dāng)網(wǎng)絡(luò)中某些鏈路出現(xiàn)丟包較為嚴重時，BHC算法將失效。為了解決BHC算法失效問題，提出BFHC，通過比較與分析，證明了本文算法能有效提高拓撲推斷的準(zhǔn)確性。

2 算法描述

2.1 BHC算法描述

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

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

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

根據(jù)

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

圖1 待推測的二叉拓撲圖

2.2 HGLT算法描述

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

2.3 改進的BFHC算法描述

在BFHC[7-9]算法中需要推斷出4、5、7的最近共同父節(jié)點，如無法推斷出4、5、7父節(jié)點的情況，并且在鏈路丟包率嚴重的情況下也能正確推斷出真實的網(wǎng)絡(luò)拓撲，為此提出改進的BFHC算法步驟如下：

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

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

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

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

以待推測的二叉拓撲圖1為例。其中，4、5為兄弟節(jié)點；7為其非兄弟節(jié)點。若l→4對應(yīng)的路徑與1→5對應(yīng)的路徑丟包情況相似，而1→7對應(yīng)的鏈路丟包特別嚴重時，通過計算Hd(2，7)(1-ε0)＜Hd(2，5)來區(qū)別7是否為4、5的兄弟節(jié)點。

2.4 結(jié)果分析

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

表1 BHC算法計算值

表2 BHC算法失效計算值

表3 BFHC算法計算值

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

3 仿真實驗與性能分析

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

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

圖2 丟包率相似時拓撲推斷準(zhǔn)確率隨發(fā)包發(fā)送數(shù)量的變化

如圖3所示，在鏈路丟包較為嚴重時，BHC算法達到的最高準(zhǔn)確率為85%，即使發(fā)送包的數(shù)量不斷增加，拓撲推測準(zhǔn)確率也不會上升；而在BFHC中，當(dāng)發(fā)送包數(shù)量增加時，推斷拓撲越接近真實拓撲。

圖3 丟包率嚴重時拓撲推斷準(zhǔn)確率隨發(fā)包發(fā)送數(shù)量的變化

綜上所述，BFHC的整體性能明顯優(yōu)于BHC算法，能夠有效地改善拓撲推斷的準(zhǔn)確性。

4 結(jié)束語

為了克服BHC算法在某些鏈路丟包嚴重時拓撲推斷誤差較大的缺點，本文提出BFHC算法，根據(jù)非兄弟節(jié)點與父節(jié)點接收探包數(shù)的估計值要大于兄弟節(jié)點這一特性，利用它們之間的海明碼距Hd，并在計算中動態(tài)地調(diào)整門限值ε，可有效地推斷出網(wǎng)絡(luò)拓撲結(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]李勇軍，蔡皖東，王偉，等.基干端到端報文丟失的網(wǎng)絡(luò)拓撲推測算法研究[J].通信學(xué)報，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ā)現(xiàn)算法[J].華中科技大學(xué)學(xué)報，2008（10）：82-86.

[5]吳文佳，張建中，張元鵬.基于丟包率的多播網(wǎng)絡(luò)拓撲推斷算法[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]吳辰文，閆毅郎.基于時間閾值丟包率估計的網(wǎng)絡(luò)斷層掃描技術(shù)[J].計算機工程，2011，37（9）：130-132.