SNMP拓扑发现方法分析总结.docx

1 SNMP协议介绍及算法说明1.1 SNMP协议介绍SNMP是目前最流行的网管协议。作为应用层上的协议，它主要通过一组Internet协议及其所依附的资源提供网络管理服务。利用SNMP管理工作站可以远程管理所有支持这种SNMP的网络设备，包括监视网络状态、修改网络设备配置、接收网络事件警告等。1.2 管理信息库MIB管理信息库MIB（Management Information Base）是网络管理系统中所有被管理元素信息的数据库。数据库中的元素是网管中的被管资源，且被管资源以对象来表示，每个对象表示被管资源某一方面的属性。通过对这些对象的存取访问，就可以得到网络设备的所有静态或动态内容，涵盖网络性能、配置、路由和故障等各个方面。每个对象又包含若干信息变量，每个信息变量包含如下信息：变量名、变量的数据类型、变量的读写属性、变量的值。MIB的定义与具体的网络管理协议无关，厂商可以在产品（如路由器）中包含SNMP代理软件，并保证在定义新的MIB项目后该软件仍遵守标准。用户可以使用同一网络管理客户软件来管理具有不同版本的MIB的多个路由器。MIB中的所有被管对象都被排列在一个树形结构之中。处于叶子位置上的对象是实际的被管对象，每个实际的被管对象表示某些被管资源、活动或相关信息。MIB分为公有MIB和私有MIB，公有MIB-2（RFC1213）是1990年定义的，所有设备厂商都支持该MIB库定义的OID变量，每个厂商还可以补充自己的MIB库，这就是私有MIB，例如Cisco的私有MIB是1.3.6.4.1.9开始，该节点下的所有自变量都是Cisco自己定义的。9是Cisco申请的唯一厂商编号。1.3 算法思想基于SNMP的拓扑发现算法方法，其基本思想是所有的网络设备维护一个MIB库，保存其所有运行进程的相关信息，并对管理工作站的查询进行响应。在网络设备的MIB中含有网络连接的信息，基于SNMP的网络拓扑发现算法就是通过采集设备的MIB数据，从中提取出关于网络拓扑的信息。算法从管理中心的缺省路由开始，采用广度优先搜索遍历的方法，对整个网络中的路由进行广度搜索，用SNMP获取每台被搜索到的路由器的路由表、地址表等信息，然后进行综合分析，从而发现网络中的路由拓扑结构。然后进行子网搜索，确定子网内各网络设备的状态、类型等。1.4 算法理论基础从设备的MIB库中提取出与逻辑网络拓扑发现相关的信息，然后将这些信息归纳、总结，从而得出网络的路由拓扑结构。在算法中需要使用的MIB-II对象描述如下：（1） system组算法中使用的对象有sysObjectID,sysLocation和SysService.（2） ip组算法中使用的对象有简单对象ipFowarding和两个表对象，ipAddTable（地址表）、ipRouteTable（路由表）。（3） interfaces组算法中使用的interfaces组的对象是ifNumber，表示系统中的网络接口数量。2 现有的网络拓扑发现算法2.1 传统的SNMP拓扑发现算法算法中定义三个队列用于实现基于SNMP的网络拓扑发现算法，分别为路由器队列、子网队列和连接队列，用于存放发现过程中的路由器、子网和连接关系。以运行拓扑发现的主机的默认网关为起始节点，访问其路由表，对于路由表的每项ipRouteDest，如果对应的ifType=4，将下一跳路由器地址ipRouteNextHop放到路由器队列，将ipRouteNextHop和路由器的连接放到连接队列。如果对应的ifType=3，将ipRouteDest放到子网队列，将ipRouteDest和路由器的连接放到连接队列中。其中的数据结构定义如下： Struct RouterQueueIpAddress routerIp;RouterQueue *next;Struct SubNetQueueIpAddress subnetIp; /子网地址IpAddress subnetMask; /子网掩码Int subnetType; /子网类型连接可用一个二元组(from,to)来表示Struct ConnectQueueItemIpAddress from;IpAddress to;ConnectQueueItem *next;*ConnectQueue;算法描述：Begin初始化路由器队列，子网队列，连接队列；把缺省路由器放入到路由器队列中；While（路由器队列非空）从路由器队列中取出一个路由器，为currentRouter;访问currentRouter路由表；If（ifType=3）/表示ipRouteNextHop和currentRouter相连接把路由表中的各ipRouteNextHop不重复地放到路由器列表中；把currentRouter与各ipRouteNextHop的连接不重复地放到连接队列；If（iftype=4）ipRouteDest不重复地放入到子网队列中；把currentRouter与ipRouteNext的连接不重复地放入连接队列中；根据子网队列的子网地址和子网掩码利用ping技术来发现子网内的其他设备；End经过上述的遍历过程，可以得到网络中支持SNMP协议的路由器和子网。2.2 改进的SNMP拓扑发现算法对于SNMP发现算法有很多种改进的方法，多数是针对路由器多IP问题，且是在传统算法的基础上进行的。下面一种改进方法，改进了原算法中的数据结构，并且采用多线程发现。（1） 已访问路由器的二叉排序树Struct routerNodeIpAddress id; /标识本路由器的idIpAddress ip; /路由器端口ip地址routerNode *left; /指向左子树的指针routerNode *right; /指向右子树的指针 VisitedRouter二叉树类，其中：root:树的根节点（2） 路由器与路由器的连接队列用来存储路由器之间的连接信息，其数据结构表示为：connRoute（3） 路由器与子网的连接队列用来存储路由器与子网的连接信息，其数据结构表示为：connSubnet算法流程描述如下：（1） 初始化，将当前机器的默认网关作为种子节点，将其插入到VisitedRoute二叉树中。（2） 将当前路由器的所有端口地址插入到VisitedRoute二叉树中。访问当前路由器中的ipRouteTable表得到每一项ipRouteNextHop和ipRouteType。（3） 如果ipRouteNextHop代表的路由器不在VisitedRoute中并且ipRouteType值为4则说明目标子网不是直接和路由器相连，ipRouteNextHop代表了下一条路由器地址，将当前路由器信息和ipRouteNextHop代表的路由器信息加入到RouteConnect中，并启动路由器发现线程。（4） 如果ipRouteNextHop代表的路由器不在VisitedRoute中并且ipRouteType值为3则说明目标子网与路由器直接相连，将当前路由器和子网信息记录到SubnetConnect数据结构中，并启动子网发现线程。（5） 如此方法直到所有的路由器和子网都被遍历过。3 算法分析3.1 速度传统的SNMP拓扑发现算法的复杂度较高，为网络中可访问的路由器数目的3次幂，管理的网络规模较大时，搜索速度比较慢。如果路由器数量为n，则算法的复杂度为O(n3)。与传统的SNMP拓扑发现算法相比，路由器数量同样为n，采用二叉树排序树结构改进算法的复杂度将为O(n2)。需要指出的是基于MIB-II的网络拓扑发现，若使用单线程，不管采用何种算法，都必须访问所有的路由器以及相应的每个路由器的路由表，即算法复杂度最少为O(n2)。若采用多线程，可以节约时间和提高效率，但空间复杂度会提高。3.2 负载在基于SNMP的算法中，给网络引入的负载包括获得拓扑信息的SNMP数据包和为判断一个地址是否有效所引入的ICMP报文利用Ping引入的。由于由ICMP所引入的负载远远大于其他因素引入的负载，所以可以用一个算法用到的所有ICMP报文在网络中所经历的总跳数（hop）代表该算法对网络造成的负载。按照这个定义，对于Ping，假设对每个节点Ping2次，则要判断一个H跳处的设备是否有效需要引入的负载是4H。3.3 完整性影响SNMP拓扑发现算法完整性的因素主要有两个，一是网络上的设备是否支持SNMP，二是管理站是否有权限访问节点的MIB库。算法要求设备必须支持SNMP协议，但一些老的设备上没有实现SNMP。在新一点的设备上，SNMP也可能被关掉了或者有访问的权限限制。对于完全支持SNMP协议的网络，拓扑发现的完整性是非常高的。因此网络中不支持SNMP协议以及没有访问权限的设备的数量决定了拓扑发现的完整性。3.4 准确性准确性可用算法对多个可选的拓扑结构的可能性来表示。SNMP算法中影响准确性的因素是对路由器多IP问题的判定。一个路由器有多个端口，每个端口对应一个IP地址，传统的SNMP算法在拓扑发现时会将一个路由器的多个端口的不同IP地址作为不同的路由器而被发现，造成拓扑图的不正确。图1 路由器多IP问题针对这个路由器多IP问题的判定，很多人提出了不同的改进算法。每种方法有各自的优点但是也都或多或少存在一些问题。大部分传统算法根据sysObjectID的值作为设备的ID来识别设备，因为每台设备在出厂时就被赋予了一个不同的sysObjectID值，这种方法大多数情况下是正确的，但由于它不像MAC地址一样是全世界唯一的，也有可能重复。因此有人提出不仅使用sysObjectID的值，还使用sysLocation的值，因为在sysObjectID有可能重复的情况下，sysLocation的值是不可能相同的。但是实际网络中路由器MIB中的sysLocation很多都没有赋值。有人提出通过MIB中的sysDescr、sysName和IfNumber这三项来归并同一路由器的不同IP的方法。还有人提出参照OSPF协议将路由器地址表（ipAddrTable）中最小的IP地址作为它的标记。也有人提出了基于二维链表的路由器多IP地址合并算法。4 其他需要考虑的问题4.1 私有MIB库在多厂商设备网络环境中，由于各个厂商大量地定义私有MIB，以扩展管理功能，使得多厂商网络的综合网管面临MIB异构性问题。一些通用网络管理软件可以提供一个第三方的网关平台，支持对所有SNMP设备的发现和监控，可集成厂商设备的私有MIB库，实现对全网（多厂商）设备进行识别和统一的管理。但私有MIB的定义一般都是用于扩展新特性的，而拓扑发现中所需的信息在公有MIB-II中定义的对象就已经足够，因此私有MIB对拓扑发现中SNMP协议对MIB的读取并没有太大的影响。4.2 拓扑范围的控制传统SNMP拓扑发现方法中没有对拓扑发现的范围加以控制，如果把它直接运用与广域网中，算法可能会无限执行下去，直到耗尽系统资源为止。所以需要限制拓扑发现的规模，不能让其无限地发现下去。因此可以通过采用设置阈值的方法进行解决，即设置最大要发现的路由器数目，通过比较已发现的路由器数目是否大于这个阈值来控制拓扑的发现范围。4.3 算法执行效率的问题实际网络环境中，网关路由表往往会很大，需要进行路由表冗余条目过滤。如对于路由表中ipRouteDest的值为255.255.255.255、127.