基于混合校验的高完整度网络拓扑发现方法*

寇晓蕤，董海量，焦永生

（61716部队，福建 福州 350003）

0 引 言

网络拓扑结构[1]是网络的基本属性，是网络管理、各类网络应用可视化和研究网络特性的基础。因此，网络拓扑图的自动绘制即网络拓扑发现技术研究一直是热门领域。

通常，根据粒度不同，网络拓扑发现可以分为四种层次[2]：接口级、路由器级、PoP级和AS级。接口级拓扑发现主要是研究网络接口之间的连接关系，每一个节点表示具有独立IP的接口，接口与IP地址一一对应。一台路由器通常有多个接口，也就用多个节点表示。节点之间的连接表示两个接口在IP层直接连接。路由器级拓扑发现主要研究获取子网级、设备级的拓扑结构[3]，即路由器与子网、网络设备之间的连接关系。PoP（Point of Presence）表示同一个自治域中的路由器集合。不同的PoP通过AS的骨干网连接。在PoP级拓扑中，每个节点表示一个PoP，连接关系表示两个PoP之间存在物理连接。AS级网络拓扑发现主要研究获取AS（Autonomous System，自治系统）级拓扑，即AS之间的连接关系，反映的拓扑相对宏观。

网络拓扑探测主要采用网络协议实现数据采集，常用的网络协议包括ICMP（Internet Control Message Protocol，因特网控制报文协议）、BGP（Border Gateway Protocol，边界网关协议）和SNMP（Simple Network Management Protocol，简单网络管理协议）。基于ICMP的方法[4]即采用Traceroute技术，通过依次发送IP数据报首部TTL（Time To Live，生存期）字段设置为1至最大跳的系列探测报文，并依次接收路由器的超时应答以获取路由器序列，即路由器的连接关系。在获取IP级拓扑后，通过解析IP所在的AS，即可推导出AS之间的连接关系。基于BGP的方法[5]则是通过直接分析BGP路由表以获取AS之间的连接关系。基于SNMP的方法主要用于发现路由器级网络拓扑[6]。SNMP协议体系架构中包含的关键要素是MIB（Management Information Base，管理信息库），其中包含不同的管理组。这些管理组中则包含了设备接口表、路由表和生成树协议等。网络管理节点通过读取被管设备MIB中的相关信息即可分析获取三层拓扑和二层拓扑，其中三层拓扑体现了路由器和子网之间的连接关系，二层拓扑则体现了桥接设备相关的连接关系。

在所有的拓扑描述方式中，三层拓扑最常见，因为它比IP级拓扑更细致精确。在一个有限的可视化平面内，子网能够将若干设备节点聚集为拓扑图上的一个子网节点，结合层进、回溯等可视化方法，清晰绘制拓扑图。三层拓扑主要采用基于SNMP的方法，要求目标网络中的所有设备开放UDP（User Datagram Protocol）161端口（SNMP代理端口），并且要求拓扑发现节点知道所有的SNMP代理口令。对于一个大型网络，这个条件很难实现。因此，本文提出一种基于混合校验机制的高完整度三层网络拓扑发现方法，同时使用基于ICMP和SNMP的探测技术，在进行综合分析后，利用校验机制对探测分析结果进行精化，从而在SNMP代理信息不完整的情况下获得较为完整准确的拓扑结构。

1 基于ICMP的三层拓扑发现方法

1.1 技术机制

图1为基于ICMP的网络拓扑发现技术原理。当探测端将探测报文的目的IP地址设置为D1的地址，将探测报文的IP数据报首部TTL值依次设置为1、2、3时，会依次收到R1、R2、R3的TTL超时回应。S解析应答报文即可获取R1的A11接口、R2的A21接口和R3的A31接口。同样，当探测端将探测报文的目的IP地址设置为D2的地址时，可以得到R1的A11接口、R2的A21接口和R4的A41接口。当探测报文的目的IP地址设置为目标网络的整个IP地址段时，即可获取整个网络中路由器与路由器以及路由器与终端的连接关系。

