网络拓扑自动搜索算法研究
徐大海 刘新 王奇 白英彩
摘 要 本文利用 MIB-Ⅱ 构造网络拓扑图的方法，对现有的一个搜索算法进行了分析，针对其
不足之处，提出了一个新的算法，将算法复杂度由原来的网络中可访问的路由器数目的 3 次方降为
2 次方, 并指出这是基于 MIB-Ⅱ 的网络拓扑搜索的最低可能阶次。
关键词 网络管理，MIB-Ⅱ，网络拓扑搜索
ALGORITHM OF NETWORK TOPOLOGY SEARCH
Xu Dahai Liu Xin Wang Qi Bai Yingcai
Department of Computer Science & Engineering Shanghai Jiaotong
University， Shanghai 200030
Abstract This paper introduces the method of building network topology with MIB-II and analyzes
an existing algorithm. A new algorithm is then proposed to cover the deficiencies in the algorithm extant.
The new method will reduce the computation complexity from the cubic of the number of available routers
to the square. It is also pointed out that the square is the minimum magnitude possible for algorithms of
MIB-II-based network topology search.
Keywords Network management， MIB-Ⅱ， Network topology search
1 引言
网络管理软件的功能是对网络进行性能监视、故障检测、配置、计费及安全等管理操作，所有
这些操作都需要一个直观、友好的用户界面。所以，在网络管理系统软件中构造网络拓扑图是很有
必要的。网络拓扑图的搜索是大多数网络管理系统的基本功能之一。
TCP/IP 技术是连接异构网络的有效工具，简单网络管理协议 SNMP
［
3
］
具有易于实现的优
点，TCP/IP 的广泛应用促使了 SNMP 成为网络管理的事实协议标准。路由表是网络管理的重要信
息，从路由表中可以得到网络拓扑图的有关信息。MIB-Ⅱ
［
1
］
提供了访问路由表的方法，从而可以利
用 MIB-Ⅱ 实现网络拓扑自动搜索。
2 访问 MIB-Ⅱ 实现网络拓扑搜索
2.1 网络的拓扑结构
图 1 是网络拓扑结构的一个模型。在网络的拓扑结构中，路由器和子网可以认为是图中的节
点。子网节点至少与它的缺省路由器相邻。
如图 1 所示，各子网通过各自的路由器与其他子网通信，这些子网可以是一个局域网，也可以
是某个局域网的一个子网，它们都连接到路由器的一个端口上。路由器的一个端口可以连接一个子
网，也可以同其他路由器相连。当一子网的某一机器向别的子网发送数据时，数据包首先到达本子
网的缺省路由器，缺省路由器检测数据包中的目的地址，根据其路由表确定该目的地址是否在与自
己相连的子网中，如果是，则把数据包直接发往目的地，否则转发给路由表中规定的下一个路由
