聶 明

（南京信息職業(yè)技術(shù)學(xué)院，南京 210046）

0 引言

隨著網(wǎng)絡(luò)規(guī)模的日益擴(kuò)大，復(fù)雜度的不斷增加，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)也隨之變得日益復(fù)雜。一個(gè)好的網(wǎng)絡(luò)管理系統(tǒng)應(yīng)該反映網(wǎng)絡(luò)中所有設(shè)備的布局結(jié)構(gòu)，方便用戶全方位地管理網(wǎng)絡(luò)，對(duì)網(wǎng)絡(luò)異常流量、設(shè)備告警、網(wǎng)絡(luò)攻擊現(xiàn)象等進(jìn)行快速診斷和定位，以減少網(wǎng)絡(luò)異常造成的損失[1]。網(wǎng)絡(luò)拓?fù)涞淖詣?dòng)發(fā)現(xiàn)，其目的是獲得被管理網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，主要指互連設(shè)備，如路由器、交換機(jī)、PC設(shè)備等的信息以及它們之間的連接關(guān)系。網(wǎng)絡(luò)拓?fù)涞淖詣?dòng)發(fā)現(xiàn)是網(wǎng)絡(luò)管理系統(tǒng)的重要組成部分，是發(fā)現(xiàn)系統(tǒng)故障和監(jiān)控設(shè)備性能的基礎(chǔ)，更是衡量一個(gè)網(wǎng)絡(luò)管理系統(tǒng)成敗的重要標(biāo)準(zhǔn)之一[2]。

1 網(wǎng)絡(luò)拓?fù)涞淖詣?dòng)發(fā)現(xiàn)

網(wǎng)絡(luò)拓?fù)涞淖詣?dòng)發(fā)現(xiàn)通過(guò)收集網(wǎng)絡(luò)拓?fù)涞母鞣N必要信息，確定網(wǎng)絡(luò)元素之間的互連關(guān)系，并在此基礎(chǔ)上構(gòu)造網(wǎng)絡(luò)拓?fù)鋱D，為網(wǎng)絡(luò)管理人員提供一個(gè)直觀了解全局網(wǎng)絡(luò)狀態(tài)的友好界面。網(wǎng)絡(luò)拓?fù)涞淖詣?dòng)發(fā)現(xiàn)是對(duì)大規(guī)模網(wǎng)絡(luò)進(jìn)行有效管理的必不可少的手段，當(dāng)前常用的網(wǎng)絡(luò)拓?fù)渥詣?dòng)發(fā)現(xiàn)方法主要包括基于ARP協(xié)議的拓?fù)浒l(fā)現(xiàn)方法、基于ICMP協(xié)議的拓?fù)浒l(fā)現(xiàn)方法和基于SNMP協(xié)議的拓?fù)浒l(fā)現(xiàn)方法等[3~6]。

1）基于ARP協(xié)議的拓?fù)浒l(fā)現(xiàn)方法。每個(gè)支持地址協(xié)議的網(wǎng)絡(luò)設(shè)備中都維護(hù)著一張ARP表，該表記錄了該設(shè)備連接的網(wǎng)絡(luò)設(shè)備的IP地址和MAC地址的對(duì)應(yīng)關(guān)系。利用ARP表，可以從一臺(tái)已知路由器或交換機(jī)的ARP表發(fā)現(xiàn)其連接的其它網(wǎng)絡(luò)設(shè)備，從這些新發(fā)現(xiàn)設(shè)備中區(qū)分出路由器和交換機(jī)，并繼續(xù)根據(jù)這些路由器和交換機(jī)的ARP表進(jìn)行設(shè)備發(fā)現(xiàn)，從而得到整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。因?yàn)锳RP表中的網(wǎng)絡(luò)設(shè)備地址都是最近活動(dòng)過(guò)的有效設(shè)備的IP地址，幾乎沒(méi)有冗余信息，所以該拓?fù)浒l(fā)現(xiàn)方法效率很高。但如果網(wǎng)絡(luò)過(guò)大，ARP表中可能無(wú)法包括網(wǎng)絡(luò)中實(shí)際存在的所有網(wǎng)絡(luò)設(shè)備，同時(shí)待發(fā)現(xiàn)的網(wǎng)絡(luò)設(shè)備需要支持ARP協(xié)議，所以該方法適合于局域網(wǎng)的拓?fù)浒l(fā)現(xiàn)。

