基于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.