基于SNMP的網絡拓撲自動發現算法的研究和應用1

聶 明

（南京信息職業技術學院，南京 210046）

0 引言

隨著網絡規模的日益擴大，復雜度的不斷增加，網絡拓撲結構也隨之變得日益復雜。一個好的網絡管理系統應該反映網絡中所有設備的布局結構，方便用戶全方位地管理網絡，對網絡異常流量、設備告警、網絡攻擊現象等進行快速診斷和定位，以減少網絡異常造成的損失[1]。網絡拓撲的自動發現，其目的是獲得被管理網絡的拓撲結構，主要指互連設備，如路由器、交換機、PC設備等的信息以及它們之間的連接關系。網絡拓撲的自動發現是網絡管理系統的重要組成部分，是發現系統故障和監控設備性能的基礎，更是衡量一個網絡管理系統成敗的重要標準之一[2]。

1 網絡拓撲的自動發現

網絡拓撲的自動發現通過收集網絡拓撲的各種必要信息，確定網絡元素之間的互連關系，并在此基礎上構造網絡拓撲圖，為網絡管理人員提供一個直觀了解全局網絡狀態的友好界面。網絡拓撲的自動發現是對大規模網絡進行有效管理的必不可少的手段，當前常用的網絡拓撲自動發現方法主要包括基于ARP協議的拓撲發現方法、基于ICMP協議的拓撲發現方法和基于SNMP協議的拓撲發現方法等[3~6]。

1）基于ARP協議的拓撲發現方法。每個支持地址協議的網絡設備中都維護著一張ARP表，該表記錄了該設備連接的網絡設備的IP地址和MAC地址的對應關系。利用ARP表，可以從一臺已知路由器或交換機的ARP表發現其連接的其它網絡設備，從這些新發現設備中區分出路由器和交換機，并繼續根據這些路由器和交換機的ARP表進行設備發現，從而得到整個網絡的拓撲結構。因為ARP表中的網絡設備地址都是最近活動過的有效設備的IP地址，幾乎沒有冗余信息，所以該拓撲發現方法效率很高。但如果網絡過大，ARP表中可能無法包括網絡中實際存在的所有網絡設備，同時待發現的網絡設備需要支持ARP協議，所以該方法適合于局域網的拓撲發現。

2）基于ICMP協議的拓撲發現方法。它通過向網絡設備發送ICMP報文，測試設備的可達性。該方法對一個網段內所有設備的網絡IP地址依次執行ping操作，根據響應就可以發現當前該網段內所有活動的網絡設備。根據給定的IP區間逐一進行ping操作，根據結果，再對上一次操作記錄的活動的IP地址逐一進行路由跟蹤，記錄下每一次路由跟蹤的操作結果，根據前面的操作結果，再分析所得到的信息，從中得到整個拓撲的連接情況。該拓撲發現方法簡單、可靠、快速，但發現具有一定的盲目性，并在一定程度上加重了網絡的負荷等，此方法適用于子網內網絡設備的發現。

3）基于SNMP的拓撲發現方法。每個網絡設備都有路由表，路由信息中包含了完整的網絡拓撲信息，包括路由目的網絡地址、目的網絡的子網掩碼、該路由的下一站IP地址、對應的端口索引和路由協議類型等。由于路由表中的下一站地址項所標識的必然是具有路由功能的網絡結點，因此從設定路由器開始，讀取路由器的路由表，可以逐漸向下發現網絡中所有基于路由功能的網絡結點。再根據路由表的本地接口的索引標識項，找到接口表中對應的接口索引，由接口表的接口類型就可以了解到所在子網的類型，從而構建出整個網絡的拓撲關系圖。這種方法的拓撲發現過程和算法簡單，目標明確，發現效率高，系統和網絡開銷小，因此得到人們的廣泛應用。但是，該方法也存在不足之處，主要表現在：

（1）無法發現網絡中沒有配置IP的網絡設備；

（2）一個路由器往往配置了多個IP地址，并且基于路由表的發現方法算法是基于IP地址的，所以對于路由器多IP現象，可能導致路由器的發現與實際情況不合；

（3）要依次檢測各網絡設備的狀態，導致算法運行時間可能過長，同時設備的發現受網絡時延等影響，不能完全實時反映網絡狀況；

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

（5）網絡設備必須支持SNMP協議。

因此，該方法主要用于大型主干網絡的拓撲發現，主要發現網絡中的路由設備，反映網絡的整體拓撲結構狀況。

可見，當前各種拓撲方法各有優缺點和局限性，在實際應用中需要根據具體的情況，有選擇或綜合地應用。本文給出了一種基于SNMP的網絡拓撲發現算法，經過實際網絡管理系統的驗證，能夠有效發現整個網絡的拓撲結構。

2 基于SNMP的網絡拓撲自動發現算法

2.1 算法思想

在網絡中路由器之間的鏈路是由其兩端路由器的端口互聯構成的，根據TCP/IP的編址原理，鏈路兩端路由器端口的IP地址必然處于同一個子網中。因此，通過一個子網中已知的IP地址和這個IP地址的子網掩碼即可計算出該子網中所有其他的IP地址。

根據以上思路，從某個節點開始，訪問其MIB庫，得到該節點所有接口的IP地址和子網掩碼，該節點稱為種子節點。通過計算得到與每一接口在同一個子網內的其他IP地址。判斷這些IP地址是否屬于路由器信息，如果是則將此路由器信息記錄到待檢測路由設備鏈表，作為下一層發現的種子節點。并同時記錄兩個路由器間的鏈路信息到拓撲信息鏈表。重復以上步驟直到沒有種子節點或者達到指定的發現層數，即可完成相應的拓撲發現過程。

