寇曉蕤，董海量，焦永生

（61716部隊，福建 福州 350003）

0 引 言

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)[1]是網(wǎng)絡(luò)的基本屬性，是網(wǎng)絡(luò)管理、各類網(wǎng)絡(luò)應(yīng)用可視化和研究網(wǎng)絡(luò)特性的基礎(chǔ)。因此，網(wǎng)絡(luò)拓?fù)鋱D的自動繪制即網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)技術(shù)研究一直是熱門領(lǐng)域。

通常，根據(jù)粒度不同，網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)可以分為四種層次[2]：接口級、路由器級、PoP級和AS級。接口級拓?fù)浒l(fā)現(xiàn)主要是研究網(wǎng)絡(luò)接口之間的連接關(guān)系，每一個節(jié)點(diǎn)表示具有獨(dú)立IP的接口，接口與IP地址一一對應(yīng)。一臺路由器通常有多個接口，也就用多個節(jié)點(diǎn)表示。節(jié)點(diǎn)之間的連接表示兩個接口在IP層直接連接。路由器級拓?fù)浒l(fā)現(xiàn)主要研究獲取子網(wǎng)級、設(shè)備級的拓?fù)浣Y(jié)構(gòu)[3]，即路由器與子網(wǎng)、網(wǎng)絡(luò)設(shè)備之間的連接關(guān)系。PoP（Point of Presence）表示同一個自治域中的路由器集合。不同的PoP通過AS的骨干網(wǎng)連接。在PoP級拓?fù)渲?，每個節(jié)點(diǎn)表示一個PoP，連接關(guān)系表示兩個PoP之間存在物理連接。AS級網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)主要研究獲取AS（Autonomous System，自治系統(tǒng)）級拓?fù)洌碅S之間的連接關(guān)系，反映的拓?fù)湎鄬暧^。

網(wǎng)絡(luò)拓?fù)涮綔y主要采用網(wǎng)絡(luò)協(xié)議實現(xiàn)數(shù)據(jù)采集，常用的網(wǎng)絡(luò)協(xié)議包括ICMP（Internet Control Message Protocol，因特網(wǎng)控制報文協(xié)議）、BGP（Border Gateway Protocol，邊界網(wǎng)關(guān)協(xié)議）和SNMP（Simple Network Management Protocol，簡單網(wǎng)絡(luò)管理協(xié)議）。基于ICMP的方法[4]即采用Traceroute技術(shù)，通過依次發(fā)送IP數(shù)據(jù)報首部TTL（Time To Live，生存期）字段設(shè)置為1至最大跳的系列探測報文，并依次接收路由器的超時應(yīng)答以獲取路由器序列，即路由器的連接關(guān)系。在獲取IP級拓?fù)浜螅ㄟ^解析IP所在的AS，即可推導(dǎo)出AS之間的連接關(guān)系?；贐GP的方法[5]則是通過直接分析BGP路由表以獲取AS之間的連接關(guān)系?；赟NMP的方法主要用于發(fā)現(xiàn)路由器級網(wǎng)絡(luò)拓?fù)鋄6]。SNMP協(xié)議體系架構(gòu)中包含的關(guān)鍵要素是MIB（Management Information Base，管理信息庫），其中包含不同的管理組。這些管理組中則包含了設(shè)備接口表、路由表和生成樹協(xié)議等。網(wǎng)絡(luò)管理節(jié)點(diǎn)通過讀取被管設(shè)備MIB中的相關(guān)信息即可分析獲取三層拓?fù)浜投油負(fù)?，其中三層拓?fù)潴w現(xiàn)了路由器和子網(wǎng)之間的連接關(guān)系，二層拓?fù)鋭t體現(xiàn)了橋接設(shè)備相關(guān)的連接關(guān)系。

在所有的拓?fù)涿枋龇绞街?，三層拓?fù)渥畛Ｒ?，因為它比IP級拓?fù)涓?xì)致精確。在一個有限的可視化平面內(nèi)，子網(wǎng)能夠?qū)⑷舾稍O(shè)備節(jié)點(diǎn)聚集為拓?fù)鋱D上的一個子網(wǎng)節(jié)點(diǎn)，結(jié)合層進(jìn)、回溯等可視化方法，清晰繪制拓?fù)鋱D。三層拓?fù)渲饕捎没赟NMP的方法，要求目標(biāo)網(wǎng)絡(luò)中的所有設(shè)備開放UDP（User Datagram Protocol）161端口（SNMP代理端口），并且要求拓?fù)浒l(fā)現(xiàn)節(jié)點(diǎn)知道所有的SNMP代理口令。對于一個大型網(wǎng)絡(luò)，這個條件很難實現(xiàn)。因此，本文提出一種基于混合校驗機(jī)制的高完整度三層網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法，同時使用基于ICMP和SNMP的探測技術(shù)，在進(jìn)行綜合分析后，利用校驗機(jī)制對探測分析結(jié)果進(jìn)行精化，從而在SNMP代理信息不完整的情況下獲得較為完整準(zhǔn)確的拓?fù)浣Y(jié)構(gòu)。

