基于多源拓扑自动发现算法研究

◆周林鹏 何锡点

基于多源拓扑自动发现算法研究

◆周林鹏 何锡点

（中国电子科技集团公司第二十八研究所 江苏 210000）

经实验发现，传统拓扑发现算法中存在节点冗余发现、链路关系不全、网关和交换机管理IP无法区分等问题。本文基于SNMP、OSPF、LLDP和ICMP等协议，融合多源数据分析，提出一种拓扑发现改进算法。通过搭建数据中心网络拓扑实现，发现新算法较传统算法而言，拓扑发现更全面、更准确，能够为全网拓扑发现提供支撑。

网络拓扑；SNMP；LLDP；多源分析

拓扑自动发现算法有很多种，但主流主要有两种：数据链路层拓扑发现和网络层拓扑发现。从目前研究现状来看，两种传统的拓扑发现算法在使用中存在的局限性，较难适配现有网络环境。通过搭建实验研究，发现其主要存在以下突出问题：（1）由于SNMP协议[1]是基于TCP/IP协议，使用交换机管理IP和网关分别作为目标地址时，采集MIB信息时，两者返回结果完全一致，故无法区分网关、交换机设备，导致拓扑信息冗余；（2）通过SNMP采集ARP、Route等信息与交换机系统版本有关，可能导致拓扑节点发现不全；（3）同一节点信息可能存放于多台交换机设备的ARP、Bridge等信息中，可能导致链路重复发现或发现不全。本文以SNMP、OSPF、LLDP和ICMP协议为基础，对传统拓扑发现算法进行改进，能够有效提高拓扑发现能力。

1 现有网络拓扑发现协议及算法

1.1 常用拓扑协议

常见的拓扑发现协议有如下几种，如表1：

表1 常见的拓扑发现协议

1.2 传统网络层拓扑发现算法

传统网络层拓扑发现算法基本思路是：从默认网关路由器开始，采用SNMP协议对网关IP进行扫描，读取ipRouteTable信息，获取其ARP表信息，判定设备当前类型（路由、交换机或主机）[4]。遍历当前对象ipRouteDest信息，根据 ipRouteType判定其是否为直接路由，获取掩码ipRouteMask信息，确定子网范围。采用ICMP，对子网设备状态进行判定。获取ipRouteNextHop下一跳路由，作为新的入口路由器，直到发现全网设备[5]。

经实验发现，此类网络层拓扑发现存在以下不足：

（1）通过SNMP采集到的ipRouteDest可能同时包含交换机设备IP、网关IP等，其分别采集的ipRouteNextHop返回结果完全一致，在进行后续条件判定会产生节点发现冗余；

（2）某些设备采集不到完整的ipRouteNextHop信息，可能导致网络拓扑发现不全；

（3）部分设备的ipRouteType信息中，存在大量冗余信息，会对后续发现产生干扰。

1.3 传统链路层拓扑发现算法

传统链路层拓扑发现算法基本思路为：以入口交换机为出发点，首先通过SNMP协议、ARP协议，获取入口交换机中缓存的地址转发信息。识别出哪些是有用端口后，通过模糊匹配获取到连接主机和交换机。通过采集交换机CDP邻居表信息，将新的交换机作为入口交换机，通过采用递归算法，直至发现一个完整的网络拓扑[6]。

经实验，此类链路层拓扑发现存在以下不足：

（1）通过ARP协议采集的数据可能在多台设备中均存在，导致拓扑发现数据冗余、链路发现不准确；

（2）对于与交换机逻辑口相连的场景，由于为同一端口接入，MAC地址一致，无法确认设备连接关系。

2 基于多源分析拓扑发现算法

为了克服传统网络层、链路层拓扑发现算法的不足，本文提出一种基于多源分析拓扑发现算法。其核心思想是基于SNMP协议，递归采集交换机ARP信息，辅助以LLDP、OSPF、ICMP等多种协议采集数据，综合多源数据进行分析，确定网络拓扑关系。

改进算法的前提：用户需要开启交换机SNMP服务，配置团体字。对支持LLDP协议的交换机需要开启LLDP协议。其核心步骤如下：

（1）获取设备IP和MAC映射关系；

（2）获取交换机直连关系；

（3）分析交换机管理地址、网关，获取子网范围；

（4）综合分析网络拓扑结构。

本算法中，涉及的主要MIB信息和OID表如表2。

2.1 获取设备IP和MAC映射关系

（1）将入口交换机作为目的交换机，使用SNMP协议获取该设备ARP和SYS模块信息，主要包括： ipNetToMediaIfIndex、ipNetToMediaPhysAdress、ipNetToMediaNetAdress、sysDescr、ipNetToMediaType等属性；

（2）根据（1）中获取的ipNetToMediaType、sysDescr属性以及SNMP协议是否有返回值等，综合判定是否为交换机或路由设备。若为交换机，则执行步骤（3）；若不为交换机，则执行（3）步骤；

（3）设置设备类型为主机类型。记录当前相连交换机IP、ipNetToMediaIfIndex；

（4）将以上信息存储至ArpInfo_List集合中，便于后续综合分析。