2）基于ICMP協(xié)議的拓?fù)浒l(fā)現(xiàn)方法。它通過(guò)向網(wǎng)絡(luò)設(shè)備發(fā)送ICMP報(bào)文，測(cè)試設(shè)備的可達(dá)性。該方法對(duì)一個(gè)網(wǎng)段內(nèi)所有設(shè)備的網(wǎng)絡(luò)IP地址依次執(zhí)行ping操作，根據(jù)響應(yīng)就可以發(fā)現(xiàn)當(dāng)前該網(wǎng)段內(nèi)所有活動(dòng)的網(wǎng)絡(luò)設(shè)備。根據(jù)給定的IP區(qū)間逐一進(jìn)行ping操作，根據(jù)結(jié)果，再對(duì)上一次操作記錄的活動(dòng)的IP地址逐一進(jìn)行路由跟蹤，記錄下每一次路由跟蹤的操作結(jié)果，根據(jù)前面的操作結(jié)果，再分析所得到的信息，從中得到整個(gè)拓?fù)涞倪B接情況。該拓?fù)浒l(fā)現(xiàn)方法簡(jiǎn)單、可靠、快速，但發(fā)現(xiàn)具有一定的盲目性，并在一定程度上加重了網(wǎng)絡(luò)的負(fù)荷等，此方法適用于子網(wǎng)內(nèi)網(wǎng)絡(luò)設(shè)備的發(fā)現(xiàn)。

3）基于SNMP的拓?fù)浒l(fā)現(xiàn)方法。每個(gè)網(wǎng)絡(luò)設(shè)備都有路由表，路由信息中包含了完整的網(wǎng)絡(luò)拓?fù)湫畔?，包括路由目的網(wǎng)絡(luò)地址、目的網(wǎng)絡(luò)的子網(wǎng)掩碼、該路由的下一站IP地址、對(duì)應(yīng)的端口索引和路由協(xié)議類型等。由于路由表中的下一站地址項(xiàng)所標(biāo)識(shí)的必然是具有路由功能的網(wǎng)絡(luò)結(jié)點(diǎn)，因此從設(shè)定路由器開始，讀取路由器的路由表，可以逐漸向下發(fā)現(xiàn)網(wǎng)絡(luò)中所有基于路由功能的網(wǎng)絡(luò)結(jié)點(diǎn)。再根據(jù)路由表的本地接口的索引標(biāo)識(shí)項(xiàng)，找到接口表中對(duì)應(yīng)的接口索引，由接口表的接口類型就可以了解到所在子網(wǎng)的類型，從而構(gòu)建出整個(gè)網(wǎng)絡(luò)的拓?fù)潢P(guān)系圖。這種方法的拓?fù)浒l(fā)現(xiàn)過(guò)程和算法簡(jiǎn)單，目標(biāo)明確，發(fā)現(xiàn)效率高，系統(tǒng)和網(wǎng)絡(luò)開銷小，因此得到人們的廣泛應(yīng)用。但是，該方法也存在不足之處，主要表現(xiàn)在：

（1）無(wú)法發(fā)現(xiàn)網(wǎng)絡(luò)中沒(méi)有配置IP的網(wǎng)絡(luò)設(shè)備；

（2）一個(gè)路由器往往配置了多個(gè)IP地址，并且基于路由表的發(fā)現(xiàn)方法算法是基于IP地址的，所以對(duì)于路由器多IP現(xiàn)象，可能導(dǎo)致路由器的發(fā)現(xiàn)與實(shí)際情況不合；

（3）要依次檢測(cè)各網(wǎng)絡(luò)設(shè)備的狀態(tài)，導(dǎo)致算法運(yùn)行時(shí)間可能過(guò)長(zhǎng)，同時(shí)設(shè)備的發(fā)現(xiàn)受網(wǎng)絡(luò)時(shí)延等影響，不能完全實(shí)時(shí)反映網(wǎng)絡(luò)狀況；

（4）路由表中包含了大量冗余信息；

（5）網(wǎng)絡(luò)設(shè)備必須支持SNMP協(xié)議。

因此，該方法主要用于大型主干網(wǎng)絡(luò)的拓?fù)浒l(fā)現(xiàn)，主要發(fā)現(xiàn)網(wǎng)絡(luò)中的路由設(shè)備，反映網(wǎng)絡(luò)的整體拓?fù)浣Y(jié)構(gòu)狀況。