1 基于ICMP的三層拓?fù)浒l(fā)現(xiàn)方法

1.1 技術(shù)機(jī)制

圖1為基于ICMP的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)技術(shù)原理。當(dāng)探測端將探測報文的目的IP地址設(shè)置為D1的地址，將探測報文的IP數(shù)據(jù)報首部TTL值依次設(shè)置為1、2、3時，會依次收到R1、R2、R3的TTL超時回應(yīng)。S解析應(yīng)答報文即可獲取R1的A11接口、R2的A21接口和R3的A31接口。同樣，當(dāng)探測端將探測報文的目的IP地址設(shè)置為D2的地址時，可以得到R1的A11接口、R2的A21接口和R4的A41接口。當(dāng)探測報文的目的IP地址設(shè)置為目標(biāo)網(wǎng)絡(luò)的整個IP地址段時，即可獲取整個網(wǎng)絡(luò)中路由器與路由器以及路由器與終端的連接關(guān)系。

圖1 基于ICMP的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)技術(shù)原理

在一個復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)中，可能在探測過程中獲取同一路由器的不同接口。圖1中，R3的A32接口與R4的A42接口相連，則在拓?fù)涮綔y過程中有可能獲取A32或A42接口地址。為了避免將同一路由器的不同接口識別為不同路由器，基于ICMP的拓?fù)浒l(fā)現(xiàn)技術(shù)通常會采用“別名（Alias）”探測機(jī)制，即當(dāng)向路由器的遠(yuǎn)端接口發(fā)送探測報文，收到應(yīng)答報文的源地址為近端接口地址時，即可判斷這兩個地址屬于同一個路由器。圖1中，向A42發(fā)送探測報文，收到的應(yīng)答報文為A41的IP地址，則認(rèn)為這二者屬于同一路由器。

1.2 子網(wǎng)推導(dǎo)算法

上述基本方法無法獲取子網(wǎng)信息，下面對上述技術(shù)進(jìn)行改進(jìn)，以獲取子網(wǎng)。

圖2是一個C類網(wǎng)可能的子網(wǎng)劃分樹，每個子網(wǎng)包含的IP地址個數(shù)都是2的冪次。同時，路由器與子網(wǎng)連接配置遵守以下基本規(guī)則：

（1）兩個路由器直連的兩個接口IP地址屬于同一子網(wǎng)；

（2）同一路由器的不同接口不在同一子網(wǎng)。

根據(jù)上述原則，設(shè)計子網(wǎng)推導(dǎo)的算法思想為：對于所發(fā)現(xiàn)的所有路由器別名地址，用WFS（Width First Search，廣度優(yōu)先搜索）算法從子網(wǎng)劃分樹的根節(jié)點(diǎn)開始遍歷，找到其所在的子網(wǎng)節(jié)點(diǎn)；如果同一路由器的別名不在該子網(wǎng)內(nèi)，則將該子網(wǎng)節(jié)點(diǎn)作為其連接的子網(wǎng)；否則，按照DFS（Depth First Search，深度優(yōu)先搜索）方法繼續(xù)向下搜索，直到同一路由器的所有別名都不處于某個子網(wǎng)節(jié)點(diǎn)。假設(shè)一個路由器的別名分別為192.168.0.1和192.168.0.65，則針對第一個IP地址從根節(jié)點(diǎn)開始遍歷。由于第二個IP與其都處于“0-255”這個子網(wǎng)節(jié)點(diǎn)，所以繼續(xù)向下搜索，最后找到“0-63”、“64-127”這兩個子網(wǎng)節(jié)點(diǎn)。利用本算法得到的是一個路由器接口可能連接的最大規(guī)模子網(wǎng)。

圖2 一個C類網(wǎng)可能的子網(wǎng)劃分樹

本算法偽代碼如下：

void FindSubnet(Tree CClassNet，RouterAlias[N])

