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

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

1 引言

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

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

本文首先給出一個(gè)高效的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法，然后詳細(xì)介紹了基于H3的拓?fù)淇梢暬幕驹恚詈蠡贛FC（microsoft foundation class，微軟基礎(chǔ)類）進(jìn)行了編程實(shí)現(xiàn)并以其對校園網(wǎng)進(jìn)行了測試與分析。

2 算法描述

2.1 拓?fù)浒l(fā)現(xiàn)算法

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

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

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

圖1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)示意

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

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

如果對圖1所示的拓?fù)浣Y(jié)構(gòu)進(jìn)行探測，則探測結(jié)果見表1。

表1 圖1的拓?fù)涮綔y結(jié)果

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

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

觀察該文件和圖1可知，該文件的輸入順序類似于圖的深度優(yōu)先遍歷序列。要實(shí)現(xiàn)拓?fù)涞目梢暬P(guān)鍵是如何從表1得到H3要求的輸入文件，最終將一條條獨(dú)立記錄的路徑信息歸并成一棵樹。并且在實(shí)現(xiàn)時(shí)必須考慮算法的高效性，因?yàn)楫?dāng)拓?fù)溆涗涍_(dá)到數(shù)千上萬條的時(shí)候，時(shí)間復(fù)雜度超過O(n2)的算法都將會(huì)變得非常緩慢。

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

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

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

2.3 拓?fù)淇梢暬?/h3>

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

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

（1）自底向上的估算

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

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

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

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

（2）自頂向下的布局

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

圖2 填充解決方案示意

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

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

圖3 孩子半球的布局點(diǎn)θ的變化

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

（3）測試與分析

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

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

3 結(jié)束語

圖4 拓?fù)浣Y(jié)構(gòu)初始狀態(tài)

圖5 旋轉(zhuǎn)后的拓?fù)浣Y(jié)構(gòu)

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

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

2 盧紅梅.一種網(wǎng)絡(luò)拓?fù)渌惴ǖ难芯亢头治?科技信息，2012(31):144～145

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

4 張耀方，孔德弟，石佳玉.改進(jìn)的網(wǎng)絡(luò)拓?fù)渫茢嗨惴?電子測試，2014(1):36～41

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

6 徐闊海.一種基于Rapha I圖形庫的網(wǎng)絡(luò)拓?fù)渖上到y(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