基于协议的网络拓扑发现算法研究

2014-11-10焦彦平李唱陈东宁

科技创新导报 2014年20期

焦彦平++李唱++陈东宁

摘要：随着网络的不断发展，其拓扑结构变得越来越复杂，其获取也变得越来越困难，该文介绍分析了网络拓扑技术的发展现状，分析了现有网络拓扑技术的不足，并且提出了基于STP、SNMP和ICMP三种常见协议的网络拓扑发现算法。

关键词：网络拓扑发现 STP SNMP ICMP

中图分类号：TP393 文献标识码：A 文章编号：1674-098X（2014）07（b）-0046-05

随着网络的不断发展与普及，网络的规模变得越来越大，网络的结构变得越来越复杂，对网络进行有效的管理和控制是保证网络处在正常高效运转的关键。但对网络进行有效的管理首先要获得网络的拓扑结构，而网络的结构复杂、节点数目繁多，靠人工统计往往是行不通的，而目前的网络拓扑发现技术又存在着一定的不足，所以研究更加有效的手段来得到网络的拓扑结构具有重大的意义。

1 网络拓扑发现算法研究

在网络拓扑发现技术方面，美国康奈尔大学的CNRG网络研究组、CAIDA组织的Skitter [1]和贝尔实验室在这方面都有了深入的研究，他们设计的算法及其技术都已经具有较好的应用，并且已经进行了商用。

在物理网络拓扑发现算法中，由于交换机转发数据具有透明性的特点，这就给物理层的拓扑结构发现带来了很大的困难。针对物理网络中的拓扑发现问题，中科院计算所的郑海提出了能依赖不完整的交换机AFT来发现物理网络拓扑的算法[2]，随后他们在此基础上进一步解决了子网中存在Hub的判定情况[3]，但存在的不足在于它们都不能准确判定链路是否为冗余链路。文献[4]和[5]给出了基于端口流量的拓扑发现算法，通过对端口流量数据的分析进而实现了网络拓扑发现，但是该方法的实际数据无法准确获得，并且获得的数据可能存在很大的误差，不具有实际的应用性。文献[6]和[7]中利用交换机地址转发表的数据构建了网络的拓扑结构，是一种数据链路层的拓扑结构发现方法，但是这种方法无法对哑交换机（不能通过SNMP协议访问的交换机）进行有效的发现。文献[8]和[9]同样给出了一种基于生成树协议（Spanning Tree Protocol，STP）的数据链路层网络拓扑发现算法，这种算法具有分析得到哑交换机的连接关系的能力，但是其缺点是无法发现交换机与主机的关系，并且要求交换机支持STP协议才能有效。

IETF于2000年推出物理拓扑MIB （Management Information Base）[10]，它IP网络的相关对象如图1所示。IETF试图去解决网络拓扑结构发现的问题，但是IETF并没有具体给出如何获取MIB的具体方法，只能通过一些通用的协议来获取MIB。

2 基于STP协议的网络拓扑发现算法

生成树协议（Spanning Tree Protocol，STP）的主要功能有两个：一是创建以某台交换机为跟的网络拓扑生成树，同时能够避免环路的产生。二是在网络拓扑发生改变时，能够达到收敛保护的目的。算法能够实现的基础在于网络中每台交换机都在Bridge MIB中保存了其交换域生成树的一部分，利用SNMP协议来获取MIB中的这些信息，再根据STP协议的特征，通过比较就可以得到整个网络拓扑结构。根据STP协议我们可以推导出以下八条结论[11-12]，这几条结论可以帮助我们判断各个端口的关系。

结论一：设交换机的根接口指定网桥为，指定接口为，由于能运行生成树协议的必须是交换机，所以必为交换机，且、通过接口、直连或通过集线器互连（设备级直连）。

结论二：处于转发状态的接口为所在网段内的其他网桥传播信息，所以必须存在连接。若无连接，它不会参与生成树算法，也就不可能有转发状态。

