基于H3的拓?fù)淇梢暬芯考皩?shí)現(xiàn)

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

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

1 引言

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

通過(guò)拓?fù)浒l(fā)現(xiàn)可以得到網(wǎng)絡(luò)地址的連接關(guān)系，但是如何將得到的拓?fù)湫畔⒑芎玫仫@示給用戶,也是一個(gè)比較困難的問(wèn)題。拓?fù)淇梢暬褪峭ㄟ^(guò)已知的拓?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é)果是樹(shù)型結(jié)構(gòu)，如果以平面的形式來(lái)顯示[6]，由于樹(shù)的節(jié)點(diǎn)數(shù)量隨著樹(shù)的深度的增加呈現(xiàn)指數(shù)增長(zhǎng)，那么能夠顯示的節(jié)點(diǎn)數(shù)量就是有限的，并且層次越深，節(jié)點(diǎn)的符號(hào)就越小。但是由于雙曲空間中空間大小呈現(xiàn)指數(shù)增長(zhǎng)，正好與樹(shù)的節(jié)點(diǎn)增長(zhǎng)的趨勢(shì)一致，所以可以借助雙曲空間來(lái)進(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)并以其對(duì)校園網(wǎng)進(jìn)行了測(cè)試與分析。

2 算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）自底向上的估算

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

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

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

通過(guò)自底向上的估計(jì)，可以得到所需要的球的半徑，下面通過(guò)自頂向下的方式來(lái)布局各個(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）可以看出如果不對(duì)節(jié)點(diǎn)進(jìn)行排序，則會(huì)浪費(fèi)很多空間。

圖2 填充解決方案示意

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

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

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

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

（3）測(cè)試與分析

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

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

3 結(jié)束語(yǔ)

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

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

本文給出了一種快速且對(duì)網(wǎng)絡(luò)產(chǎn)生負(fù)載較小的拓?fù)浒l(fā)現(xiàn)算法，利用數(shù)據(jù)庫(kù)來(lái)存儲(chǔ)信息，方便程序?qū)ζ溥M(jìn)行快速的檢索。并基于H3的拓?fù)淇梢暬韺?duì)數(shù)據(jù)進(jìn)行預(yù)處理，最終實(shí)現(xiàn)了拓?fù)淇梢暬y(cè)試結(jié)果表明，該方法可以很好地對(duì)網(wǎng)絡(luò)拓?fù)溥M(jìn)行可視化，但是發(fā)現(xiàn)的拓?fù)洳皇呛芡暾?，需要通過(guò)多種手段識(shí)別匿名路由器，借助網(wǎng)絡(luò)斷層掃描技術(shù)推測(cè)拓?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和鄰接分組對(duì)的網(wǎng)絡(luò)拓?fù)渫茰y(cè)方法.蘭州交通大學(xué)學(xué)報(bào)，2013,32(1):88～91

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

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

6 徐闊海.一種基于Rapha I圖形庫(kù)的網(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