可見(jiàn)，當(dāng)前各種拓?fù)浞椒ǜ饔袃?yōu)缺點(diǎn)和局限性，在實(shí)際應(yīng)用中需要根據(jù)具體的情況，有選擇或綜合地應(yīng)用。本文給出了一種基于SNMP的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法，經(jīng)過(guò)實(shí)際網(wǎng)絡(luò)管理系統(tǒng)的驗(yàn)證，能夠有效發(fā)現(xiàn)整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。

2 基于SNMP的網(wǎng)絡(luò)拓?fù)渥詣?dòng)發(fā)現(xiàn)算法

2.1 算法思想

在網(wǎng)絡(luò)中路由器之間的鏈路是由其兩端路由器的端口互聯(lián)構(gòu)成的，根據(jù)TCP/IP的編址原理，鏈路兩端路由器端口的IP地址必然處于同一個(gè)子網(wǎng)中。因此，通過(guò)一個(gè)子網(wǎng)中已知的IP地址和這個(gè)IP地址的子網(wǎng)掩碼即可計(jì)算出該子網(wǎng)中所有其他的IP地址。

根據(jù)以上思路，從某個(gè)節(jié)點(diǎn)開始，訪問(wèn)其MIB庫(kù)，得到該節(jié)點(diǎn)所有接口的IP地址和子網(wǎng)掩碼，該節(jié)點(diǎn)稱為種子節(jié)點(diǎn)。通過(guò)計(jì)算得到與每一接口在同一個(gè)子網(wǎng)內(nèi)的其他IP地址。判斷這些IP地址是否屬于路由器信息，如果是則將此路由器信息記錄到待檢測(cè)路由設(shè)備鏈表，作為下一層發(fā)現(xiàn)的種子節(jié)點(diǎn)。并同時(shí)記錄兩個(gè)路由器間的鏈路信息到拓?fù)湫畔㈡湵?。重?fù)以上步驟直到?jīng)]有種子節(jié)點(diǎn)或者達(dá)到指定的發(fā)現(xiàn)層數(shù)，即可完成相應(yīng)的拓?fù)浒l(fā)現(xiàn)過(guò)程。

2.2 算法描述

算法可具體描述如下：

1）根據(jù)網(wǎng)絡(luò)管理系統(tǒng)的IP和掩碼，使用路由跟蹤的方法獲取網(wǎng)管終端所在的默認(rèn)路由器網(wǎng)關(guān)地址。訪問(wèn)該路由器獲取ipAdderssTable地址表信息，將其編號(hào)加入AllRouters隊(duì)列（元素包括路由器名、接口號(hào)、接口IP、接口號(hào)和接口IP等），其中接口號(hào)與接口IP的多少依據(jù)各個(gè)不同路由器而不同）和AccessRouters隊(duì)列（待訪問(wèn)路由器，結(jié)構(gòu)跟AllRouters類似）；

2）從AccessRoutes取出一個(gè)元素設(shè)為當(dāng)前處理的路由器Rx，依次訪問(wèn)Rx的路由表ipRouteTable表項(xiàng)，將目標(biāo)子網(wǎng)信息編號(hào)無(wú)重復(fù)地放入子網(wǎng)隊(duì)列Subnets（元素包括子網(wǎng)號(hào)，子網(wǎng)地址，掩碼等）；

3）判斷路由器與子網(wǎng)連接關(guān)系：依次對(duì)Rx的ipRouteTable表項(xiàng)檢查，如果ipRouteType項(xiàng)不為4，表示相應(yīng)子網(wǎng)與Rx直接相連，下一跳地址ipNextHopIpAddress項(xiàng)為空。根據(jù)Rx的ipAddressTable信息確定y端口與該子網(wǎng)z相連接，將連接關(guān)系組（Rx，y，Subnets）無(wú)重復(fù)地放入R-links-S隊(duì)列（路由器接口與子網(wǎng)相連的接配對(duì)的二元組）；

4）判斷路由器之間的連接關(guān)系：如果ipRouteType為4，下一跳ipNextHopIpAddress地址有效，表明另一個(gè)路由器與Rx直接相連。根據(jù)ipNextHopIpAddress地址信息訪問(wèn)另一個(gè)路由器的ipAddressTable，判斷AllRouters隊(duì)列中是否己經(jīng)存在該路由器信息，如不存在則把該路由器編號(hào)加入隊(duì)列AllRouters和AccessRouters中。很容易確定Rx的y端口與另一個(gè)路由器Ru的v端口直接連接。因此把元素（Rx，y，Ru，v）無(wú)重復(fù)地放入隊(duì)列R-links-R（路由器接口與路由器接口相連的二元組）中。