结论三：阻塞接口若无连接存在，则生成树协议不会令其阻塞，它一定是进行冗余备份的线路。所以若阻塞接口的指定网桥非本交换机，其上一定有连接存在。

结论四：对于设备级直连交换机、的两接口、，若，则、通过集线器连接，反之，接口、直连。其中表示交换机通过接口收到数据包的源MAC地址集，表示交换机通过接口收到数据包的源MAC地址集。

结论五：假设交换机接口的地址转发表中仅包含主机设备，若主机数目为1，则该接口与主机直连；若主机数目大于l，则该接口通过集线器连接主机群。

结论六：若交换机接口的地址转发表中无其他交换机的地址信息但包含路由器地址，则该接口与路由器直连。若交换机接口的地址转发表中无其他交换机和路由器的地址信息，则它与转发表中的主机设各级直连，通过结论五进行连接确认。

结论七：若的非根端口的指派网桥为（），且端口的状态是阻塞的，且的非根端口的指派端口与的指派端口相等，那么与直连，且该链路是备份链路。

结论八：满足规则1的2个端口与，不妨假定是根端口，是非根端口，若存在其他端口（）与满足规则1，那么、与之间必定存在集线器或哑交换机等不支持SNMP 的设备。

利用上述的八条结论，可以得出基于STP协议的拓扑发现算法：根据结论一，当发现未知的网桥时，它一定是哑交换机。以根交换机为源地址Ping哑交换机，利用结论二查找拓扑结构生成树的内容，如果其中包含哑交换机的MAC地址，则认为它们之间存在直接相连的关系。其中伪造根交换机为源地址的Ping数据包是为了满足生成树转发下行接口的完备性。STP发现算法利用网络OSI第二层连接信息生成网络拓扑图，按广度优先遍历、先主干后备份的顺序进行，算法流程如图2所示。

详细描述如下：

（1）对网络中所有的设备进行访问，对交换机进行识别并且存入临时链表A中。

（2）将链表A中的所有交换机IP逐个取出来，并通过SNMP协议访问同时记录根网桥MAC地址、本机的根接口、处于转发和阻塞接口的指定网桥MAC及其指定接口。endprint

（3）对网络拓扑生成树进行广度优先遍历。根据STP协议可以得到交换区域的根网桥，而后将根网桥加入到FIFO（先进先出队列）的等待进一步检测的队列B中。

（4）从队列B中取出一个交换机放入链表C中。在临时链表A中找出根接口的指定交换机为的交换机信息逐一添入待检测队列B中。由结论一、三可知它们属于设备级直连，并从临时链表A中去除该交换机信息。

（5）重复4，直到队列B为空。

（6）判断添加交换机连接：查询链表C中每个交换机接口的指定网桥和指定接口，若存在相同的交换机，则说明它们与指定的网桥是相互连接的，但它们是通过集线器等连接设备相连的，否则为设备直连，修改指定网桥的指定接口类型。

（7）若在临时链表A中仍不为空，则说明存在网络中存在哑交换机，如果临时链表A为空，则跳转至10。

（8）在临时链表A中对每个交换机根接口的指定网桥进行查询，若该网桥不存在于临时链表A中，根据结论一，将该网桥加入待检测队列B中。并重复进行4、5、6步骤。

（9）处理哑交换机连接：在链表C中逆序查找除哑交换机自身所在分枝以外其他分枝的交换机接口转发状态，若其状态转发无连接并且其转发地址中包含该哑交换机的MAC地址，则对该接口与哑交换机之间的连接信息进行添加。

（10）处理冗余连接：判断每个交换机的阻塞接口查询它的指定网桥，将连接填入对应的接口信息区。

（11）向全网主机发送广播Ping包，对于处在设备直连状态的两台交换机，对直连两接口的地址转发表进行访问，并且根据结论四改写其接口信息。

（12）根据结论六对主机之间的连接和路由器之间连接进行添加。

STP拓扑发现算法具有以下四个方面的优点：

（1）能够对哑设备存在的情况进行处理。

在STP发现算法中，根据结论六利用交换机接口的指定网桥来发现哑交换机，并且利用了结论一和结论四处理接口连接集线器的情况。

