基于網絡斷層掃描技術的網絡拓撲推測方法研究
2008-12-31 00:00:00李貴山蔡皖東
計算機應用研究 2008年12期
(西北工業大學計算機學院，西安 710072)
摘 要：目前的網絡拓撲推測方法主要是基于網絡性能參數的極大似然估計方法，而其計算量會隨著網絡規模的增長而急劇增加，從而影響在實際網絡中的應用。討論了網絡斷層掃描在網絡拓撲推斷中的測量方法和推斷方法，提出了一種基于網絡斷層掃描技術的網絡拓撲快速推測方法，根據觀測節點測量數據的相似度推測網絡的邏輯拓撲結構。通過仿真研究表明，該方法推測準確且計算簡單，具有優勢，即使在發送較少報文的情況下，也可以得到較高的準確推斷率。
關鍵詞：網絡斷層掃描； 網絡拓撲推測； 報文丟失； 多播
中圖分類號：TP393 文獻標志碼：A
文章編號：10013695(2008)12381303
Study on topology inference method based on network tomography
LI Guishan， CAI Wandong
(School of Computer Science， Northwestern Polytechnical University， Xi’an 710072， China)
Abstract:These methods require knowledge of the network topology; therefore a first crucial step in the tomography process is topology identification. MLE method recently have been proposed as means to infer network logical topology， but the time spent on MLE increased sharply with the size of the network， which may restrict the technique to be used in practice. This paper described a fast approach to identify the logical network topology. This approach only needed to calculate the similarity degree based on the measurements to identify the network topology， which could accurately identify the network topology and saved more time than the present ones. Experiment proves the proposed algorithm in a simulated network and validated its accuracy and efficiency.
Key words：network tomography; network topology identification; loss performance; multicast
0 引言
為了預測和推斷網絡性能，必須了解網絡拓撲，這樣才能對整個網絡的鏈路情況有一個準確的判斷。隨著網絡規模的日益膨脹，網絡結構日趨復雜，已朝著分布化、非協作、異質管理和基于邊緣控制的方向演變，通過在網絡內部相關節點上采集有關數據的傳統測量方法已不能滿足現在網絡測量的需求。如何準確地掌握或預測網絡拓撲結構與網絡行為，已成為網絡性能測量與分析方法研究領域的重要目標和前提。常規的拓撲推測方法是基于路由器或路由器協作的，通過分析來自網絡內部資源的數據(如BGP路由表、ICMP Replies)，生成Internet拓撲或性能的報告[1，2]，但是由于各ISP之間的非協作性，使得這種方法受到網絡訪問權限的限制，只適合于在具有管轄權的網絡范圍內進行測量；另外，將大量路由器統計的性能數據傳輸給中心網管系統，需消耗大量帶寬，增加了網絡負荷[3]。鑒于這種內部測量方法的弊端，采用網絡斷層掃描[4]（network tomography，NT）技術成為近年來網絡測量的研究熱點，它利用端到端測量進行網絡拓撲及內部性能參數推測。在端到端測量的網絡拓撲推測方法研究中，主要是利用報文丟失性能[5，6]來推測網絡拓撲，其他可以利用的性能參數包括端到端的鏈路延時[7]、鏈路利用情況以及鏈路延時的變化[8]等。目前已經提出的基于網絡斷層掃描技術的網絡拓撲推測方法主要有極大似然方法[3，5，6，9]，是在已知端到端的報文丟失情況下，為所有可能的邏輯拓撲構建一個似然函數，找到一個拓撲結構使似然函數取得最大值。該方法的缺點是計算量會隨著網絡節點數量的增加而急劇增加，影響了其在實際網絡中的應用。本文提出了一種簡單快速的基于網絡斷層掃描技術的網絡拓撲推測方法，其根據邊緣觀測節點測量數據的相似度推測網絡的邏輯拓撲結構，無須計算額外的參數。本文給出了報文丟失模型，并在此基礎上詳細描述了網絡拓撲推測算法，并通過仿真分析，證明了該算法的可行性和準確率。
1 相關工作
網絡斷層掃描技術是基于對網絡中有限個節點的傳輸測量。使用統計學的原理來估算或推斷網絡的性能參數，可用如下線性模型表示:
Yt=AXt+ε
其中：Yt是在時間t對網絡中不同節點的測量結果向量;A為路由矩陣;ε為噪聲向量;Xt為和時間相關的測量參數( 如平均時延、隨機OD 流量、排隊時延等) 。
網絡斷層掃描技術的研究分為鏈路級參數推斷[10，11]（通過接收節點的網絡特性分析網絡鏈路級的特性，包括時延分布、丟包率和帶寬等參數估計）、網絡端到端流量估計[12，13] （目的是利用鏈路級的測量數據推斷網絡端到端的流量，是網絡鏈路級參數推理的反過程）和網絡拓撲推斷（根據網絡性能參數推斷網絡的拓撲結構）三個方面。基于網絡斷層掃描的網絡拓撲推斷分為兩個步驟:a)通過端到端測量獲得端到端的性能參數矩陣；b)根據端到端的性能參數矩陣推斷網絡的拓撲結構。端到端測量有組播網絡測量和單播網絡測量兩種。在組播網絡中，通過測量源節點向接收節點發送大量的測量數據，利用接收節點觀察接收到測量分組的情況得出網絡的特性矩陣[14]。而單播網絡中要獲得不同節點間的相關性比組播網絡復雜很多，通常采用鄰接分組對[15，16]和三明治分組列車[17] 兩種方式獲得網絡性能矩陣。
網絡拓撲推斷一般利用反演方法進行，目前主要有DBT(deterministic binary tree)算法[5]、LBT( likelihoodbased binary tree)算法[9]和分層算法[18]等網絡拓撲推斷算法。
DBT算法主要應用于組播網絡拓撲推斷。LBT 算法是Coates 提出的一種全局搜索算法，其思想是在所有可能樹結構集合F中，找出真實樹結構T*， 然后利用最大似然法推測真實拓撲樹。但由于所有可能樹的數量巨大，計算所有可能樹的概率值是不可能的，搜索只在一部分可能樹中進行。分層算法是由Meng 等人提出的一種基于圖論的網絡拓撲推斷算法，其思想是根據接收節點對的相似性將節點劃分成不同的集合，逐級劃分并加入新的節點，最后成為一個大的集合。
網絡拓撲推斷的關鍵是網絡的性能測量與拓撲推斷。對于性能測量，在不知道網絡拓撲的情況下如何合理選擇接收節點比較困難；同時測量的次數和測量結果的精確度緊密相關，因此如何估計測量精度對拓撲推斷的影響及如何在測量精度與測量流量之間取得最佳效果也是一個技術難點。對于拓撲推斷，由于推斷中假定不同測量數據包之間是相互獨立的，而在實際的網絡中這些假定并不成立，如何減少假定的限制是一個技術難點。
2 網絡報文丟失模型
本文的推測方法基于多播，假定多播網絡中沒有環路，物理多播樹包括網元（網絡節點）及其通信鏈路。而邏輯多播樹包括物理多播樹的分支節點和它們之間的邏輯鏈路。邏輯鏈路包括一條或多條物理鏈路。因此邏輯鏈路中除根節點和葉子節點外的中間分支節點至少有兩個子節點。可用以下方法由物理多播樹構造邏輯多播樹：除根節點外刪除只有一個子節點的中間節點，調整鏈路集合，將父節點與子節點直接連接。
2. 1 邏輯多播拓撲模型
用T＝（V，L）來描述網絡的邏輯拓撲。其中：V代表拓撲中的邏輯節點集合，L表示連接節點的邏輯鏈路集合。根節點0是探測報文的根節點，用0∈V表示，所有探測報文從0被多播到整個網絡中。節點集合RV表示所有的葉節點，是探測報文的接收節點。若一條鏈路的兩個端點不是根節點和葉節點，則稱此鏈路為內部鏈路。每個非葉節點k都至少有一個子節點，用集合d(k)＝{di(k)|1≤i≤nk}表示。nk為節點k的子節點數；每個非根節點k均有一個父節點，用f(k)表示。通常將(f(k)，k)∈L稱為鏈路k。對于正整數n，定義f 1＝f且f n(k)=f(f n-1(k))，如果k＝f n(j)成立，則稱節點j是節點k的子孫節點。用a(U)表示集合UV中所有節點最近的祖先節點，如果集合U中的節點具有相同的父節點，即f(k)＝a(U)，則U中的節點k∈U稱為兄弟節點。（V(k)，L(k)）表示以節點k為根的子樹，R(k)＝R∩V(k)。
2. 2 報文丟失模型
在2.1節所述拓撲模型的基礎上，假設樹T中任一鏈路的報文丟失率服從獨立的Bernouli分布。每個探測報文成功到達鏈路k的概率為pk。用隨機過程Z＝(Zk)k∈V描述節點接收探測報文的情況，如果報文到達了節點k∈V，則隨機變量Zk ＝1；否則Zk ＝0。對于j∈d(k)，如果Zk ＝0，則有Zj ＝0。如果用布爾變量Z(l)k表示第l個探測報文到達節點k的情況，那么當發送探測報文的總數為n時，k節點的探測報文的到達情況就可以用“01”序列{Z(m)k}，1≤m≤n來表示。其中：0表示對應的探測報文沒有到達該節點；1表示到達了該節點。
如果內部節點k在一次探測報文發送過程中沒有接收到該報文，那么它的所有子孫節點d(k)均不會接收到此次報文；反之，如果非根節點k在一次探測報文發送的過程中成功地接收到該報文，那么它的所有祖先節點a(U)均收到此次報文。基于在邊緣節點觀測到的報文接收情況和上述關系，假設節點i和j有著共同的父節點k，可以用式（1）[19]對網絡內部節點的報文丟失情況進行推測：
Z∧k={Z(m)i∨Z(m)j， m=1，2，…，n}
（1）
因為當一個內部節點接收到某次探測報文，同時丟失在通往其子孫節點的鏈路的概率非常小，隨著探測次數的增加，對結果的影響可以忽略。
3 推測方法
網絡斷層掃描測量方法是在網絡邊緣進行的，只有在葉節點才可以觀測到報文丟失情況。本文的推測方法基于多播，并利用探測報文在共享鏈路上的丟失情況是相同的這一事實，選擇節點間相似度最大的作為兄弟節點，因為共享鏈路越多，探測結果的相似度就越接近。為了推測網絡邏輯拓撲結構，需要先定義節點間的相似度函數，依據節點間的相似度來推斷出網絡拓撲，通過所測得的性能值對相關節點進行遞歸分組，最后可以得到網絡拓撲。
3. 1 節點間的相似度函數
定義1 設Zi、Zj分別為節點i和節點j的報文丟失情況，Zi＝{ Z(n)i}， i∈V，Zj＝{Z(n)j}， j∈V，|Zi|＝|Zj|＝n。節點i報文丟失情況和節點j報文丟失情況的相似度函數為
SDij=∑nm=1(Z(m)i+Z(m)j)
(2)
由定義可知，節點i和j的觀測值Z(m)i和Z(m)j同時為0的次數越多，節點之間的相似度越大。當節點i和j是兄弟節點且觀測值Z(m)i和Z(m)j同時為0時，有兩種原因造成這種情況：a)多播報文丟失在其父節點或祖先節點上；b)報文成功到達它們的父節點，但是同時丟失在鏈路i和j上。由上面的討論可知，這種情況出現的概率很小，顯然隨著測量次數n的增加，其兄弟節點的相似度逐漸增強；其次，非兄弟節點間探測報文同時為0的次數顯然小于兄弟節點間探測報文同時為0的次數。本文就是利用上述思想，對網絡拓撲進行推測的。
3. 2 推測算法
根據多播網絡的特點可知，發送節點發送的報文在到達網絡內部的路由器節點后，這些報文在內部節點被復制，然后再發送到它的各個分支上。因此可以推斷，如果某個報文到達了某節點的子節點中的一個，其必然到達了這個節點。所以兩兄弟節點的報文丟失分布具有最大的相關性，父節點的報文丟失分布是其兩個子節點的報文丟失的或。基于二叉樹的網絡邏輯拓撲方法首先從節點集合中，計算所有葉子節點兩兩間的報文觀測結果SD值并選擇SD值最小的葉子節點作為兄弟節點，為其構建父節點，并根據式(1)推測父節點的報文丟失情況。在葉節點集合中用構建的父節點代替這對兄弟節點。重復上述過程直至節點集的大小為1，最終就可以推測出整個網絡的拓撲結構。下面的算法詳細描述了網絡邏輯拓撲結構的推測方法。
輸入：葉節點集合R包括葉節點接收報文情況(Z(i)k)i=1，…，nk∈R。
a)計算葉節點集合兩兩元素之間的SDij值，并從中找尋最大的SDuv。
b)在葉集合R中加入新的節點k為節點u、v的父親節點，并將節點u、v從集合R中除去。
c)估計新加入父親節點k的報文接收情況Z∧k=Z(m)u∨Zmv（m=1，2，…，n）。
d)重復上述過程直到葉節點集合中剩余一個元素。
輸出：根據父子關系得到網絡的邏輯拓撲結構。
4 仿真實驗
為了驗證算法的有效性，用NS2[20]進行了仿真實驗。用16個節點的二叉樹表示網絡拓撲，如圖1所示。圖中每條鏈路的帶寬為1 Mbps、傳輸延時10 ms、采用DropTail策略丟棄報文、隊列大小為10。另外為了在仿真過程觀測到報文丟失，仿真過程中引入了error model，設定鏈路1的報文丟失概率為0.02，鏈路2和3的報文丟失的概率是0.08，鏈路4~7的丟失概率是0.05，其余鏈路的丟失率設置為0.1。探測報文由Exponential產生，報文大小為200，idle time為 200 ms， burst time為300 ms。報文從節點0，自頂向下被多播到網絡中每個節點。
在實驗中，每發送1 000個探測報文在葉節點收集一次實驗數據，作為一次采樣。進行100次數據采樣，并統計其中正確推測網絡邏輯拓撲的次數。圖2中顯示了準確推測出如圖1所示邏輯拓撲比率隨探測報文數量變化關系。從中不難發現隨著發送探測報文數量的增加，能夠正確推測網絡拓撲的次數也在增加，正確推測的比率逐漸收斂于1。在發送的報文數量大約170左右，正確推測網絡的次數達到81次，正確推測的比率接近0.8；在發送的報文數量大約300左右，正確推測網絡的次數達到92次，正確推測的比率接近0.9。因此可以通過發送較少的報文推測出比較準確的網絡邏輯拓撲結構。
5 結束語
基于節點相似度的網絡拓撲推測方法是通過端到端的測量來推測網絡的邏輯拓撲結構，無須網絡內部設備的協作。其相對于現有推測方法，計算量較小，且不會隨著網絡規模的增加，計算量急劇增加。通過仿真驗證了該方法準確，即使在發送較少報文的情況下，也可以得到較高的準確推斷率。
參考文獻：
[1]GOVINDANR， REDDYA. An analysis of Internet interdomain topolo and route stability[C]//Proc of IEEE INFOCOM’97. Washington DC:IEEE Computer Society，1997: 850857.
[2]GRIFFINT G， WILFONG G. An analysis of BGP convergence properties[C]//Proc of ACM SIGCOMM’97.New York:ACM，1999:277288.
[3]CASTROR， COATESM. Maximum likelihood identification of network topology from endtoend measurement，TREE0109[R]. Houston: Rice University， 2002.
[4]COATESM， ALFREDO H， NOWAKR， et al. Internet tomography[J]. IEEE Signal Processing Magazine， 2002，19(3): 4765.
[5]DUFFIELDN， HOROWITZJ， PRESTIF， et al. Multicast topology inference from endtoend loss[J]. IEEE Trans on Information Theory， 2002，48(1): 2645.
[6]CACERESR， DUFFIELDN G， HOROWITZ J. Loss based inference of multicast network topology[C]//Proc of IEEE Conference on Decision and Control. Phoenix:IEEE Press， 1999:30653070.
[7]DUFFIELDN， HOROWITZJ， PRESTIF， et al. Multicast topology inference from endtoend measurements， Report ofITC Seminar on IP Traffic Measurement， Modeling and Management[R]. [S.l.]: ATT LabsResearch， 2000.
[8]HUITIAN， HONGSHEN. An improved algorithm of multicast topology inference from endtoend measurements[J].International Journal of Communication Systems， 2006，19(8): 935953.
[9]CASTROR， COATESM， GADHIOKM. Maximum likelihood network topology identification from edgebased unicast measurements[C]//Proc of ACM Sigmetric. New York:ACM Press，2002:1120.
[10]DUFFIEDN， JOSEPHH， DONT. Multicastbased loss inference with missing data[J]. IEEE Journal on Selected Areas in Communications， 2002，20(4):700713.
[11]TSANGY， COATESM， NOWAKR. Nonparametric Internet tomography[C]//Proc of IEEE International Conference on Acours， Speech， and Signal Processing. Orlando:[s.n.]，2002:20452048.
[12]VARDIY. Metrics useful in network tomography studies[J]. IEEE Signal Processing Letters，2004，11(3):353355.
[13]LIANG Gang， YU Bin. Maximum pseudo likelihood estimation in network tomography[J]. IEEE Trans on Signal Processing， 2003，51(8):20432053.
[14]DUFFIELDNG， HOROWITZJ， PRESTI LF. Adaptive multicast topology inference[EB/OL]. (20020807). http://www.research.att.com/~duffield/papers/dhl01adapt.pdf.
[15]MENGFUS， ALFREDO H. Unicastbased inference of network link delay distributions with finite mixture models[J]. IEEE Trans on Signal Processing， 2003，51(8):22192228.
[16]TSANGY， COATESM， NOWAK R. Network delay tomography[J]. IEEE Trans on Signal Processing， 2003，51(8):21252136.
[17]COATROR， COATESM， GANG LIANG， et al. Network tomography: recent developments[J]. Statistical Science， 2004，19(3):499517.
[18]SHIH M S， ALFREDO HI.Topology discovery on unicast networks:a hierarchical approach based on endtoend measurements[EB/OL]. [2005]. http://www.eecs.umich.edu/~msim/Publications/cspl357.ps.pdf.
[19]ZHU Weiping， GENG Zhi. A bottomup inference of loss rate[J]. Computer Communications，2005，28(4):351365.
[20]Information Sciences Institute of University of Southern California. The network simulator 2[EB/OL]. www.isi.edu/nanam/ns2.
