基于混合校驗的高完整度網(wǎng)絡(luò)拓撲發(fā)現(xiàn)方法*

寇曉蕤，董海量，焦永生

（61716部隊，福建 福州 350003）

0 引 言

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

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

網(wǎng)絡(luò)拓撲探測主要采用網(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é)議）?；贗CMP的方法[4]即采用Traceroute技術(shù)，通過依次發(fā)送IP數(shù)據(jù)報首部TTL（Time To Live，生存期）字段設(shè)置為1至最大跳的系列探測報文，并依次接收路由器的超時應(yīng)答以獲取路由器序列，即路由器的連接關(guān)系。在獲取IP級拓撲后，通過解析IP所在的AS，即可推導(dǎo)出AS之間的連接關(guān)系。基于BGP的方法[5]則是通過直接分析BGP路由表以獲取AS之間的連接關(guān)系。基于SNMP的方法主要用于發(fā)現(xiàn)路由器級網(wǎng)絡(luò)拓撲[6]。SNMP協(xié)議體系架構(gòu)中包含的關(guān)鍵要素是MIB（Management Information Base，管理信息庫），其中包含不同的管理組。這些管理組中則包含了設(shè)備接口表、路由表和生成樹協(xié)議等。網(wǎng)絡(luò)管理節(jié)點通過讀取被管設(shè)備MIB中的相關(guān)信息即可分析獲取三層拓撲和二層拓撲，其中三層拓撲體現(xiàn)了路由器和子網(wǎng)之間的連接關(guān)系，二層拓撲則體現(xiàn)了橋接設(shè)備相關(guān)的連接關(guān)系。

在所有的拓撲描述方式中，三層拓撲最常見，因為它比IP級拓撲更細致精確。在一個有限的可視化平面內(nèi)，子網(wǎng)能夠?qū)⑷舾稍O(shè)備節(jié)點聚集為拓撲圖上的一個子網(wǎng)節(jié)點，結(jié)合層進、回溯等可視化方法，清晰繪制拓撲圖。三層拓撲主要采用基于SNMP的方法，要求目標網(wǎng)絡(luò)中的所有設(shè)備開放UDP（User Datagram Protocol）161端口（SNMP代理端口），并且要求拓撲發(fā)現(xiàn)節(jié)點知道所有的SNMP代理口令。對于一個大型網(wǎng)絡(luò)，這個條件很難實現(xiàn)。因此，本文提出一種基于混合校驗機制的高完整度三層網(wǎng)絡(luò)拓撲發(fā)現(xiàn)方法，同時使用基于ICMP和SNMP的探測技術(shù)，在進行綜合分析后，利用校驗機制對探測分析結(jié)果進行精化，從而在SNMP代理信息不完整的情況下獲得較為完整準確的拓撲結(jié)構(gòu)。

1 基于ICMP的三層拓撲發(fā)現(xiàn)方法

1.1 技術(shù)機制

圖1為基于ICMP的網(wǎng)絡(luò)拓撲發(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è)置為目標網(wǎng)絡(luò)的整個IP地址段時，即可獲取整個網(wǎng)絡(luò)中路由器與路由器以及路由器與終端的連接關(guān)系。

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

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

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

上述基本方法無法獲取子網(wǎng)信息，下面對上述技術(shù)進行改進，以獲取子網(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é)點開始遍歷，找到其所在的子網(wǎng)節(jié)點；如果同一路由器的別名不在該子網(wǎng)內(nèi)，則將該子網(wǎng)節(jié)點作為其連接的子網(wǎng)；否則，按照DFS（Depth First Search，深度優(yōu)先搜索）方法繼續(xù)向下搜索，直到同一路由器的所有別名都不處于某個子網(wǎng)節(jié)點。假設(shè)一個路由器的別名分別為192.168.0.1和192.168.0.65，則針對第一個IP地址從根節(jié)點開始遍歷。由于第二個IP與其都處于“0-255”這個子網(wǎng)節(jié)點，所以繼續(xù)向下搜索，最后找到“0-63”、“64-127”這兩個子網(wǎng)節(jié)點。利用本算法得到的是一個路由器接口可能連接的最大規(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é)點集合;

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

{

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

{

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

{

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

RouterAlias[N] -= RouterAlias[j];

}

}

}

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

{

return;

}

}

return；

}

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

2 基于SNMP的三層拓撲發(fā)現(xiàn)方法

2.1 基于DFS和WFS的方法

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

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

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

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

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

基于以上考慮，為更完整地發(fā)現(xiàn)網(wǎng)絡(luò)拓撲信息，可采用以下策略：

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

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

（3）對于所有SNMP代理，讀取路由表通過綜合分析獲取子網(wǎng)層拓撲。

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

圖4 使用代理發(fā)現(xiàn)機制發(fā)現(xiàn)的更為完整的拓撲圖示例

3 基于混合校驗機制的綜合分析算法

3.1 基于ICMP的方法補全基于SNMP獲取的拓撲圖

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

圖5 基于終端提升拓撲發(fā)現(xiàn)完整性示例

3.2 綜合校驗分析算法

為最大限度地得到完整的拓撲圖，綜合使用基于ICMP和SNMP的方法對網(wǎng)絡(luò)拓撲進行探測分析，因此可能得到重復(fù)的結(jié)果。此外，由于基于ICMP的方式是對子網(wǎng)進行推導(dǎo)，因此存在并不完全準確的情況。因此，設(shè)計綜合校驗分析算法，以便獲取無冗余且更精確的分析結(jié)果。從計算機處理角度看，子網(wǎng)層拓撲可描述為三元組[路由器連接子網(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ò)拓撲進行探測分析的多個結(jié)果之間也可以相互進行校驗，校驗規(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)的方法能夠獲取更準確的結(jié)果。但是，考慮到實際網(wǎng)絡(luò)的復(fù)雜性，二者結(jié)合使用并綜合分析，可以互相彌補不足，最終獲取最完整準確的拓撲圖，這是一種盡最大努力的方法。

4 實驗結(jié)果

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

圖6 一個真實網(wǎng)絡(luò)拓撲探測結(jié)果

5 結(jié) 語

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