《一种基于图的网络拓扑概率故障定位方法.doc》由会员分享，可在线阅读，更多相关《一种基于图的网络拓扑概率故障定位方法.doc（5页珍藏版）》请在三一文库上搜索。
1、一种基于图的网络拓扑概率故障定位方法中图法分类号：TP393文献标识码：A 作为网络管理的重要组成部分，拓扑管理可以反映网络设备的配置、布局和节点状态。网络主机或数据链路的失效会导致网络拓扑故障，但由于网络庞大，故障源的具体位置很难确定，因此准确地进行拓扑故障定位是拓扑管理的关键。通过拓扑故障定位，能够及时发现失效的主机或链路，提高网络性能、增强网络可靠性。 实现拓扑故障定位的基础是拓扑发现，本文在研究IP网络拓扑发现的基础上，使用基于无向图的方法对网络拓扑故障定位进行了研究。 1拓扑发现方法研究 实现IP网络的拓扑管理，也就是对IP网络进行拓扑发现与监控。IP网络拓扑发现有以下常用的方法1：
2、利用SNMP获取MIB中的拓扑信息；利用ICMP Ping/Ping Broadcast命令判断目的设备的存在性；利用ICMP Traceroute命令获得路由器间的连接关系；利用DNS命令发现域内主机和路由器的相关拓扑信息；利用ARP获取同一以太网网段内所有活动主机的拓扑信息；利用BGP，OSPF，RIP等路由协议获取路由信息，从而快速获得路由器间的连接关系以及子网拓扑信息。 使用ICMP Echo/Reply能够迅速发现网络中的IP节点，简单有效且具有通用性。SNMP功能强大、发现速度快，目前主要的网络设备都支持SNMP。SNMP的标准MIB II(RFC 1213)中包含了对管理网络非常
3、有用的信息，具有通用性。因此本文采用ICMP与SNMP相结合的方法来实现IP网络拓扑发现，具有快速、通用的优点，能满足网管系统的实时性要求。其具体方法是：使用SNMP获取MIB中与拓扑发现相关的关键信息，据此构造出网络主拓扑，再使用ICMP发现子网中的终端设备，实现子拓扑的构建，从而完成整个IP网络的拓扑发现。 在标准MIB II(RFC 1213)中，与拓扑发现相关的关键信息主要包括sys组、if组和ip组变量2。本文主要用到if组和ip组。根据ip组中的iPForwarding变量可判断该设备是否为路由器；根据if组的设备网络接口表可判断此接口所连接的子网类型；根据ip组的IP地址表可判断
4、与路由器相连的子网地址；根据ip组的IP路由表可找到与该路由器非直接连接的下一跳路由器IP地址。 拓扑发现算法的流程如下： (1)从被管IP地址段中取出一个IP地址，使用SNMP获取其iPForwarding值，如果为1，则设备具有前向转发IP数据包的功能，为路由器。如果找到了一个路由器，转步骤(2)；如果不存在路由器，则算法结束。 (2)使用SNMP查询该路由器IP地址表(iPAddrTable)，取得表中所有IP地址(ipAdEntAddr)和相应的子网掩码(iPAdEntNetMask)。将ipAdEntAddr和相应的iPAdEntNetMask进行与操作，确定该路由器所连接的所有子网
5、地址，如果子网都不在管理范围内，算法结束；否则，从接口表(ifTable)获得变量ifType，确定子网的网络类型。 (3)获得子网信息后，查询该路由器路由表(ipRouteTable)，获得非直接连接路由器的下一跳IP地址(ipRouteNextHop)，即路由类型(ipRouteType)的值为4(indirect)。如果无这样的路由器，算法结束；否则，转步骤(2)。针对上述算法所确定的所有子网，使用ICMP发现网内的所有活动IP节点。在此基础上对该拓扑进行周期监控，发现网络拓扑变化和不可达情况，但不能确定故障的具体位置。因此拓扑故障定位是下一步需要研究的问题。 2拓扑故障定位方法研究 通
6、信网络中故障定位的技术很多，包括专家系统、依赖图、码书、信任网络、因果关系图或根据实际情况建模4,5。根据定位方式，故障定位技术又可以分为被动方式6和主动探测方式7,8。本文使用图论模型进行网络建模，并在此基础上进行了故障定位研究。 在网络拓扑稳定的情况下，当某台主机或者路由器(以下简称为主机)出现了不可达的情况(假设网络中路由算法在网络连通情况下都能够发现正确路由)，可能是主机出现了故障或与该主机相连的所有链路出现了故障。区分这两种情况，准确地进行拓扑故障定位是一个重要难题，为解决该问题，本文使用了基于无向图的概率方法进行网络拓扑故障的定位。 21网络与无向图 在网络研究中可以将网络抽象为无
7、向图，简称图3。一个图G定义为一个有序对(V，E)，记为G=(V，E)。其中：V是一个非空集合，称为顶点集或者点集，其元素称为顶点或者点，用n表示顶点数；E是由V中的点组成的无序点对构成的可重集合（同一点对在E中可出现多次），称为边集，其元素称为边，用m表示边数。边记为uv，也可记为e，即e=uv，并称u(或v)与e关联；连接两个相同顶点边的条数称为边的重数，重数大于1的边称为重边；顶点重合为一点的边称为环；没有环也无重边的图称为简单图。 假设网络中主机、链路的故障发生相互独立，并且同一个设备的故障发生情况也是独立的，主机、链路的故障时间间隔概率分布是已知的。图1中，以Fvi表示网络中顶点vi的故障时间间隔分布函数，以Fej表示网络中边ej的故障时间间隔分布函数。在下面的讨论中，t表示当前时刻，tvi与tej表示vi与ej上次发生故障的时刻。 22基于无向图的概率故障定位 下面对网络中的各种不可达情况进行分析，并在此基础上进行概率故障定位。 23故障定位的实例分析 下面以图1为例，说明故障模型的化简方法。 3结束语 本文在IP网络拓扑发现的基础上研究了一种基于无向图的网络拓扑概率故障定位方法，该拓扑故障定位方法已在实际的IP城域网中得到使用，能够有效地排除网络故障，提高了网络性能。