5）把隊(duì)列R-links-R進(jìn)行去冗處理。因?yàn)樵谝陨系乃惴▽?shí)現(xiàn)中，有可能存相同的連接信息加入到隊(duì)列中。例如:R1的2端口與R4的3端口直接相連，在算法實(shí)現(xiàn)過(guò)程中，可能同時(shí)在隊(duì)列中加入了（R1，2，R4，3）和（R4，3，R1，2）的元素組，雖然它們?cè)谛问缴喜灰粯?，但他們表示同一個(gè)連接信息。

6）把Rx的元素組從AccessRouters中刪除，如果AccessRouters不為空，轉(zhuǎn)到（2），如果為空，程序中止。

算法運(yùn)行結(jié)束以后，AllRouters包含了所有活動(dòng)的路由器，子網(wǎng)隊(duì)列Subnets包含了所有活動(dòng)的子網(wǎng)，隊(duì)列R-links-S和隊(duì)列R-links-R的信息表示路由器與子網(wǎng)、路由器與路山器之間連接關(guān)系，最終可以準(zhǔn)確而完整地把拓?fù)浣Y(jié)構(gòu)繪制出來(lái)。

2.3 拓?fù)浒l(fā)現(xiàn)中幾個(gè)問(wèn)題

1）路由器多IP地址問(wèn)題

路由器的每個(gè)接口對(duì)應(yīng)著一個(gè)IP地址，一個(gè)接口下可以配置多個(gè)端口。根據(jù)以上拓?fù)浒l(fā)現(xiàn)方法，就會(huì)出現(xiàn)重復(fù)訪問(wèn)同一路由器的現(xiàn)象，嚴(yán)重影響拓?fù)浒l(fā)現(xiàn)算法的準(zhǔn)確性和效率。本文采取的具體解決方法是：路由器MIB庫(kù)中的ipAddrTable表中提供了該網(wǎng)絡(luò)設(shè)備所有的IP地址信息，ipAddrEntry表中的每一行是一個(gè)ipAddrEntry，而一個(gè)ipAddrEntry對(duì)應(yīng)一個(gè)接口的地址信息。由于ipAddrTable中的對(duì)象都是只讀的，所以使用ipAddrTable中的一個(gè)IP地址來(lái)標(biāo)識(shí)路由器，同時(shí)結(jié)合ifTable表，可以把接口和其IP地址一一對(duì)應(yīng)起來(lái)。在實(shí)際應(yīng)用時(shí)選擇ipAddTable中的最大的IP作為路由器的標(biāo)識(shí)IP地址更合理，由此就解決多IP識(shí)別問(wèn)題。

2）控制拓?fù)溟撝?/p>

上述算法利用路由表來(lái)從內(nèi)向外發(fā)現(xiàn)路由器，可以發(fā)現(xiàn)的范圍很廣，如果不加以控制，可能造成拓?fù)浒l(fā)現(xiàn)時(shí)間過(guò)長(zhǎng)，達(dá)不到預(yù)期發(fā)現(xiàn)的效果。通過(guò)對(duì)路由器的向下發(fā)現(xiàn)Hop數(shù)進(jìn)行控制，并設(shè)置閾值，當(dāng)從某個(gè)路由器向下發(fā)現(xiàn)Hop數(shù)達(dá)到設(shè)定閾值，則停止繼續(xù)向下發(fā)現(xiàn)。這樣得到的拓?fù)浒l(fā)現(xiàn)結(jié)果是以種子節(jié)點(diǎn)為中心向外輻射的星形樹，同一層次的路由器處于同一樹干上。但有時(shí)為簡(jiǎn)化程序復(fù)雜度，也可以利用限制拓?fù)浒l(fā)現(xiàn)時(shí)間的辦法來(lái)控制發(fā)現(xiàn)的范圍[7]。

3 算法應(yīng)用