图1 基于ICMP的网络拓扑发现技术原理

在一个复杂的网络结构中，可能在探测过程中获取同一路由器的不同接口。图1中，R3的A32接口与R4的A42接口相连，则在拓扑探测过程中有可能获取A32或A42接口地址。为了避免将同一路由器的不同接口识别为不同路由器，基于ICMP的拓扑发现技术通常会采用“别名（Alias）”探测机制，即当向路由器的远端接口发送探测报文，收到应答报文的源地址为近端接口地址时，即可判断这两个地址属于同一个路由器。图1中，向A42发送探测报文，收到的应答报文为A41的IP地址，则认为这二者属于同一路由器。

1.2 子网推导算法

上述基本方法无法获取子网信息，下面对上述技术进行改进，以获取子网。

图2是一个C类网可能的子网划分树，每个子网包含的IP地址个数都是2的幂次。同时，路由器与子网连接配置遵守以下基本规则：

（1）两个路由器直连的两个接口IP地址属于同一子网；

（2）同一路由器的不同接口不在同一子网。

根据上述原则，设计子网推导的算法思想为：对于所发现的所有路由器别名地址，用WFS（Width First Search，广度优先搜索）算法从子网划分树的根节点开始遍历，找到其所在的子网节点；如果同一路由器的别名不在该子网内，则将该子网节点作为其连接的子网；否则，按照DFS（Depth First Search，深度优先搜索）方法继续向下搜索，直到同一路由器的所有别名都不处于某个子网节点。假设一个路由器的别名分别为192.168.0.1和192.168.0.65，则针对第一个IP地址从根节点开始遍历。由于第二个IP与其都处于“0-255”这个子网节点，所以继续向下搜索，最后找到“0-63”、“64-127”这两个子网节点。利用本算法得到的是一个路由器接口可能连接的最大规模子网。

图2 一个C类网可能的子网划分树

本算法伪代码如下：

void FindSubnet(Tree CClassNet，RouterAlias[N])

{

SubNet[N]=NULL;

int I,j,n=0;

int level;

for(level=0;level＜=CClassNet的 最 大 层 级；level++)

{

CClassNetSubnode[level]=CClassNet第 level层的所有子网节点集合;

for(i=0;i＜= CClassNetSubnode[level]的子网节点个数-1;i++)

{

for(j=0；j＜=N-1；j++)

{

if(RouterAlias[j]与其他任何一个别名不属于同一个CClassNetSubnode[level]的子网节点)

{

SubNet[n++]=CClassNetSubnode[level]的 第 i个子网节点;

RouterAlias[N] -= RouterAlias[j];

}

}

}

if(n＞=N)//如果所有别名均找到对应的子网节点

{

return;

}

}

return；

}

在上述伪代码中，RouterAlias[N]用于存储路由器别名，SubNet[N]用于存储找到的子网节点，level用于记录C类网层级，其中根节点视为0层。

2 基于SNMP的三层拓扑发现方法

2.1 基于DFS和WFS的方法

基于SNMP的三层拓扑发现通常采用DFS或WFS，即从根节点出发获取其路由表，然后从中按照相应策略选取下一个读取节点，直到获得所有节点。使用这种方法的优势在于探测效率高，获得的冗余信息少；缺点在于当网络中存在不开放SNMP的节点时，会造成拓扑图发现不完整。

图3左侧图给出了一个示例，其中直线表示子网（下同）。如果R3不支持SNMP，则无论使用DFS还是WFS，都只能获得图3右侧图所示的不完整拓扑。

图3 一个基于DFS或WFS方法的不完整拓扑发现示例

2.2 基于代理发现的方法

为避免搜索方法不足，使用基于代理发现的方法，这是一种遍历机制。定义支持SNMP访问的节点为SNMP代理。对于常用的SNMPv1（第一版）而言，安全认证机制为“共同体名”，相当于一个口令。大部分设备对读操作使用的共同体名默认设置为“public”。出于安全性考虑，网络管理员会更改默认口令。