{

SubNet[N]=NULL;

int I,j,n=0;

int level;

for(level=0;level＜=CClassNet的 最 大 層 級；level++)

{

CClassNetSubnode[level]=CClassNet第 level層的所有子網(wǎng)節(jié)點(diǎn)集合;

for(i=0;i＜= CClassNetSubnode[level]的子網(wǎng)節(jié)點(diǎn)個數(shù)-1;i++)

{

for(j=0；j＜=N-1；j++)

{

if(RouterAlias[j]與其他任何一個別名不屬于同一個CClassNetSubnode[level]的子網(wǎng)節(jié)點(diǎn))

{

SubNet[n++]=CClassNetSubnode[level]的 第 i個子網(wǎng)節(jié)點(diǎn);

RouterAlias[N] -= RouterAlias[j];

}

}

}

if(n＞=N)//如果所有別名均找到對應(yīng)的子網(wǎng)節(jié)點(diǎn)

{

return;

}

}

return；

}

在上述偽代碼中，RouterAlias[N]用于存儲路由器別名，SubNet[N]用于存儲找到的子網(wǎng)節(jié)點(diǎn)，level用于記錄C類網(wǎng)層級，其中根節(jié)點(diǎn)視為0層。

2 基于SNMP的三層拓?fù)浒l(fā)現(xiàn)方法

2.1 基于DFS和WFS的方法

基于SNMP的三層拓?fù)浒l(fā)現(xiàn)通常采用DFS或WFS，即從根節(jié)點(diǎn)出發(fā)獲取其路由表，然后從中按照相應(yīng)策略選取下一個讀取節(jié)點(diǎn)，直到獲得所有節(jié)點(diǎn)。使用這種方法的優(yōu)勢在于探測效率高，獲得的冗余信息少；缺點(diǎn)在于當(dāng)網(wǎng)絡(luò)中存在不開放SNMP的節(jié)點(diǎn)時，會造成拓?fù)鋱D發(fā)現(xiàn)不完整。

圖3左側(cè)圖給出了一個示例，其中直線表示子網(wǎng)（下同）。如果R3不支持SNMP，則無論使用DFS還是WFS，都只能獲得圖3右側(cè)圖所示的不完整拓?fù)洹?/p>

圖3 一個基于DFS或WFS方法的不完整拓?fù)浒l(fā)現(xiàn)示例

2.2 基于代理發(fā)現(xiàn)的方法

為避免搜索方法不足，使用基于代理發(fā)現(xiàn)的方法，這是一種遍歷機(jī)制。定義支持SNMP訪問的節(jié)點(diǎn)為SNMP代理。對于常用的SNMPv1（第一版）而言，安全認(rèn)證機(jī)制為“共同體名”，相當(dāng)于一個口令。大部分設(shè)備對讀操作使用的共同體名默認(rèn)設(shè)置為“public”。出于安全性考慮，網(wǎng)絡(luò)管理員會更改默認(rèn)口令。

基于以上考慮，為更完整地發(fā)現(xiàn)網(wǎng)絡(luò)拓?fù)湫畔?，可采用以下策略?/p>

（1）將已知共同體名的設(shè)備作為SNMP代理寫入列表；

（2）對于整個目標(biāo)網(wǎng)段的設(shè)備，發(fā)送共同體名為“public”的SNMP讀報文，若收到應(yīng)答，則將相應(yīng)設(shè)備寫入代理列表，由此最大限度地尋找SNMP代理；

（3）對于所有SNMP代理，讀取路由表通過綜合分析獲取子網(wǎng)層拓?fù)洹?/p>

本方法效率低于基于DFS或WFS的方法，但完整度更高。圖4示意了針對圖3使用代理發(fā)現(xiàn)機(jī)制獲取的拓?fù)洌然贒FS或WFS的更完整。此外，實驗中發(fā)現(xiàn)，除路由器等交換橋接設(shè)備外，很多終端設(shè)備可作為代理，由此可以進(jìn)一步提升拓?fù)浒l(fā)現(xiàn)完整性。在圖5給出的示例中，R5和R8不是SNMP代理，但終端設(shè)備H是代理。如果不使用H，則R8分支將被隱去。

圖4 使用代理發(fā)現(xiàn)機(jī)制發(fā)現(xiàn)的更為完整的拓?fù)鋱D示例

3 基于混合校驗機(jī)制的綜合分析算法

3.1 基于ICMP的方法補(bǔ)全基于SNMP獲取的拓?fù)鋱D