2.2 算法描述

算法可具體描述如下：

1）根據網絡管理系統的IP和掩碼，使用路由跟蹤的方法獲取網管終端所在的默認路由器網關地址。訪問該路由器獲取ipAdderssTable地址表信息，將其編號加入AllRouters隊列（元素包括路由器名、接口號、接口IP、接口號和接口IP等），其中接口號與接口IP的多少依據各個不同路由器而不同）和AccessRouters隊列（待訪問路由器，結構跟AllRouters類似）；

2）從AccessRoutes取出一個元素設為當前處理的路由器Rx，依次訪問Rx的路由表ipRouteTable表項，將目標子網信息編號無重復地放入子網隊列Subnets（元素包括子網號，子網地址，掩碼等）；

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

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

5）把隊列R-links-R進行去冗處理。因為在以上的算法實現中，有可能存相同的連接信息加入到隊列中。例如:R1的2端口與R4的3端口直接相連，在算法實現過程中，可能同時在隊列中加入了（R1，2，R4，3）和（R4，3，R1，2）的元素組，雖然它們在形式上不一樣，但他們表示同一個連接信息。

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

算法運行結束以后，AllRouters包含了所有活動的路由器，子網隊列Subnets包含了所有活動的子網，隊列R-links-S和隊列R-links-R的信息表示路由器與子網、路由器與路山器之間連接關系，最終可以準確而完整地把拓撲結構繪制出來。

2.3 拓撲發現中幾個問題

1）路由器多IP地址問題

路由器的每個接口對應著一個IP地址，一個接口下可以配置多個端口。根據以上拓撲發現方法，就會出現重復訪問同一路由器的現象，嚴重影響拓撲發現算法的準確性和效率。本文采取的具體解決方法是：路由器MIB庫中的ipAddrTable表中提供了該網絡設備所有的IP地址信息，ipAddrEntry表中的每一行是一個ipAddrEntry，而一個ipAddrEntry對應一個接口的地址信息。由于ipAddrTable中的對象都是只讀的，所以使用ipAddrTable中的一個IP地址來標識路由器，同時結合ifTable表，可以把接口和其IP地址一一對應起來。在實際應用時選擇ipAddTable中的最大的IP作為路由器的標識IP地址更合理，由此就解決多IP識別問題。

2）控制拓撲閾值

上述算法利用路由表來從內向外發現路由器，可以發現的范圍很廣，如果不加以控制，可能造成拓撲發現時間過長，達不到預期發現的效果。通過對路由器的向下發現Hop數進行控制，并設置閾值，當從某個路由器向下發現Hop數達到設定閾值，則停止繼續向下發現。這樣得到的拓撲發現結果是以種子節點為中心向外輻射的星形樹，同一層次的路由器處于同一樹干上。但有時為簡化程序復雜度，也可以利用限制拓撲發現時間的辦法來控制發現的范圍[7]。

3 算法應用

依據上述算法思想，在某公司的網絡綜合管理平臺中成功實現了網絡拓撲結構的自動發現，并驗證了算法的正確性。該平臺以開源OPENNMS框架為基礎進行二次開發，主要功能包括拓撲圖管理、設備管理、排程管理、告警管理、報表管理和性能管理等，可以對網絡中的各類設備進行全面管理和監控，及時發現并排除設備故障。

網絡拓撲算法采用的開發工具為M Y E C L I P S E 7.0，開發語言是J a v a，使用JDK1.6.5，前臺的拓撲圖繪制采用Flex技術實現。算法對交換機和路由器的MIB庫的訪問利用了Java SNMP開源開發包，該開發包實現了SNMP協議的V1和V2版本。

在校園網的實驗試驗環境下，主干網絡由1臺路由器和多臺三層交換機組成，交換機下掛接了若干PC服務器，用本算法對此網絡進行探測，所得到的拓撲圖如圖1所示。

根據圖1的顯示結果分析，本算法已經正確地識別出來了路由器172.18.45.1和交換機172.18.45.118、172.18.45.215、172.18.45.125、192.168.0.47，以及連接在交換機上的所有服務器。本發現算法發現效率高、實用性強，可廣泛應用于網絡管理軟件的拓撲圖管理。

4 結束語

網絡的拓撲結構對網絡管理系統非常重要，各個軟件廠商也采用自己的實現方法開發了一些進行拓撲發現的系統。本文對SNMP網絡拓撲算法進行了深入研究，并在此基礎進行了改進，提高了算法的發現效率，增強了網絡拓撲信息顯示的直觀性，為網絡管理、網絡故障定位和網絡設備管理提供了強有力的支持。該方法已成功應用于某公司的網絡綜合管理平臺，取得了良好的效果。

[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網絡拓撲圖的自動構造實現[J].上海交通大學學報,1997,31(8):97-101.

[5] 楊棉.網絡自動拓撲發現算法研究[D].武漢:華中師范大學,2003.

[6] 李玉鵬,王換招,田海燕,等.基于SNMP和JAVA的網絡拓撲發現[J].計算機工程與應用,2004,(5):152-154.

[7] 李子柱,倪春勝等.網絡拓撲發現系統的設計與實現[J].計算機工程,2006,1(2):104-106.