基于以上考虑，为更完整地发现网络拓扑信息，可采用以下策略：

（1）将已知共同体名的设备作为SNMP代理写入列表；

（2）对于整个目标网段的设备，发送共同体名为“public”的SNMP读报文，若收到应答，则将相应设备写入代理列表，由此最大限度地寻找SNMP代理；

（3）对于所有SNMP代理，读取路由表通过综合分析获取子网层拓扑。

本方法效率低于基于DFS或WFS的方法，但完整度更高。图4示意了针对图3使用代理发现机制获取的拓扑，比基于DFS或WFS的更完整。此外，实验中发现，除路由器等交换桥接设备外，很多终端设备可作为代理，由此可以进一步提升拓扑发现完整性。在图5给出的示例中，R5和R8不是SNMP代理，但终端设备H是代理。如果不使用H，则R8分支将被隐去。

图4 使用代理发现机制发现的更为完整的拓扑图示例

3 基于混合校验机制的综合分析算法

3.1 基于ICMP的方法补全基于SNMP获取的拓扑图

利用SNMP获取的拓扑图，结果准确，但可能存在别名不统一和拓扑图不连通的情况。对于图4的示例，R31、R32、R33同属于R3；对于图5的示例，R51与R82不连通。为解决上述问题，使用基于ICMP的别名探测分析方法将R3的三个接口地址统一到同一路由器；使用基于Traceroute的路由器连接关系探测分析机制，可将R51与R82进行连接并进行子网推导。

图5 基于终端提升拓扑发现完整性示例

3.2 综合校验分析算法

为最大限度地得到完整的拓扑图，综合使用基于ICMP和SNMP的方法对网络拓扑进行探测分析，因此可能得到重复的结果。此外，由于基于ICMP的方式是对子网进行推导，因此存在并不完全准确的情况。因此，设计综合校验分析算法，以便获取无冗余且更精确的分析结果。从计算机处理角度看，子网层拓扑可描述为三元组[路由器连接子网的接口IP（别名），子网号，子网掩码]序列。基于这个三元组，具体的分析校验规则如下。

（1）冗余去除规则：如果两种方法同时发现了同一个三元组，则直接删除其中的一个；

（2）噪声去除规则：如果一个路由器别名相同，但利用两种方法获取的子网不同，则直接将基于ICMP发现的结果去掉；

（3）规模精化规则：如果一个别名相同，但利用ICMP方法获取的子网范围大于用SNMP发现的结果，则直接将利用ICMP获取的结果去掉；

（4）越界修订规则：别名不同，但如果用ICMP方法获取的子网与用SNMP方法获取的子网有重叠（前者子网覆盖后者，或有重合），则用后者修订前者，缩小前者的子网规模。

此外，基于ICMP的方法对网络拓扑进行探测分析的多个结果之间也可以相互进行校验，校验规则与上述第3、4条规则类似，即：

（1）规模精化规则：如果两种ICMP方法获取的别名相同但子网范围不同，则直接去掉子网范围较大的结果；

（2）越界修订规则：如果两种ICMP方法获取的别名不同但子网有重叠（前者子网覆盖后者，或有重合），则用后者修订前者，缩小前者的子网规模。

以上规则的核心是基于SNMP的方法比基于ICMP推导的方法能够获取更准确的结果。但是，考虑到实际网络的复杂性，二者结合使用并综合分析，可以互相弥补不足，最终获取最完整准确的拓扑图，这是一种尽最大努力的方法。

4 实验结果

为验证上述技术与算法的效果，在不预先设置任何共同体名的极端情况下对一个真实网络的拓扑进行探测分析，最终获取的结果如图6所示。可见，该方法能够有效发现三层网络拓扑。

图6 一个真实网络拓扑探测结果

5 结 语

本文给出了一种较有效的三层拓扑发现方法。对于一个大型网络而言，很难全面了解新加设备情况，也可能出现节点失效情况。为应对上述情况，本文给出了较为完美的解决方案。此外，设备使用默认共同体名是一种安全风险，本文也提供了一种检测该安全风险的方法。