拓扑发现算法之议

摘要：作为配置管理的核心和资源管理的基础，完整、精确并且具备可视化友好界面的网络拓扑是检测网络故障、分析网络性能的基础，介绍了网络物理拓扑发现的分类，基于SNMP设备的MIN-II和Bridge-MIB管理信息库，分别设计了网络层拓扑发现算法和数据链路层拓扑发现算法，经测试，算法能够准确的发现网络层设备及连接关系，能够比较准确的对数据链路层进行拓扑发现。

关键词：拓扑发现算法；MIB-II；Bridge-MIB；

随着网络规模的不断扩大和网络拓扑结构的日益复杂，网络管理的地位变得越来越重要，有效、可靠的网络管理已经成为网络系统正常运行的关键。OSI参考模型网络管理标准中定义了网络管理的5大功能，分别是故障管理、配置管理、性能管理、安全管理和计费管理[1]，其中配置管理是进行网络管理的前提，其主要功能是网络拓扑发现和各类设备的配置信息管理。网络拓扑结构是网络中各节点之间互联关系的一种表示，拓扑结构通常被构建成一个图形，对网络拓扑进行发现是对网络管理系统最基本的功能要求，所谓拓扑发现是指通过某种算法探测和识别特定网络中的网络元素和各网络元素之间连接关系，并以字符、图形等方式将拓扑进行显示。作为配置管理的核心和资源管理的基础，完整、精确并且具备可视化友好界面的网络拓扑结构是检测网络故障、分析网络性能的基础[2]。

根据拓扑发现算法涉及的TCP/IP网络层次，一般可以将网络拓扑发现分为网络层和数据链路层拓扑发现两个层次，网络层拓扑发现主要实现网络层路由设备的探测、子网以及连接关系的发现，数据链路层拓扑发现的主要工作是二层设备与主机的探测及其连接关系的确定，好的拓扑发现算法能够快速、准确的发现网络中的三层和二层网络设备，进而确定网络拓扑[3]，利用SNMP网络设备的MIB-II和Bridge-MIB管理信息库，是进行网络物理拓扑发现的常见方法，下边对基于MIB-II和Bridge-MIB的拓扑发现算法进行讨论。

1网络层设备拓扑发现

探测三层（网络层）设备最基本的方法是获取网络中路由设备的路由表（RoutingTable），路由表中记录了目标IP地址（ipRouteDest）的下一条地址（ipRouteNextHop）以及数据的传送方向等信息。支持SNMP的设备会将自己的路由表放在管理信息库（ManagemnetInformationBase，MIB）中，因此，可以通过SNMP获取远端三层设备的路由表。

根据三层网络设备SNMP的特点，设计如下拓扑发现算法：

Foreachrouterinrouter_set

{

ifrouterexsits(interfacetable){next;}

getipRouteTable;

getipAddrTableaddtointerface_table;

ForeachentryinipRouteTable

{

if(ipRouteType=indirect)

{

swapipRoutDestwithitsinterfaceifexsits(nterface_table);

if(ipRouteDestnot_in(router_set)

{

AddRoutertorouterset;

}

Addrouter->ipRouteDesttoedge_set;

}

}}

算法通过遍历和分析三层设备的MIB，确定设备类型和设备间的连接关系，最后确定三层设备网络拓扑结构，使用该算法对某网络中运行拓扑发现，结果如图1所示。

2数据链路层设备拓扑发现

二层（数据链路层）设备的探测是在三层设备探测的基础上增加路由器到交换机、交换机到交换机、交换机到主机之间的连接关系。网络中的交换机同时负责维护自己的生成树状态表（SpanningTreeProtocol，STP）和MAC地址转发表（ForwardData-Base，FDB）,并保存在标准SNMPv2-SMI（StructureofManagementInformation，管理信息结构）中。

二层网络拓扑发现的复杂性在于以太网交换机等设备的透明性。邻居设备交换信息主要通过生成树协议（SpanningTreeProtocol，STP）实现。交换机保留MAC地址和接口状态（网内主机的MAC地址与交换机端口的对应关系）的主要载体是MAC转发表（FDB），FDB可以通过SNMP的Bridge-MIB来访问。可以简单的通过Bridge-MIB计算得出设备之间的物理连接的关系，但由于Bridge-MIB存在时间老化、某些二层设备未配置管理IP导致网管无法访问以及设备学习不全等情况，导致很难通过计算得到一张精确的拓扑结构，这些问题需要采用特有的算法、特定技术来解决[4]。根据数据链路层网络设备MIB-II及Bridge-MIB的特点，基本算法描述如下：

Foreachswitchinswitch_set

{

getdot1dTpFdbTable;

ifipAddisaswitch&isonlyiponthatport

{

drawedgebetweenthem;

}

}

由于二层网络中还存在着哑设备、集线器等不可网管的设备，因此该算法对设备的发现还不够完整，还需使用直接连接定理和间接连接定理进行优化，算法如下：

ForeachSinST

{

Foreach''''x''''inPT(S)

{

ForeachEiinPAT(S,PT)

{

ForeachEkinPAT(S,PT)otherthanEi

{

If(EkdisconnectsSandEi)

{//(S)x-a(Ei)b-y(Ek)

deleteEkfromSandSfromEk;

deletePAT(Ek,y'''')fromPAT(S,x);

deletePAT(s.x'''')fromPAT(Ek,y);

applysameproceduretoallentriesinPAT(Ek,y'''')andPAT(S,x'''');

}

}

}

}}

拓扑发现结果如图2所示。

3结束语

文章对基于SNMP的TCP/IP网络层拓扑发现和数据链路层拓扑发现算法进行研究。根据网络设备MIB-II和Bridge-MIB管理信息库的特点，分别设计了网络层拓扑发现和数据链路层拓扑发现算法。在校园网环境下对算法进行验证，经验证，算法能够准确的发现网络层设备及其之间的连接关系，但是对于数据链路层设备和连接关系的发现还不够准确，这是由于由于二层是设备的Bridge-MIB存在时间老化、哑设备以及设备学习不全等原因导致的，要计算得到精确的拓扑结构，还需要整合多种拓扑发现工具并对算法进行进一步优化[5]，这也是需要进一步研究的方向。