（2）能够发现并对冗余连接进行处理。

在生成树算法中，它以阻塞某些接口来实现无环路转发。在STP发现算法中，通过查找比较接口状态，将那些处于阻塞状态的接口取出，为其与指定网桥添加连接，便能发现冗余连接。

（3）能够对网络拓扑结构的变化进行及时反映。

在运行STP协议的网络中，如果网络物理拓扑发生变化，算法会立即被触发，进而对整个网络的拓扑结构进行重新的绘制，所以在STP发现算法得出的物理拓扑始终是最新最完整的。但在其他算法中，对网络拓扑结构的绘制必须通过报文之间的交流来进行，如果存在两台或者几台设备由于某种原因很久没有发生通信，则会导致此设备不会被发现，网络拓扑结构绘制不完整。

（4）能够对多个子网的复杂环境网络拓扑结构进行有效的发现。

不同子网间的交换机即使直接相连，它们也是通过各自的网关交换信息，但它们必定都遵循生成STP协议以构造无环路交换域，所以利用STP发现算法可以发现这些相对比较复杂连接。

3 基于ICMP协议的网络拓扑发现算法

在ICMP协议中有Ping命令和Traceroute命令，这两种命令可以帮助我们获得网络的拓扑结构。

Ping命令往往用来检测一个节点是不是处在运行的状态或者是检测两个节点之间的时延（RTT）。Ping向所要检测的目的地址发送ICMP echo请求包，等待接收ICMP echo响应包，按照成功的次数及一些其他数据对网络的时延等一些性能进行评估。一般情况下Ping只关心网络上的源节点和目的节点，而不考虑网络的其他细节，同时也可以利用Ping的广播得到整个网络的主机状态。在文献[13]中给出了Ping的三类规则，利用这三类规则可以对某个IP地址所归属的网络或者是IP的有效性进行判断，具体如下：

（1）通过Ping的广播来判定IP地址所属子网。

递减猜测子网掩码的长度，对每个猜测的子网掩码构造广播地址，进行Ping操作，如果主机对构造的广播地址有回应则说明猜测的子网掩码是正确。给定一个IP地址，可利用本规则猜测该地址所属的子网掩码：

for（masklen=31； i> 7 ； i--） {

假定子网掩码的长度是masklen；

为IP地址和masklen构造主机号为全0和全1的直接广播地址；

ping这些广播地址；

如果多于两个主机对这两个ping都做出了响应，则返回masklen，否则继续；

}

（2）通过一组地址来判定该组地址所属子网。

已知地址集A中的IP地址同属于一个子网，对地址集A进行异或操作，找出第一个不为0的位，则该位及其后的各位都只能是主机号，而不可能是子网号。从而判断出子网掩码的长度（可能比实际子网掩码的位数长），而子网地址则可通过猜测得到的子网掩码做按位与运算得出。求取子网掩码的伪代码如下：

（3）判定在某个域中的有效IP地址。

已知一个子网空间的地址集B，推测已知的子网地址空间中有效的IP地址，其算法描述如下：

