基于无向图的网络拓扑生成算法.doc

基于无向图的网络拓扑生成算法 科技论文 基于无向图的网络拓扑生成算法 汪德文陈健 摘要:网络拓扑图在网络管理中起着非常重要的作用,但是目前还没有任何公共协 议用于网络拓扑发现,因此,用于拓扑发现的拓扑信息一般都来源于多种协议本 文建立了基于无向图的网络拓扑描述模型,用来描述形式各异的拓扑信息,并提出 了基于该模型的拓扑生成算法,该算法与网络协议无关,适用性强. 关键词:网络拓扑拓扑发现拓扑描述模型协议无关的拓扑生成算法无向图 1引言 拓扑管理是网络管理的重要组成部分,是配置管理的核心和故障管理的基础.拓扑 发现是指利用网管协议或工具搜集分布在网络各处的原始拓扑数据,通过拓扑生成算法 综合出完整的拓扑信息.网络拓扑发现包括两方面的内容:拓扑信息收集和拓扑图的生 成. 由于目前还没有任何公共协议可用于拓扑发现,加上网络和网管协议种类众多,因 此,现有的网络拓扑发现方法中的拓扑信息来源于多种协议.怎样用统一的模型来描述 这些拓扑信息,从而用统一的算法来描述现有的拓扑发现方法值得研究. 本文在充分总结分析网络拓扑发现方法特点的基础上,归纳其共性,抽象出了网络 拓扑描述模型和协议无关的网络拓扑图生成算法. 2基本思想 本算法的基本思想是由局部拓扑生成整个目标网络的拓扑结构.网络拓扑信息是从 网络线路上的多种协议中收集来的,从某一种协议中提取出来的拓扑信息只是目标网络 中某一片的局部拓扑,如两个或多个路由器的连接.这些局部拓扑是用来还原整个目标 网络拓扑结构的原材料,我们要像拼图一样把这些原材料拼接起来.不同的协议中 包含的拓扑信息在表示形式上有很大差异,因此,在拼接之前,要把零散的,形式各异 的局部拓扑信息归一化为统一的表示形式.这就需要为网络拓扑结构的描述建立一个模 型,在该模型的基础上实现网络拓扑图的拼接,拼接的过程就是网络拓扑图的生成过程. 从上面的叙述中可以看出,算法的核心是网络拓扑描述模型和网络拓扑图生成算法. 3网络拓扑结构描述模型 3.1模型选择要求 建立网络拓扑描述模型的目的是用来表示从各种协议中获取的各种拓扑信息,将异 构的拓扑信息归一化. 既然是要用局部拓扑拼接整个目标网络的拓扑结构,那么局部拓扑和整个网络拓 扑就应该用一个同构的模型来表示,整个网络拓扑表现为局部拓扑的和.无向图具备 电信技术研究2007年第4期 这样的特点,因此,用无向图来描述网络拓扑是合适的. 首先,网络拓扑图描述的是网络元素以及网络元素之间的关系,图是某类具体事物 和这些事物之间的联系的抽象,因此,图可以描述网络元素之间的各种关系. 其次,图是一个抽象的模型,与协议无关,可以描述从各种协议中提取的网络拓扑 信息. 最后,各种零散的局部拓扑信息都可以用图来描述,将局部拓扑图拼接为整个目标 网络拓扑图的过程实际上就是图的并,联运算.因此,图的运算可以实现网络拓扑图的 拼接. 3.2相关定义 先给出图及相关概念的定义u. 定义1:一个图G定义为一个有序对(V,E),记为G(V,E),其中 (1)v是一个非空集合,称为顶点集,其元素称为顶点或点,IVI表示顶点数. (2)E是由V中的点组成的无序点构成的集合,成为边集,其元素称为边,且同 一 点对在E中可能出现多次. 图G的顶点集也记为V(G),边集记为E(G).顶点集和边集都有限的图称为有限图, 即没有重边也没有环的图称为简单图.图G的顶点数和边数分别用符号n(G)和m(G)表 示. 定义2:设G『,是G的子图,Gl和G,的并运算是G的一个子图,其顶点集为 v(G1)UV(G,),其边集为E(G)UE(G,).图I是图的并运算示意图. G1G2GlUG2 图1图的并运算示意图 定义3:在不相交的G1和G2的并图quG2中,把的每个顶点和的每个顶点连 接起来所得到的图称为Gl和G2的联图,记为VG2.图2是图的联运算示意图. 2 a ● G1 b ● a G2GlVG 图2图的联运算示意图 b 科技论文 3.3网络拓扑描述模型 网络拓扑描述模型是拓扑生成算法的基础,只有建立了合适的描述模型,才能使拓 扑生成算法独立于网络协议,只和描述模型有关.网络拓扑描述模型的作用是: (1)将从各种协议中获取的拓扑信息表示为统一的形式,即拓扑信息的归一化. (2)作为拓扑信息与拓扑生成算法之间的中介.归一化后的拓扑信息作为拓扑生成 算法的输入,而不是各种表示形式各异的原始拓扑信息,这样拓扑生成算法就可以独立 于网络协议了,从不同的协议中提取的拓扑信息经过描述模型归一化后都可以使用同一 个拓扑生成算法生成拓扑图. 根据上述图的相关概念,网络拓扑图可以抽象为简单无向图,图的顶点表示网络元 素,边表示网络元素之间的连接关系.根据这个模型,网络拓扑图的还原过程可以概括 为两个步骤: 第一步,把从各种协议中提取的拓扑信息表示