辛富國，李榮芳，王中振，權(quán)東曉

（1.陜西郵電職業(yè)技術(shù)學(xué)院 咸陽 712000；2.西安電子科技大學(xué) 西安 710071）

1 引言

隨著社會的不斷發(fā)展，網(wǎng)絡(luò)在人們?nèi)粘Ｉ詈凸ぷ髦械淖饔迷絹碓街匾?。網(wǎng)絡(luò)的功能越來越強大，網(wǎng)絡(luò)的規(guī)模也在不斷擴大，流量也不斷上升。即使是網(wǎng)絡(luò)管理員也可能并不清楚網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，因此拓撲發(fā)現(xiàn)的作用變得越來越重要。拓撲發(fā)現(xiàn)包括合作探測和非合作探測[1]。合作探測時，管理員可以通過訪問路由表、MBI庫[2]等來輔助探測拓撲，這能夠幫助管理員了解網(wǎng)絡(luò)的連接關(guān)系，同時根據(jù)流量信息對網(wǎng)絡(luò)進行擴容；非合作探測主要用作攻擊，指的是在沒有訪問權(quán)限的情況下，通過向網(wǎng)絡(luò)發(fā)送數(shù)據(jù)分組，根據(jù)其返回的信息來推測網(wǎng)絡(luò)拓撲。傳統(tǒng)的算法是基于 ICMP（internet control messages protocol，互聯(lián)網(wǎng)控制報文協(xié)議）來進行拓撲發(fā)現(xiàn)[3]，由于一些路由器不響應(yīng)，使得發(fā)現(xiàn)的拓撲不完整，較好的解決方案是結(jié)合流量、時延[4]、地址轉(zhuǎn)發(fā)表[5]等信息進行網(wǎng)絡(luò)斷層掃描[3～5]，推測拓撲信息。

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

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

2 算法描述

2.1 拓撲發(fā)現(xiàn)算法

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

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

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

圖1 網(wǎng)絡(luò)拓撲結(jié)構(gòu)示意

2.2 數(shù)據(jù)預(yù)處理

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

如果對圖1所示的拓撲結(jié)構(gòu)進行探測，則探測結(jié)果見表1。

表1 圖1的拓撲探測結(jié)果

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

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

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

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

表2 排序后的探測結(jié)果

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

2.3 拓撲可視化

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

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

（1）自底向上的估算

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

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

則對應(yīng)到雙曲空間分別為:

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

（2）自頂向下的布局

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

圖2 填充解決方案示意

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

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

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

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

（3）測試與分析

基于提出的拓撲發(fā)現(xiàn)算法和可視化方法，在VC6.0環(huán)境下借助MFC編寫了拓撲發(fā)現(xiàn)軟件，數(shù)據(jù)庫采用MySQL，對校園網(wǎng)進行了測試，測試結(jié)果如圖4所示。

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

3 結(jié)束語

圖4 拓撲結(jié)構(gòu)初始狀態(tài)

圖5 旋轉(zhuǎn)后的拓撲結(jié)構(gòu)

本文給出了一種快速且對網(wǎng)絡(luò)產(chǎn)生負載較小的拓撲發(fā)現(xiàn)算法，利用數(shù)據(jù)庫來存儲信息，方便程序?qū)ζ溥M行快速的檢索。并基于H3的拓撲可視化原理對數(shù)據(jù)進行預(yù)處理，最終實現(xiàn)了拓撲可視化。測試結(jié)果表明，該方法可以很好地對網(wǎng)絡(luò)拓撲進行可視化，但是發(fā)現(xiàn)的拓撲不是很完整，需要通過多種手段識別匿名路由器，借助網(wǎng)絡(luò)斷層掃描技術(shù)推測拓撲結(jié)構(gòu)，也可以進行分布式拓撲發(fā)現(xiàn)。

1 閆興篡，殷建平，蔡志平.網(wǎng)絡(luò)拓撲發(fā)現(xiàn)算法綜述.計算機工程與應(yīng)用，2007,43(14):131～135

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

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

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

5 李丹程，馬東琳，韓春燕等.面向Trunk技術(shù)的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)算法研究，2012,33(11):2435～2441

6 徐闊海.一種基于Rapha I圖形庫的網(wǎng)絡(luò)拓撲生成系統(tǒng).軟件導(dǎo)刊,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