网络拓扑发现算法的研究

宋翠

摘 要：本文主要针对目前比较常用的网络拓扑发现算法，进行了较深入的理论分析和研究。分析了拓扑发现在网络管理中的重要性，并总结出各算法的优缺点，并提出可以根据应用的实际环境，将多种拓扑发现算法融合，扬长避短，从而达到更佳的发现效果。

关键词：网络管理；SNMP；拓扑发现

一、基于SNMP协议的拓扑发现算法

该方法是通过标准的SNMP协议来实现的，由一个指定的或默认的路由器开始，通过读取该路由器的IP路由表，获取到下一跳路由器的IP地址信息。依据此法，采用广度优先遍历或深度优先遍历对整个网络内的路由器进行遍历，可依次向下发现网络中的路由器。将目的IP地址和子网掩码进行“与”运算，从而得到网络地址，再通过路由类型的判断，来确定所连接的子网类型，从而确定网络中各设备的互连情况，构建整个网络的拓扑图。因此，该算法简单易行，发现网络设备的效率高，网络与系统开销小。

其不足是：要求待发现的网络内的设备必须支持SNMP协议，否则无法发现。同时，出于对网络安全方面的考虑，在访问管理信息库时需要密码，即共同体的值，若是不知道该值，就无法访问网络设备，也就无法获得网络连接的信息。

二、基于ICMP协议的拓扑发现算法

首先给定一个IP地址范围，对该范围内的所有IP发起ping命令，将ping通的活动IP地址记录到IP地址表中。然后从该表中提取一个IP地址，对该地址进行TraceRoute操作，将途经的路由器记录到路由器队列中。重复上述操作，直至指定范围内的所有IP地址都操作完毕为止。接下来再对IP地址表中的每个IP地址发送子网掩码请求，从应答的报文中获取该IP地址所对应的子网掩码，确定其网络地址，并加入子网队列。将所得结果进行分析对照，合并归属于同一路由器的不同地址，从而得到网络的拓扑结构。此算法理论简单，操作方便，适用性较强，不仅能发现拓扑，又能检测网络设备和主机的存活性。

它的不足是：ping命令只能测试源与目的地之间的连通性，而途中经历了哪些设备却无法确定。使用TraceRoute命令，尽管能探测出途中经过的路由器，但此命令却不能直观地反映网络设备间的连接关系。由于给定的IP地址是个范围，不够准确，里面可能含有不存在的地址，在对每个IP都进行ping和TraceRoute操作时，就增加了系统开销，浪费了带宽，因此该方法效率不高。此外，如果防火墙处于开启状态，ICMP包则是无法通过，也就无法准确发现网络的拓扑结构。

三、基于RIP协议的拓扑发现算法

RIP协议是小型网络中常用的距离矢量路由协议，以跳数作为路径的度量标准，最大跳数为15跳，16跳则认为网络不可达。RIP协议分为RIPv1和RIPv2，其中RIPv2支持VLSM及CIDR技术。在发送路由更新时，将整张路由表发送给直连邻居。接收到邻居的路由更新时，同自己路的由表进行对照，将表中不存在的路由添加进来，对于表中已存在的路由比较一下哪个更优，则采用哪个。启用RIPv2的路由器在网络拓扑没发生变化时，默认每隔30秒钟就发送一次更新，即周期性更新；当拓扑发生变化时，则立即发送更新即触发更新。若路由条目在180秒内无更新收到，则该路由被标记为无效，若在240秒内还没收到更新，则从将该路由条目从路由表中删除。因此可以通过RIP协议与路由器交互，获取相应路由表信息，分析并从中提取出网络拓扑结构。

该算法的优点是速度快、性能高且发现结构较准确。但对此协议数据单元的解析难度较大，同时要求被检测网络内的路由器都得使用RIP协议。此外，由于RIP最大跳数为15跳，这就决定了它搜索的范围较小，因此这种算法的实用性也变得越来越小。

四、基于OSPF协议的拓扑发现算法

OSPF开放最短路径优先协议，是最为典型的链路状态路由协议，其通用性高，功能强。OSPF作为一种内部网关协议，用于在同一AS自治域系统中的路由器之间交换路由信息。其原理是，运行OSPF协议的每台路由器都知道自己直连的网络，向网络中直连邻居发送Hello数据包，确认邻居是否存在。然后将所创建链路状态数据包LSP泛洪到其所有的邻居，邻居则将收到的LSP存放到数据库中。每台路由器都依据自己数据库中的信息去构建一个完整的最短路径优先树SPF树，并根据SPF算法计算通向所有目的网络的最佳路径，将其添加到路由表中。当网络结构发生变化时，立即发送链路状态通告LSA，运行路由算法，重新计算路由。因此，网络内的每台路由器都拥有一致的网络拓扑结构，所不同的是每个路由器的拓扑结构都是以自己为根节点的树结构。

基于OSPF协议的发现算法就是获取网络内的一台路由器的LSA数据库，并实时获取LSA同步网络拓扑的信息，其优点是效率高、速度快、准确。由于OSPF协议较复杂，实现难度较大，并且要求网络内的路由器都得启用OSPF协议。此外，它采用的SPF算法非常复杂，对硬件设备的要求也较高，计算路由时开销大。

综上所述，当前网络拓扑发现的算法有很多，各有优缺点及适用范围。在实际应用中，可基于上述拓扑发现算法，并结合实际研究、应用的环境，将两种或多种拓扑发现算法融为一体，扬长避短，从而演化出一种更为优化、更为适用的网拓扑发现算法。