基于丟包率的多播網絡拓撲推斷算法

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

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

1 引言

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

2 算法描述

2.1 BHC算法描述

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

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

其中，n代表源節點發送的探測包數；⊕代表異或操作。

根據

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

圖1 待推測的二叉拓撲圖

2.2 HGLT算法描述

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

2.3 改進的BFHC算法描述

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

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

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

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

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

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

2.4 結果分析

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

表1 BHC算法計算值

表2 BHC算法失效計算值

表3 BFHC算法計算值

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

3 仿真實驗與性能分析

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

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

圖2 丟包率相似時拓撲推斷準確率隨發包發送數量的變化

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

圖3 丟包率嚴重時拓撲推斷準確率隨發包發送數量的變化

綜上所述，BFHC的整體性能明顯優于BHC算法，能夠有效地改善拓撲推斷的準確性。

4 結束語

為了克服BHC算法在某些鏈路丟包嚴重時拓撲推斷誤差較大的缺點，本文提出BFHC算法，根據非兄弟節點與父節點接收探包數的估計值要大于兄弟節點這一特性，利用它們之間的海明碼距Hd，并在計算中動態地調整門限值ε，可有效地推斷出網絡拓撲結構。

[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]李勇軍，蔡皖東，王偉，等.基干端到端報文丟失的網絡拓撲推測算法研究[J].通信學報，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]趙濤，蔡皖東，李惠賢.基于漢明距離的傳感器網絡分層拓撲發現算法[J].華中科技大學學報，2008（10）：82-86.

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