依據(jù)上述算法思想，在某公司的網(wǎng)絡(luò)綜合管理平臺(tái)中成功實(shí)現(xiàn)了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的自動(dòng)發(fā)現(xiàn)，并驗(yàn)證了算法的正確性。該平臺(tái)以開源OPENNMS框架為基礎(chǔ)進(jìn)行二次開發(fā)，主要功能包括拓?fù)鋱D管理、設(shè)備管理、排程管理、告警管理、報(bào)表管理和性能管理等，可以對(duì)網(wǎng)絡(luò)中的各類設(shè)備進(jìn)行全面管理和監(jiān)控，及時(shí)發(fā)現(xiàn)并排除設(shè)備故障。

網(wǎng)絡(luò)拓?fù)渌惴ú捎玫拈_發(fā)工具為M Y E C L I P S E 7.0，開發(fā)語(yǔ)言是J a v a，使用JDK1.6.5，前臺(tái)的拓?fù)鋱D繪制采用Flex技術(shù)實(shí)現(xiàn)。算法對(duì)交換機(jī)和路由器的MIB庫(kù)的訪問(wèn)利用了Java SNMP開源開發(fā)包，該開發(fā)包實(shí)現(xiàn)了SNMP協(xié)議的V1和V2版本。

在校園網(wǎng)的實(shí)驗(yàn)試驗(yàn)環(huán)境下，主干網(wǎng)絡(luò)由1臺(tái)路由器和多臺(tái)三層交換機(jī)組成，交換機(jī)下掛接了若干PC服務(wù)器，用本算法對(duì)此網(wǎng)絡(luò)進(jìn)行探測(cè)，所得到的拓?fù)鋱D如圖1所示。

根據(jù)圖1的顯示結(jié)果分析，本算法已經(jīng)正確地識(shí)別出來(lái)了路由器172.18.45.1和交換機(jī)172.18.45.118、172.18.45.215、172.18.45.125、192.168.0.47，以及連接在交換機(jī)上的所有服務(wù)器。本發(fā)現(xiàn)算法發(fā)現(xiàn)效率高、實(shí)用性強(qiáng)，可廣泛應(yīng)用于網(wǎng)絡(luò)管理軟件的拓?fù)鋱D管理。

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

網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)對(duì)網(wǎng)絡(luò)管理系統(tǒng)非常重要，各個(gè)軟件廠商也采用自己的實(shí)現(xiàn)方法開發(fā)了一些進(jìn)行拓?fù)浒l(fā)現(xiàn)的系統(tǒng)。本文對(duì)SNMP網(wǎng)絡(luò)拓?fù)渌惴ㄟM(jìn)行了深入研究，并在此基礎(chǔ)進(jìn)行了改進(jìn)，提高了算法的發(fā)現(xiàn)效率，增強(qiáng)了網(wǎng)絡(luò)拓?fù)湫畔@示的直觀性，為網(wǎng)絡(luò)管理、網(wǎng)絡(luò)故障定位和網(wǎng)絡(luò)設(shè)備管理提供了強(qiáng)有力的支持。該方法已成功應(yīng)用于某公司的網(wǎng)絡(luò)綜合管理平臺(tái)，取得了良好的效果。

[1] Y.Breitbart,M.Garofalakis,B.Jai,C.Martin,R.Rastogi,A.Silbe rschatz,"Topology Discovery in Heterogeneous IP Networks:The NetInventory System,"IEEE/ACM Transactions on Networking,vol.12,no.3,June 2004,pp.401-414.

[2] F.Nazir,T.H.Tarar,F.Javed,H.Suguri,H.F.Ahmad,A.Ali, "Cons tella:A Complete IP Network Topology Discovery Solution,"APNOMS 2007,October 2007,Sapporo,Japan,pp.425-436.

[3] N.Dufield,F.L.Presti,V.Paxson,D.Towsley,"Network Loss Tomography Using Striped Unicast Probes,"IEEE/ACM Transactions on Networking,August 2006,vol.14,no.4, 697-710.

[4] 孫德文,高儒振.基于SNMP網(wǎng)絡(luò)拓?fù)鋱D的自動(dòng)構(gòu)造實(shí)現(xiàn)[J].上海交通大學(xué)學(xué)報(bào),1997,31(8):97-101.

[5] 楊棉.網(wǎng)絡(luò)自動(dòng)拓?fù)浒l(fā)現(xiàn)算法研究[D].武漢:華中師范大學(xué),2003.

[6] 李玉鵬,王換招,田海燕,等.基于SNMP和JAVA的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2004,(5):152-154.

[7] 李子柱,倪春勝等.網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程,2006,1(2):104-106.