基于H3的拓撲可視化研究及實現

辛富國，李榮芳，王中振，權東曉

（1.陜西郵電職業技術學院 咸陽 712000；2.西安電子科技大學 西安 710071）

1 引言

隨著社會的不斷發展，網絡在人們日常生活和工作中的作用越來越重要。網絡的功能越來越強大，網絡的規模也在不斷擴大，流量也不斷上升。即使是網絡管理員也可能并不清楚網絡的拓撲結構，因此拓撲發現的作用變得越來越重要。拓撲發現包括合作探測和非合作探測[1]。合作探測時，管理員可以通過訪問路由表、MBI庫[2]等來輔助探測拓撲，這能夠幫助管理員了解網絡的連接關系，同時根據流量信息對網絡進行擴容；非合作探測主要用作攻擊，指的是在沒有訪問權限的情況下，通過向網絡發送數據分組，根據其返回的信息來推測網絡拓撲。傳統的算法是基于 ICMP（internet control messages protocol，互聯網控制報文協議）來進行拓撲發現[3]，由于一些路由器不響應，使得發現的拓撲不完整，較好的解決方案是結合流量、時延[4]、地址轉發表[5]等信息進行網絡斷層掃描[3～5]，推測拓撲信息。

通過拓撲發現可以得到網絡地址的連接關系，但是如何將得到的拓撲信息很好地顯示給用戶,也是一個比較困難的問題。拓撲可視化就是通過已知的拓撲數據將目標網絡的節點和連接狀況完整、清晰地呈現在人們眼前，為人們分析、了解目標網絡的狀況提供依據。單點拓撲發現的結果是樹型結構，如果以平面的形式來顯示[6]，由于樹的節點數量隨著樹的深度的增加呈現指數增長，那么能夠顯示的節點數量就是有限的，并且層次越深，節點的符號就越小。但是由于雙曲空間中空間大小呈現指數增長，正好與樹的節點增長的趨勢一致，所以可以借助雙曲空間來進行顯示[7]。基于H3的拓撲可視化[8]就是基于這樣的原理實現的。

本文首先給出一個高效的網絡拓撲發現算法，然后詳細介紹了基于H3的拓撲可視化的基本原理，最后基于MFC（microsoft foundation class，微軟基礎類）進行了編程實現并以其對校園網進行了測試與分析。

2 算法描述

2.1 拓撲發現算法

在這里采用常用的基于ICMP的拓撲發現算法，首先利用ping程序探測主機是否在線，如果在線則逐步改變TTL（time to live,生存時間）值進行路徑探測。為了提高效率，對算法做了以下改進。

一是采用多線程編程來進行探測。由于利用ping程序探測時，如果主機在線則會立即返回信息，否則必須默認等待超時后才能確定主機不在線，需要的時間比較長。若主機在線，需要逐步改變TTL值進行路徑探測。因此當探測的地址空間較大時，單線程執行需要的時間會很長，所以采用多線程編程來提高探測速度。

二是采用由遠及近的探測方式。在圖1所示的拓撲結構中，假設主機A探測到主機H在線后，依次設定TTL值為2和1，則分別會收到節點G和F返回的超時信息ICMP_timeout。A到H的路徑探測結束，然后探測節點J，首先設置TTL值為3，則會接收到節點I返回的信息，然后設置TTL值為2，接收到節點G返回的信息。由于在前面已經探測過A到G的路徑了，因此后面就沒有必要設置TTL值為1繼續探測，提高了探測速度。在真實網絡中，特別是探測距離較遠的外網時，能大大提高探測速度，減少發送分組的數量，對網絡造成的影響也較小。

圖1 網絡拓撲結構示意

2.2 數據預處理

拓撲探測得到的路徑信息，用數據庫進行存儲，包括目的節點以及經過的每一個路由器的IP地址。由于有的路由器對ICMP數據分組沒有響應，如果沒有收到回復，在數據庫中則將路由器的地址記為255.255.255.255，方便以后將IP地址轉換成整數進行壓縮存儲。

如果對圖1所示的拓撲結構進行探測，則探測結果見表1。

表1 圖1的拓撲探測結果

而H3可視化軟件的輸入文件中每一行代表一個節點，其內容格式為:depth identifier[…]。

depth是指當前節點在骨干樹中的深度，如果當前行A的前面數行中某行B的深度比行A的深度小1，則說明在樹中A是B的孩子節點，有一個連線從B到A。identifier用來描述節點，一般為IP地址等信息，[]中的信息為附加信息，用來描述節點是主機、路由器、顯示標志等。圖1所示的網絡拓撲結構，其對應的文件格式為:

觀察該文件和圖1可知，該文件的輸入順序類似于圖的深度優先遍歷序列。要實現拓撲的可視化，關鍵是如何從表1得到H3要求的輸入文件，最終將一條條獨立記錄的路徑信息歸并成一棵樹。并且在實現時必須考慮算法的高效性，因為當拓撲記錄達到數千上萬條的時候，時間復雜度超過O(n2)的算法都將會變得非常緩慢。

在處理時，可以對數據庫的內容先進行hop_1（第1跳）的排序，再對hop_2進行排序……在對hop_30進行排序后（假設最多為30跳），表1將會變成表2的結果。

表2 排序后的探測結果

從表2中的數據可以看出，相似度越高的記錄越鄰近，那么在遍歷數據庫生成H3需要的文件的時候，只需要比較當前記錄和上一條記錄的差異，就可以依據這些差異添加相應的節點，從而減少了不必要的比較。同時，該過程中對每一條記錄的每一跳的遍歷剛好是一個深度遍歷的序列，這樣就可以生成H3需要的文件。該算法的時間復雜度是O(n)，速度比較快。

