基于无向图的网络拓扑生成算法.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是图的联运算示意图.2ag1bag2glvg图2图的联运算示意图b科技论文3.3网络拓扑描述模型网络拓扑描述模型是拓扑生成算法的基础,只有建立了合适的描述模型,才能使拓扑生成算法独立于网络协议,只和描述模型有关.网络拓扑描述模型的作用是:(1)将从各种协议中获取的拓扑信息表示为统一的形式,即拓扑信息的归一化.(2)作为拓扑信息与拓扑生成算法之间的中介.归一化后的拓扑信息作为拓扑生成算法的输入,而不是各种表示形式各异的原始拓扑信息,这样拓扑生成算法就可以独立于网络协议了,从不同的协议中提取的拓扑信息经过描述模型归一化后都可以使用同一个拓扑生成算法生成拓扑图.根据上述图的相关概念,网络拓扑图可以抽象为简单无向图,图的顶点表示网络元素,边表示网络元素之间的连接关系.根据这个模型,网络拓扑图的还原过程可以概括为两个步骤:第一步,把从各种协议中提取的拓扑信息表示为一个个的子图gi,g:,g;第二步,求子图的并图g.g:glug2uug并图g就是整个目标网络的拓扑图.3.4通信子网边界拓扑描述问题及解决方法网络拓扑发现中,一般是利用路由信息来发现路由器子网,利用主动探测获取存活主机地址j.路由信息只是描述用户子网路由而不是主机路由,因此,通信子网的边界拓扑用无向图描述为路由器拓扑子图g,g删中的顶点代表用户子网,而不是主机;主动探测只是获取的存活主机的ii)地址,用无向图描述为主机拓扑子图gh,gh中只有顶点,代表主机.g与gh吲的交集为空,因此gugh是非连通的,如图3所示,b是路由器,a,c,d是用户子网,e,f,g是主机.这就是通信子网边界拓扑描述问题.产生通信子网边界拓扑描述问题的原因是缺少主机与通信子网连接的描述信息.怎样描述主机与通信子网的连接关系呢?实际上,用户子网的网络号与主机地址信息本身已经包含了两者之间的关系:用户子网包含主机,主机只是用户子网内部元素,如图4a所示,通信子网里用户子网节点已经代表了该子网内所有的主机.因此,如果把用户子网与主机的关系描述为子网包含主机,拓扑图中就只有路由器和用户子网,无法把主机单独表示出来了.c一-:1iof-!:l_一go一一jj!gro缸图3通信子网边界拓扑描述问题示意图3电信技术研究2007年第4期如果把用户子网与主机的关系描述为主机通过用户子网连接到路由器,就可以把用户子网看作连接主机和路由器的网络元素了,这样就能在拓扑图中清楚的反映出路由器,子网和主机,如图4b.九用,删包含t帆b,用广予髑与主jlj足财等实体图4用户子网与主机关系示意图在这样的描述方法下,无向图中的顶点有三种类型:路由器,-ti和主机,通信子网边界拓扑描述问题的解决方法如下:首先分别用g吼n和g分别表示路由器子网拓扑和主机,其中gn.中只有顶点没有边.对于每个g中的顶点,在所有g.盯中寻找类型为子网的顶点nefn0,如果ip在子网netno.范围内,求neln0构成的子图和gh吲的联图,用g,替换gh0.即gh.st=gh.sivgnetn.其中gnei=(n01),)这样处理后,与g川.的并图就是连通的了.4网络拓扑图生成模型通过建立网络拓扑图描述模型,网络拓扑发现问题就归结为两个图论相关的简单问题:将拓扑信息表示为无向图;图的并运算.本节结合例子来描述网络拓扑图生成模型.例子中,拓扑发现设备可以获取目标网络中路由器间传输的ospf路由协议报文,利用icmp探测网络内活动的主机ip地址.从ospf报文中可以提取网络中某个路由器和与其直连的路由器之问的关系.advertisingrouter是通告该报文的路由器的fd,下方的2个类型为ptp的链路描述说明该路由器与其他两个路由器直连,这个两个路由器的id就是报文中的ls_id字段,在该报文中的值分别为192.168.11.129和192.168.11.130.图5是一个ospf报文的解析结果.在本算法中有三种网络元素:路由器,主机,子网.其中,路由器的标识是路由器id号,主机的标识是地址,子网标识是子网号.在算法中图g的顶点对应的网络元素标识作为下标,也就是说标识为m的网络元素在图g中对应的顶点为,例如,地4科技论文址为192.168.11.135的主机对应的顶点为l92l68.35,网络号为192.18.0.0的子网对应的顶点为l92l8oo.l1nk一5tateadvert1sementtype:router-lsa(1.).link一一stat星一id三-皇135一一一一一一一一一一一一一一,ladvertisi.router一:.皇一168一,35(192.一168一.ii一.一1曼ilssequencenumber:ox800066dclscheck5um:6ca6length:96田f1aqs:ox02(e)number0flnk5:6田围田田固圈e:stubid:192.168.11.135data:255.255.呈55.一呈主ie:ptpid:192.168.11.129data:192.168.11.2一堕i1505064641type:51:ubid:192.168.11.0dal:a:255.255.255一至2一met盟vpe:ptpid:192.168.11.130data:192.168.11.38m.etr.j.type:stubid:192.168.11.36data:255.255.255.252metrc:type:stubid:_.18.0.0data:255.255.240.0metrc:图5ospf报文解析结果设整个网络的拓扑g,通信子网拓扑gc;通信子网局部拓扑图;主机子图;与g的联图.拓扑生成算法描述如下:第一步,根据路由协议生成通信子网局部拓扑图.在ospf协议中,每个链路状态描述对应的是个局部拓扑,=(e)其中,=口r,l,2,ecsl=mad,rohium,u如rohler|dtllsld2,n如roh_erldu|出lj,n是链路状态描述的个数.第二步,生成通信子网g.第一步中得到的所有通信子网局部拓扑(的并图就是通信子网g,m是局部拓扑的个数.第三步,利用icmp报文探测目标网络地址段内的所有地址,发现活动网络主机,并为每个主机生成一个主机子图(每个子图由一个顶点组成)=(,ehi)其中,=),eh=.第四步,将主机与子网连接起来,生成主机一子网局部拓扑子图.即对于每个主机子图,其中=),=,从中找出顶点子网号,满足ip属-t-u的地址范围,求出主机与其所在子网构成的局部拓扑g5u吖u=u=电信技术研究2007年第4期ghsl=ghlvg=(,巨,).其中,=子网号,=.第五步,生成整个目标网络的拓扑图gg=u(u).i=1g描述了整个目标网络中包含的网络元素,以及网络元素之间的连接关系.整个算法的思想就是从局部到整体.先发现网络元素,生成局部拓扑,找出局部拓扑之间的联系,最后生成整个目标网络的拓扑图.由于使用图的概念作为网络拓扑图的描述模型,可以用相应的图运算来完成网络拓扑图的生成过程,使得网络拓扑图的发现,生成过程层次分明.虽然本例中的拓扑信息是从ospf和icmp协议中提取的,但是文中提出的拓扑图生成算法是与协议无关的,不管拓扑信息从哪些协议中提取,都可以用第3节中的拓扑描述模型进行归一化,然后利用该算法生成目标网络的拓扑图.5总结由于还没有公共的拓扑发现协议,因此,现有的网络拓扑发现方法中,用于拓扑发现的拓扑信息来自多种协议,不同的协议对应的拓扑发现算法不同.本文建立的基于无向图的拓扑描述模型可以将来自不同协议的拓扑信息归一化为统一的表示形式,在此基础上提出的拓扑生成算法独立于协议,实现了各种网络拓扑发现方法的统一描述.参考文献1张先迪,李正岛图论及其应用.北京:高等教育出版社.20042yuribreitbart,minosgarofalakis,benjai,clifrmartin,rajeevrastogiandavisilberschatz.topologydiscoveryinheterogeneousipnetworks:thenetlnventorysystem.ieee/acmtransactionsonnetworking,vol.12,no.3,june200431j.moy,ospfversion2,r