表2 SNMP相关主要MIB信息表

2.2 获取交换机之间直连关系

（1）判定目的交换机当前是否支持LLDP协议，若支持，则获取交换机的NeiPortIndex和NeiMac信息。若不支持，则从遍历ArpInfo_List，将下一个交换机作为目的交换机；

（2）截取NeiMac的前13字节（如：00：00：00：00：0）作为此交换机的MAC（实验发现，交换机各端口MAC地址不相同，但主流交换机中各端口存在MAC前部分字节重复，如华为、Cisco等厂商同一设备端口前14位一致，中兴、迈普等设备端口的前13位一致。故此处采用MAC前13字节）；

（3）从ArpInfo_List集合中模糊匹配（2）中的交换机MAC，获取新发现的交换机IP地址；

（4）将（3）中发现的交换机作为目的交换机，递归执行（1）、（2）、（3）步骤；

（5）将发现的交换机记录至Switches_Queue集合，同时将交换机之间的直连关系记录至Switches_Lines集合。

图2 获取交换机之间直连关系

2.3 区分交换机管理地址和网关，获取子网范围

（1）从目的交换机为入口，采集其IpAdEntAddr、IpAdEntIfIndex等信息；

（2）通过IpAdEntAddr和IpAdEntIfIndex对比匹配，过滤IP为目的交换机或IP为“127.0.0.1”的IP，获取网关IP。同时，设置ArpInfo_List集合中对应IP的设备类型为网关；

（3）获取目的交换机IpAdEntNetMask掩码信息，结合（2）中的目的交换机网关，计算目的交换机对应子网IP范围；

（4）遍历Switches_Queue集合，将下一个交换机指定为目的交换机，递归执行（1）（2）（3）步骤，直至所有交换机遍历结束为止，将所有子网信息存至ChildNet_List集合。

图3 区分交换机管理地址和网关，获取子网范围

2.4 综合分析拓扑结构

（1）分析交换机直连关系Switches_Lines集合，若某交换机节点出现的次数最多，则设定其为根节点交换机；

（2）从根节点交换机开始，采用深度遍历算法，分析其直连交换机。若存在直连交换机，则执行（3）步骤；若不存在则，执行（4）步骤；

（3）获取根节点交换机对应的Bridge信息，若dot1dTpFdbPort中无重复，则记录其对应端口的MAC地址dot1dTpFdbAdress。若dot1dTpFdbPort中出现重复，则根据ArpInfo_List中端口索引、交换机直连关系Switches_Lines、以及dot1dTpFdbPort最小重复次数为依据，确定根节点直连交换机MAC和IP。记录交换机与交换机端口连线关系，并将新发现的交换机作为新的根节点交换机，递归执行（1）（2）（3）步骤；

（4）根据ArpInfo_List集合、ChildNet_List集合，综合分析与之相连的子网或主机设备；

（5）遍历ARP表中未连接的离散点，获取其ArpInfo_List集合中的IP、端口索引进行匹配，若其交换机IP、端口索引完全匹配，则记录其连线关系；

（6）采用ICMP、OSPF等协议，验证拓扑分析的准确性，并加以修正。同时，确定设备节点的实时状态。

图4 综合分析拓扑结构

3 结果与分析

本实验环境主要由9台交换机组成，一个核心交换机，多台接入交换机，在接入交换机上配置网关，连接各子网。

采用传统拓扑发现算法，其采集拓扑关系如下（图5）。

实验分析发现，与核心交换机直连的还有192.168.9.*的子网，且存在部分交换机发现不全等现象。

采用本文改进拓扑算法分析，其最终发现的拓扑图如下（图6）。

实验结果与实际真实拓扑基本一致。经对比说明，改进拓扑发现算法能够更准确、全面发现拓扑结构。能够对全网拓扑发现起到支撑作用。

图5 传统算法拓扑发现效果图

图6 改进算法拓扑发现效果图

4 结束语

本文给出了一种基于多源拓扑自动发现算法。能够基于现有ARP、SNMP等协议的局限性，尽可能完整发现全局网络拓扑结构，能够有效过滤网关IP，提供更为高效的拓扑发现和分析手段。在今后工作中，要尝试对含有防火墙、安全策略的网络拓扑结构进行研究，相信会有更多的优秀成果。

[1]张春强.深入理解Net-SNMP[M].北京：北京机械工业出版社，2015.

[2]薛健.IP 级网络拓扑发现技术的研究与实现[D].哈尔滨：哈尔滨工业大学，2013.

[3]Nur A Y，Mehmet E T.Cross-AS（X-AS） Internet Topology Mapping[Z].Computer Networks，2018：132.

[4]Motamedi R，Rejaie R，Walter W.A.Survey of Techniques for Internet topo-logy discovery[J].IEEE Communications Surveys & Tutorials，2015，17（02：1044-1065.

[5]Kardes H，Gunes M，Oz T.Cheleby：A Subnet-Level Internet Topology Mapping System[C].Communication Systems and Networks（COMSNETS），2012：1-10.

[6]周长建.融合多协议的网络层拓扑发现算法研究[D]. 哈尔滨：哈尔滨工业大学，2017.