2.3 拓撲可視化

得到文件以后，就要根據文件對拓撲結構進行可視化。由于基于單點探測的網絡拓撲是一個樹型結構，需要布局的節點數量隨著樹的深度的增加呈現指數增長。而在歐幾里得空間中可用的布局空間則呈現多項式增長，這樣為了顯示結果就要將離根節點較遠的節點占用的空間減小，從而導致能夠看到離根節點較近的拓撲連接關系，而較遠的節點無法看清。由于雙曲幾何空間中可用的布局空間隨著半徑的增長呈現指數形式的增長，所以H3借助雙曲幾何空間進行顯示。通過投射模型將雙曲空間投影到歐幾里得空間進行顯示，因為直線的顯示速度要快很多，在用戶拖動查看拓撲結構時速度較快。

在樹的布局上，H3可視化算法是由施樂帕克研究中心開發的圓錐樹[9]系統擴展來的。圓錐樹將葉子節點布局在從雙親節點發散出來的圓錐的圓周上，而H3算法則將葉子節點布局在一個覆蓋在圓錐之上的半球面上。這個算法要進行兩趟遍歷:自底向上執行一趟來估算每個半球容納所有的孩子半球所需要的半徑大小，自頂向下執行一趟來將每個孩子半球布局到雙親半球的表面。這兩步是不能合并的，因為在布局孩子半球的時候需要先確定雙親半球的半徑[8]。

（1）自底向上的估算

設雙親半球的半徑為rp，在p+1層有n個孩子半球，每個孩子半球的地面圓的面積為Dk，則p層的半球的表面積為p+1層的所有孩子半球的底面圓的面積和，即:

從而得到雙親半球的半徑為:

則對應到雙曲空間分別為:

通過自底向上的估計，可以得到所需要的球的半徑，下面通過自頂向下的方式來布局各個節點。

（2）自頂向下的布局

在布局的時候，所有的孩子半球都依據其子孫的數量進行排序，依據孩子半球的大小自內向外地在環狀帶上填充，子孫數量最多的填充到極點位置。圖2（a）為填充方式的側視圖，圖 2（b）為填充方式的俯視圖，從圖2（c）可以看出如果不對節點進行排序，則會浪費很多空間。

圖2 填充解決方案示意

設每個孩子半球的坐標為:(rp,,θ)，通過第一步，已經得到了半徑rp，下面求出 和θ。

由于圖3可以得到，兩個相鄰的孩子節點的θ的增量取決于兩個孩子半球的半徑，通過推導可以得到:

圖3 孩子半球的布局點θ的變化

在一個環狀帶內，順時針不斷增大θ值來布局孩子節點，當環狀帶j填充至θ=2π時，則移動至下一個離極點更遠的環狀帶j+1。由于對節點進行了排序，所以每個環狀帶內的第一個節點半徑最大，可以通過第一個孩子半球的半徑求得 的增量:

（3）測試與分析

基于提出的拓撲發現算法和可視化方法，在VC6.0環境下借助MFC編寫了拓撲發現軟件，數據庫采用MySQL，對校園網進行了測試，測試結果如圖4所示。

左側以列表的形式顯示發現的主機，通過點擊“+”號可以將到達目標節點的路由信息顯示到下方的編輯框里。通過多次測量，得到了254個主機，并繪制了拓撲結構，初始拓撲中，根節點的 和θ均為0，顯示在球表面的中心位置。通過拖拽可以實現旋轉效果，方便觀察感興趣的節點，如圖5所示。

3 結束語

圖4 拓撲結構初始狀態

圖5 旋轉后的拓撲結構

本文給出了一種快速且對網絡產生負載較小的拓撲發現算法，利用數據庫來存儲信息，方便程序對其進行快速的檢索。并基于H3的拓撲可視化原理對數據進行預處理，最終實現了拓撲可視化。測試結果表明，該方法可以很好地對網絡拓撲進行可視化，但是發現的拓撲不是很完整，需要通過多種手段識別匿名路由器，借助網絡斷層掃描技術推測拓撲結構，也可以進行分布式拓撲發現。

1 閆興篡，殷建平，蔡志平.網絡拓撲發現算法綜述.計算機工程與應用，2007,43(14):131～135

2 盧紅梅.一種網絡拓撲算法的研究和分析.科技信息，2012(31):144～145

3 劉香麗，吳辰文，茹俊年等.基于Tarceroute和鄰接分組對的網絡拓撲推測方法.蘭州交通大學學報，2013,32(1):88～91

4 張耀方，孔德弟，石佳玉.改進的網絡拓撲推斷算法.電子測試，2014(1):36～41

5 李丹程，馬東琳，韓春燕等.面向Trunk技術的網絡拓撲發現算法研究，2012,33(11):2435～2441

6 徐闊海.一種基于Rapha I圖形庫的網絡拓撲生成系統.軟件導刊,2014,13(1):149～151

7 Lamping J,Rao R.Laying out and visualizing large trees using a hyperbolic space.Proceedings of UIST’94,Marina del Rey,California,USA,1994:13～14

8 Munzner T.Interactive visualization of large graphs and networks.Doctoral Dissertation of Stanford University,2000

9 Robertson G,Mackin lay J,Card S.Cone trees:animated 3D visualizations of hierarchical information.Proceedings of the Conference on Human Factors in Computing Systems(CHI’91),New Orleans,Louisiana,USA,1991:189～194