網絡拓撲識別：基于ｔｒａｃｅｒｏｕｔｅ的層析成像方法
2009-01-01 00:00:00廖海亮胡光岷錢峰楊志豪
計算機應用研究 2009年1期
（電子科技大學 寬帶光纖傳輸與通信網技術教育部重點實驗室， 成都 610054）
摘 要：針對傳統的網絡拓撲識別方法（如traceroute）無法完成包含不協作節點的拓撲識別以及基于網絡層析成像技術的拓撲識別方法的復雜性和不確定性問題，提出一種基于traceroute的層析成像技術的拓撲識別方法。該方法可通過提出的最小相似度聚類算法和匿名節點構造歸并算法，將網絡層析成像獲得的拓撲信息與traceroute探測結果融合，構成最終的拓撲結構。NS2的仿真表明，該方法不僅可識別包含不協作節點的網絡拓撲，且所使用的探測包的數量也大大減少。
關鍵詞：跟蹤路由；匿名路由；網絡層析成像；三明治包；聚類分析；遞歸算法
中圖分類號：TP39302 文獻標志碼：A
文章編號：10013695(2009)01027604
Network topology inference:tomography method based on traceroute
LIAO Hailiang，HU Guangmin，QIAN Feng，YANG Zhihao
(Key Laboratory of Broadband Optical Fiber Transmission Communication Networks， University of Electronic Science Technology of China， Chengdu 610054， China)
Abstract:To the problem in the traditional network topology(for instance，traceroute) that the network topology which contained uncooperative routers couldn’t be inferred and the problem of complexity and indetermination in topology inference based on tomography， this paper introduced a network topology inference method based on traceroute and tomography. This method combined the traceroute result with the topology information obtained by tomography to construct a final topology using minimum similarity cluster algorithm and merging and constructing anonymous routers algorithm.The simulation on NS2 shows that this method not only be able to infer the network topology which contains uncooperative routers， but also enormously reduce the number of probes.
Key words:traceroute; anonymous router; network tomography; sandwich probe; clustering analysis; recursion
0 引言
網絡拓撲識別是利用各種測量手段對所關心網絡的邏輯拓撲進行推測。傳統的網絡拓撲識別法（如traceroute、DNS zone transfer）假定所有的中間節點均可協作，并根據中間路由器反饋的探測包來推測網絡的拓撲結構，通常需要中間節點的協作和協議的支持。這類網絡拓撲識別法最早由R.Siamwalla等人[1]提出，包括基于ping/廣播ping的方法、基于traceroute的方法以及基于DNS zone transfer的方法。隨著網絡規模的不斷擴大和對安全性的要求越來越高，節點間的協作變得越來越困難，該方法的實施也變得越來越困難。基于網絡層析成像的方法只通過對網絡端到端的測量，無須中間節點的協作，通過主動發送探測包或者被動收集網絡中的信息來識別拓撲結構，已成為國內外學術界的研究熱點。
網絡拓撲識別的層析成像[2]方法假定所有中間節點均不協作，通過發送端到端的探測包收集并分析探測包的統計特征（如時間差的平均值、方差、丟包率等），推測網絡拓撲。Ratnasamy等人在該方法的研究上做了先驅工作。他們利用向節點對廣播發送多包組的方法收集共享鏈路的丟包率信息，利用DBT算法 (deterministic binary tree classification algorithm) 實現二元邏輯狀拓撲的識別[3，4]。DBT算法同樣被用于利用多包組時延等測量度量的拓撲識別。Castro等人在單播網絡測量方面提出重大改進，他們提出了一種利用共享鏈路隊列延遲的sandwich探測方法，并提出ALT算法(agglomerative tree algorithm)實現拓撲重構；為使此方法不用設定門限并適用于一般樹結構，Coates等人[5]繼而提出了反轉跳馬爾可夫鏈蒙特卡洛（reversible jump Markov chain Monte Carlo）算法進行最大似然估計的拓撲識別；Shin Mengfu等人[6]通過建立有限混合模型獲得sandwich包對均值的時延差分布，進而采用圖聚類的方法獲得網絡拓撲結構。相對于傳統的拓撲識別方法，網絡拓撲識別的層析成像方法存在的主要問題是：由于假設中間所有路由器節點均不協作，造成探測包發送數量過多、求解不穩定、多解性強等缺陷，嚴重影響了方法的實用性。
傳統網絡拓撲識別法的缺陷是要求大量的中間路由器配合，這在實際的大型網絡中往往難以辦到；網絡層析成像假設所有中間路由器均不協作，增大了測量工作的難度。本文認為在實際的大規模網絡測量問題中，要求大量的中間路由器配合是很難的，假設所有中間路由器均不協作也是沒有必要的，在網絡中必然存在一些不協作節點，也必然存在一些可協作節點。為此本文結合兩類拓撲識別法的優點，提出一種基于traceroute的網絡拓撲層析成像法。該方法首先利用traceroute探測信息構造一棵不完整的初始拓撲樹（因為部分中間節點不協作，因而不能獲得完整的拓撲信息），以最少的探測包對未知拓撲進行類似網絡層析成像的探測，通過遞歸調用最小相似度聚類算法和匿名節點構造歸并算法，將網絡層析成像獲得的拓撲信息與traceroute探測結果融合，構成最終的拓撲結構。NS2的仿真表明本文提出的方法可以取得不錯的效果。
1 網絡拓撲識別的背景
11 網絡拓撲識別問題表述
T=（V，E），V為樹的節點集合，V=｛v0｝∪Vr∪Vi。其中：Vr為葉節點集合，Vr={v1，v2，…，vN}，| Vr|=N；Vi為中間節點集合，假設|Vi|=k，Vi={R1，R2，…，Rk}，k為中間節點的個數，是待估計的參數。要求的是中間節點集合Vi以及邊集E。
12 匿名路由器的影響
基于traceroute的網絡拓撲識別是利用中間節點返回的ICMP應答報文信息來識別目標網絡的拓撲結構。Jin Xing等人[7]在對基于traceroute的網絡拓撲識別方法研究中發現了匿名路由器的問題，并提出了IMA算法(isomap merging algorithm)來解決匿名路由器的問題。但是這個算法只能合并不返回ICMP報文的匿名路由器（也就是下面提到的a)類或b)類匿名路由），對于完全丟棄任何ICMP報文的匿名路由器（如c)類匿名路由器），該算法不能進行處理。匿名路由器根據其對ICMP報文不同的處理方式，可以分為以下三類：
a)不回復ICMP應答報文。在這種情況下，只知道這個地方有一跳，但是不知道這個中繼節點的任何信息。在traceroute的結果中這種路由器顯示為*。
b)只在輕載時回復ICMP應答報文，給拓撲識別帶來不穩定性。
c)丟棄ICMP應答報文。在這種情況下，這個中繼節點以及其后的鏈路將變得不可測量。在traceroute的結果中這種路由器以及其后的節點均將超時，并被顯示為*。
這三種匿名路由器的存在將給網絡拓撲識別帶來巨大的問題。其中如果c)類匿名路由存在，將只能識別源節點到這個匿名路由的網絡，其后的網絡將不可識別；a)類匿名路由和b)類匿名路由的存在也會帶來路由冗余的問題。如果匿名路由存在于某個節點，只知道這個節點上有一跳，而不知道這一跳的具體信息，無法將每條鏈路的匿名路由器合并起來，這樣就會造成匿名路由器的冗余，如圖1所示。
13 基于網絡層析成像的拓撲識別原理
131 一些基本的定義
par(v):節點v的父節點；
節點v的子節點集：c(v)={v′∈V:par(v′)=v}；
Pi:根節點到節點i的鏈路；
節點對(i， j)的探測樹t(i， j)=Pi∪Pj；
a(i， j):節點對(i， j)的最近公共祖先節點；
節點對(i， j)的相似度γi， j：標志了根節點到a(i， j)的長度；
以v為公共祖先節點的測量樹集T(v)={t(i， j):a(i， j)=v，i 混合因子a(v)=P(a(i，j)=v)=|T(v)|/v∈Vi|T(v)|。 132 三明治(sandwich)包探測原理 端到端的測量使用sandwich單播探測包用于獲得一系列滿足單調性并能反映共享鏈路特征的量度。每次測量結果均由在某個接收點處通過一個三包組中首尾兩個探測包到達它的時間差記錄。每個sandwich探測包由三個包組成[8]，即兩個目的為同一接收點的小包與一個目的為另一接收節點的較大包，它們相互獨立發送。三明治包探測法的理論依據是在共享鏈路上，第二個小探測包排在大包之后，從而使大探測包將兩個小包分開。三包組的三個包在經過中間節點時，由于中間大包在中間節點排隊的時延較長，使得兩個小包間的時延變大。兩個小包到達目的節點的時間差就與這個節點和其他接收節點共享的鏈路部分的長度有關。三明治包的原理可以用圖2來說明。 三明治包的任何一次測量均以一對節點為目標，實際上測量的是共享鏈路Pa(i， j)的長度特征，即節點對(i， j)的相似度γi，j，這個值反映了一個節點對的共享鏈路的層次信息。假設在整個測量過程中網絡拓撲是不變的，且測量網絡具有以下統計特性[6]： a)空間獨立性。不同鏈路的包延遲是獨立的。 b)時間獨立性。在一條鏈路上包延遲是獨立同分布的。 c)延遲一致性。不同的包組在經過同一條共享鏈路的排隊延遲是一致的。 d)相似度同分布。對于i、 j、k、l∈Vr，且i≠j，k≠l，若a(i， j)=a(k，l)，當測量次數n→∞時，P(|γi， j -γk，l |→0)=1。 對于t(i， j)∈T(v)的測量值γi， j，根據中心極限定理和統計特性d），應該是獨立同分布且服從高斯分布，所以能夠得到所有測量值所服從的混合高斯模型[6]，其表達式如下： f(γi， j)=v∈Via(v)(γi， j;θv) 2 結合traceroute的基于最小相似度分層聚類的拓撲識別算法 21 拓撲樹的數據結構組織 拓撲樹的每個節點包含五個域：a)nodeID，節點的ID；b)nodeType，節點類型，普通或匿名路由器；c)layer，節點所在的層次；d)children，指針項，指向子節點（這個節點的下層節點）；e)brothers，指針項，指向兄弟節點（這個節點的同層節點）。 由于拓撲樹為多叉樹，可這樣規定其數據結構，它的children指向它的其中一個子節點，而它的其他子節點由這個子節點的brothers以鏈式方式指明。這種數據結構如圖3所示。 22 初始樹構造算法 筆者根據traceroute的探測結果得到一棵不完整的初始拓撲樹。算法(算法1)描述如下： ConstructInitTree { 根據第一條traceroute結果構造初始樹； for每條traceroute結果do { this=初始樹的根節點； for這條traceroute結果的每一個節點ID do { if這個ID是匿名路由 把這個ID的節點加到this的子節點集的最后； this=新加節點； else if這個ID的節點已存在于this的子節點集中 this=這個節點； else 把這個ID的節點加到this的子節點集的最后； this=新加節點； } } } 23 最小相似度聚類算法 根據統計特性原則d)，兩個節點對(i， j)和(k，l)，如果a(i， j)=a(k，l)，那么γi，j =γk，l 。但由于誤差的存在，這兩個值是不可能完全相等的。該算法就是為了消除這種誤差而提出的。在策略上，可以采用全局的最小距離聚類或分層的最小相似度聚類。但是，對于前一種策略，如果a(i， j)≠a(k，l)，而γi， j ≈γk，l，采用這種策略就會發生聚類的錯誤，將本不是一類的數據聚成一類。所以本文采用后一種策略。與前一種策略不同，分層的最小相似度聚類算法只考慮當前有效數據并只聚類這些數據中值最小的那一類數據，既有效地避免了其他層數據的干擾，逐步縮小有效數據的范圍，又提高了聚類算法的準確性。算法（算法2）描述如下: MiniCluster(max) { while(true) { 找到有效數據中的最小數據； 比較其他有效數據與最小數據之間的差值； 找出差值最小和次小的兩個數據； 把差值最小的那個數據和最小數據作加權平均； 把差值最小的那個數據置為無效； if（次小差值＞THRESHOLD*最小差值次小差值＞max break; } } 24 匿名節點構造和歸并算法 本文用三明治包測量技術來獲取每個節點對的相似度。由于初始拓撲樹已經含有部分的拓撲信息，可以利用這些信息來減少獲取節點對的相似度所需要發送的三明治包的數目，這個策略在該算法中稱之為分級發送策略。具體策略如下：對于待測中間節點v的所有葉子子孫節點，如果其中任意一個節點對(i， j)的探測樹t(i， j)可以由初始樹確定，并且其公共祖先節點a(i， j)是節點v，那么這個節點對所需要發送的三明治包的個數為正常發送數目的1/10，并將該節點對的數據置為參考數據，找出參考數據中的最大值作為minCluster()算法的參數。如果節點對(i， j)的探測樹t(i， j)可以由初始樹確定，且其公共祖先節點a(i， j)不是節點v，不對其進行三明治包測量。匿名節點構造和歸并算法用于處理由算法1得到的初始拓撲樹中的匿名路由器。b）類匿名路由可以看做是部分的a)類匿名路由，在本文中a）b)類匿名路由在拓撲圖中記為0。由圖1可以看出，這類匿名路由器存在很多冗余，算法3要對這類匿名路由進行歸并。c)類匿名路由在拓撲圖中記為 *。這類匿名路由情況比較復雜，首先要根據三明治包探測數據來判斷是否應該在這個匿名路由與相應目標節點之間添加一個c)類匿名路由，然后再對這個節點調用該算法對其子節點進行歸并處理。算法（算法3）描述如下： AnonymousRouterModification(Node*pNode) { if pNode是葉節點 return； if pNode的子節點集需要進行構造或者歸并處理 { 計算以pNode為根節點的樹有哪些葉子節點； 對這些葉子節點進行分級發送三明治包； max=參考數據中的最大值； 對有效的探測數據調用MinCluster(max)進行處理； if(pNode為*型匿名路由) { min=有效的探測數據中的最小值； for所有有效的三明治探測數據detect { if(detect＞min) 在pNode和detect相應的兩個葉節點之間分別添加一個*型匿名路由（BirthMove()操作）； } } 把pNode的所有下層子節點分成確定節點集、0型匿名節點集、*型匿名節點集； for所有v1，v2∈0型匿名節點集，v1≠v2 { min=有效的探測數據中的最小值； detect=v1最左葉節點和v2最左葉節點的測量值； if(detect＞min) merge(v1，v2); } for所有v1，v2∈*型匿名節點集，v1≠v2 { min=有效的探測數據中的最小值； detect=v1最左葉節點和v2最左葉節點的測量值； if(detect＞min) merge(v1，v2); } } for所有pNextNode∈pNode的下層子節點 AnonymousRouterModification(pNextNode); } 3 算法仿真 本文通過NS2仿真軟件模擬對仿真網絡的三明治包的發送和收集測量數據，并對一棵測量樹的數據用MATLAB進行求均值處理。其所有主體算法均用C++編寫并在Microsoft Visual C++ 6.0平臺上實現。 仿真網絡的原始拓撲如圖4所示。中間節點中，0代表a)類或者b)類匿名路由；*代表c)類匿名路由。 用NS2得到的三明治包探測數據和利用traceroute得到的結果如圖5所示。在traceroute的探測數據中，#為結束符，a代表10號目標節點；b代表11號目標節點。 對一棵樹的先序遍歷就是先遍歷這棵樹的根節點，再對以這個節點的子節點為根節點的樹遞歸地用這種方法進行遍歷。在遍歷過程中，每經過一個節點就輸出該節點的信息，這些節點信息包括節點的ID、節點的層次以及節點的類型。根據算法的輸出數據而重構得到的拓撲圖如圖6所示。從圖中可以看出，整個拓撲樹被正確識別；但同時發現，如果存在關鍵匿名路由器，則其后的中間節點即使不是c)類匿名路由器，由于不知道其信息，仍認為它們是c)類匿名路由器，用符號*來標志。 4 結束語 本文提出一種基于traceroute的網絡拓撲識別層析成像方法，該方法結合了基于中間節點協作法和基于層析成像法的優點，解決了傳統測量方法無法解決的非協作節點問題。它充分利用了根據traceroute探測得到的目標網絡的部分拓撲信息，有效地避免了探測過程中信息冗余帶來的無謂的探測包的發送，大大減少了需要發送的探測包的個數，提高了網絡拓撲識別的準確性和可靠性，解決了網絡層析成像存在的探測包發送數量過多、求解不穩定、多解性強等問題。但是也發現，最小相似度聚類算法需要根據數據的特點或經驗來設定一個聚類門限，此門限影響了最小相似度聚類算法的結果，會給拓撲識別的準確度帶來影響。在今后的工作中將會繼續研究如何改進最小相似度聚類算法，以取得更為理想的聚類結果。 參考文獻： ［1］ SIAMWALLA R，SHARMA R，KESHAV S.Discovering Internet topology[C]//Proc of the 18th Conference on IEEE Computer Communications.1999. ［2］COATES M，ALFRED O，HERO R，et al.Internet tomography[J].IEEE Signal Processing Magazine，2002，19(3):4765. [3]RATNASAMY S，McCANNE S.Inference of multicast routing trees and bottleneck bandwidths using endtoend measurements[C]//Proc of the 18th Conference on IEEE Computer Communications.1999:353360. [4]DUFFIELD N G，HOROWITZ J，LO PRESTI F，et al.Multicast topology inference from endtoend measurements[M]//ITC Seminar on IP Traffic， Measurement and Modelling.2000:110. [5]COATES M，CASTRO R，NOWAK R.Maximum likelihood network topology identification from edgebased unicast measurements[R].Houston:Rice University，2002:2129. ［6］SHIN Mengfu，ALFRED O，HERO III.Hierarchical inference of unicast network topologies based on endtoend Measurements[J].IEEE Trans on Signal Processing，2007，55(5)：17081718. ［7］JIN Xing，YIU W P K，CHAN S H G，et al.Network topology inference based on endtoend measurements[J].IEEE Journal on Selected Area in Communications，2006，24(12):21822195. ［8］CASTRO R，COATES M，LIANG R，et al.Internet tomography:recent developments[J].Statistical Science，2004，19(3):499517.