利用SNMP獲取的拓?fù)鋱D，結(jié)果準(zhǔn)確，但可能存在別名不統(tǒng)一和拓?fù)鋱D不連通的情況。對于圖4的示例，R31、R32、R33同屬于R3；對于圖5的示例，R51與R82不連通。為解決上述問題，使用基于ICMP的別名探測分析方法將R3的三個接口地址統(tǒng)一到同一路由器；使用基于Traceroute的路由器連接關(guān)系探測分析機(jī)制，可將R51與R82進(jìn)行連接并進(jìn)行子網(wǎng)推導(dǎo)。

圖5 基于終端提升拓?fù)浒l(fā)現(xiàn)完整性示例

3.2 綜合校驗分析算法

為最大限度地得到完整的拓?fù)鋱D，綜合使用基于ICMP和SNMP的方法對網(wǎng)絡(luò)拓?fù)溥M(jìn)行探測分析，因此可能得到重復(fù)的結(jié)果。此外，由于基于ICMP的方式是對子網(wǎng)進(jìn)行推導(dǎo)，因此存在并不完全準(zhǔn)確的情況。因此，設(shè)計綜合校驗分析算法，以便獲取無冗余且更精確的分析結(jié)果。從計算機(jī)處理角度看，子網(wǎng)層拓?fù)淇擅枋鰹槿M[路由器連接子網(wǎng)的接口IP（別名），子網(wǎng)號，子網(wǎng)掩碼]序列?；谶@個三元組，具體的分析校驗規(guī)則如下。

（1）冗余去除規(guī)則：如果兩種方法同時發(fā)現(xiàn)了同一個三元組，則直接刪除其中的一個；

（2）噪聲去除規(guī)則：如果一個路由器別名相同，但利用兩種方法獲取的子網(wǎng)不同，則直接將基于ICMP發(fā)現(xiàn)的結(jié)果去掉；

（3）規(guī)模精化規(guī)則：如果一個別名相同，但利用ICMP方法獲取的子網(wǎng)范圍大于用SNMP發(fā)現(xiàn)的結(jié)果，則直接將利用ICMP獲取的結(jié)果去掉；

（4）越界修訂規(guī)則：別名不同，但如果用ICMP方法獲取的子網(wǎng)與用SNMP方法獲取的子網(wǎng)有重疊（前者子網(wǎng)覆蓋后者，或有重合），則用后者修訂前者，縮小前者的子網(wǎng)規(guī)模。

此外，基于ICMP的方法對網(wǎng)絡(luò)拓?fù)溥M(jìn)行探測分析的多個結(jié)果之間也可以相互進(jìn)行校驗，校驗規(guī)則與上述第3、4條規(guī)則類似，即：

（1）規(guī)模精化規(guī)則：如果兩種ICMP方法獲取的別名相同但子網(wǎng)范圍不同，則直接去掉子網(wǎng)范圍較大的結(jié)果；

（2）越界修訂規(guī)則：如果兩種ICMP方法獲取的別名不同但子網(wǎng)有重疊（前者子網(wǎng)覆蓋后者，或有重合），則用后者修訂前者，縮小前者的子網(wǎng)規(guī)模。

以上規(guī)則的核心是基于SNMP的方法比基于ICMP推導(dǎo)的方法能夠獲取更準(zhǔn)確的結(jié)果。但是，考慮到實際網(wǎng)絡(luò)的復(fù)雜性，二者結(jié)合使用并綜合分析，可以互相彌補(bǔ)不足，最終獲取最完整準(zhǔn)確的拓?fù)鋱D，這是一種盡最大努力的方法。

4 實驗結(jié)果

為驗證上述技術(shù)與算法的效果，在不預(yù)先設(shè)置任何共同體名的極端情況下對一個真實網(wǎng)絡(luò)的拓?fù)溥M(jìn)行探測分析，最終獲取的結(jié)果如圖6所示?？梢?，該方法能夠有效發(fā)現(xiàn)三層網(wǎng)絡(luò)拓?fù)洹?/p>

圖6 一個真實網(wǎng)絡(luò)拓?fù)涮綔y結(jié)果

5 結(jié) 語

本文給出了一種較有效的三層拓?fù)浒l(fā)現(xiàn)方法。對于一個大型網(wǎng)絡(luò)而言，很難全面了解新加設(shè)備情況，也可能出現(xiàn)節(jié)點(diǎn)失效情況。為應(yīng)對上述情況，本文給出了較為完美的解決方案。此外，設(shè)備使用默認(rèn)共同體名是一種安全風(fēng)險，本文也提供了一種檢測該安全風(fēng)險的方法。