for（每个ping测试成功的地址）{

把此地址的后续N个地址加入到临时集合中；

if（地址以1，63，129或者193结尾） {

可能有其他的主机在这个空间中，把N个具有相同前缀的随机地址加入到临时集合中；

Traceroute命令可以发现源节点和目的节点之间的路由器。其原理是通过Traceroute命令向目的节点发送端口为65535的UDP报文，它们之间的路由器在转发该数据包之间会将其TTL值减1，如果当TTL值变为了0，则该路由器向源节点发送TTL-Expired ICMP的消息。Traceroute命令就是通过这个特性，将发送包的TTL值不断的增大，这样会使源节点到目的节点间这条路经上所有的路由器均会向源节点发送TTL-Expired ICMP包，这样就将此路径上的所有路由器进行发现。如图3所示，对一个目标设备发送的第一个数据包中TTL值为1，所以此报文在遇到两个节点之间第一个路由器R1时，就会向源节点发送TTL-Expired ICMP包，这样路由器R1就被发现了，R1就成了网络拓扑结构中的一部分。之后就将发送报文的TTL值不断增加1，一直加到发送的报文被目的节点所接收，就可以得到之间所有路由器节点。endprint

通过上述方式我们可以构造出包含节点R1，R2，R3，…，Rn和连接关系（源主机，R1），（R1，R2），（R2，R3），…，（Rn，目标设备）拓扑结构来。由于基本所有的路由器都会向源节点发送TTL-Expired ICMP消息，所以一般情况下，通过Traceroute命令得出来的网络拓扑结构是比较准确的。

通过ICMP中的Ping和Traceroute命令的特性可以实现对网络拓扑结构的发现。

算法的主要步骤如下：

（1）首先在域内随机选取形式为（* .1）的地址同时将它们存在临时地址集A。

（2）然后每次从A中取出一个IP地址a通过步骤3进行判定，直到地址集A中没有IP地址可以取，绘制网络拓扑图。

（3）首先利用Ping命令判断该地址是否为有效地址，如果有效则将该地址存入地址集B中并且根据规则3将更多的地址加入地址集A中。而后有效地址a进一步执行Traceroute命令，会得到与其相连接的所有路由器的信息，然后利用规则2猜测地址a所属的子网地址。

算法流程如图4所示。

4 基于SNMP协议的网络拓扑发现算法

在一般的基于SNMP协议的拓扑发现方法中，网络中的每个设备都有路由表，路由表中的信息包含了网络拓扑结构的信息，路由表包括路由目的网络地址、网络的子网掩码、该路由的下一站IP地址、对应的端口索引和路由协议类型等信息。由于路由表中下一跳的节点一定是具有路由功能的节点，所以就可以在设定路由器开始，依次读取每台路由器的路由表，这样就可以逐个发现每台具有路由功能的节点，进而得出具有路由功能节点的拓扑结构。再根据路由表的本地接口的索引标识项，找到接口表中所对应的本地接口索引，由接口表的接口类型就可以判断其所在子网的类型，最终构建出整个网络的拓扑结构图。这种方法的拓扑发现过程和算法的优点在于其过程简单，运行速度快，发现效率高，对资源消耗比较小，因此，得到了大家的广泛应用。但是，该方法的不足也很明显，主要表现在以下五个方面：

（1）由于只是根据IP地址来发现设备，这样就无法发现网络中没有配置IP的网络设备。

（2）由于目前一个路由器往往具有不止一个IP地址，而此基于路由表的发现方法算法实际上就是基于IP地址的，所以一个具有多个IP地址的路由器会导致一台设备被算法当成了多台设备，与实际情况不符合。

（3）因为要对网络中所有设备进行检测，在网络规模比较大时可能导致算法执行时间较长，同时由于实际网络中情况比较复杂，存在网络时延等情况，可能导致发现的网络拓扑结构不准确。

（4）在路由表中本身存在大量的冗余信息，可能导致网络拓扑结构的不准确。

（5）根据该算法进行拓扑发现需要网络中所有的设备都支持SNMP协议。

因此，该方法一般用于骨干网络拓扑结构的发现，主要对网络的路由节点进行发现，对网络的整体情况进行绘制。可见，无论是基于STP的拓扑发现算法还是本节的拓扑发现算法都各有优缺点和局限性，在实际的应用中要根据具体的情况发挥出算法的功能。

本节在现有基于SNMP算法的基础上研究了一种基于SNMP的网络拓扑发现改进算法，经过实际网络管理系统的验证，能够有效发现管控网络的三级拓扑结构，即：骨干网路由、二级子网和三级子网拓扑结构。

这种算法的基本思想是在网络中路由器之间的链路是由其两端路由器的端口互联构成的，根据TCP/IP的编址原理，链路两端路由器端口的IP地址必然处于同一个子网中。因此，通过一个子网中已知的IP地址和这个IP地址的子网掩码即可计算出该子网中所有其他的IP地址。根据这种思路，从某个节点开始，访问其MIB库，得到该节点所有接口的IP地址和子网掩码，该节点称为种子节点。通过计算得到与每一接口在同一个子网内的其他IP地址。判断这些IP地址是否属于路由器信息，如果是则将此路由器信息记录到待检测路由设备链表，作为下一层发现的种子节点。并同时记录两个路由器问的链路信息到拓扑信息链表。重复以上步骤直到没有种子节点或者达到指定的发现层数，即可完成相应的拓扑发现过程。算法流程如图5所示。

详细描述如下：

（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，Z）无重复地放入R-1inks-S队列（路由器接口与子网相连的接配对的二元组）。

（4）判断路由器之间的连接关系：如果ipRouteType为4，下一跳ipNextHopIpAddress地址有效，表明另一个路由器与Rx直接相连。根据ipNextHopIpAddress地址信息访问另一个路由器的ipAddressTable，判断AllRouters队列中是否己经存在该路由器信息，如不存在则把该路由器编号加入队列AllRouters和AccessRouters中。很容易确定Rx的Y端口与另一个路由器Ru的V端口直接连接。因此把元素（Rx，Y，Ru，V）无重复地放入队列R-links-R（路由器接口与路由器接口相连的二元组）中。endprint

（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的信息表示路由器与子网、路由器与路由器之间连接关系，最终可以准确而完整地把拓扑结构绘制出来。

5 结语

该文分析了网络拓扑技术的重要性，介绍了现有各类网络拓扑发现算法，并重点针对其不足进行了分析，根据现有网络拓扑发现算法的不足，根据实际，选取STP、SNMP和ICMP三个常用协议做为基础，提出了基于这三种常见协议的网络拓扑发现算法，同时提出了一种基于SNMP协议的拓扑发现改进算法，更好的解决了网络拓扑发现比较难以有效解决的问题。

参考文献

[1] K.C.Claffy D.McRobb.Measurement and Visualization of Internet Connectivity and Performance[EB/OL]. http：//www.caida.org/Tools/Skitter， 2001.

[2] 郑海，张国清.物理网络拓扑发现算法的研究[J].计算机研究与发展，2002， 39（3）：264-268.

[3] 张国强，张国清，李仰耀.物理网络拓扑发现算法的研究和系统实现[J].小型微型计算机系统，2006，27（1）：12-16.

[4] 邱林，张建忠，吴功宜.基于端口流量的物理网络拓扑发现方法研究[J].计算机工程与应用，2002，38（22）：171-172.

[5] 陈艳秋，宋银濒，刁成嘉.利用端口流量分析解决物理网络拓扑发现问题[J].计算机工程与应用，2007，43（5）：150-152.

[6] Gobjuka.H， Breitbart.Y.Ethernet Topology Discovery for Networks with Incomplete Information[J]. IEEE INFOCOM，2007（8）：631-638.

[7] Uzair.U，Ahmad.HF，AIi.A，Suguri.H.An Efficient Algorithm for Ethernet Topology Discovery inLarge Multi-subnet Networks[J]. IEEE INFOCOM， 2007（4）：1-7.

[8] Farkas J，de Oliveira V.G， Salvador M.R， dos Santos G.C. Automatic Discovery of Physical Topology in Ethernet Networks [J].IEEE INFOCOM，2008，3：848-854.

[9] 曲朝阳，胡绪超.基于SNMP的网络拓扑发现与拓扑生成树的绘制[J].网络安全技术与应用，2007（3）：23-27.

[10] J Case，M Fedor，M Schoffstall.Simple Network Management Protocal [S].RFC1157，1999.

[11] 石玫.网络拓扑自主发现[D].中国人民解放军信息工程大学，2007.

[12] 张占国，刘淑芬，包铁，等.基于STP协议的物理网络拓扑发现算法[J].计算机工程，2008，34（6）：98-100.

[13] 王婕，欧阳松.网络拓扑自动发现算法的研究[J].计算机测量与控制，2005， 13（9）：978-980.endprint