基于OSPF协议的网络拓扑发现算法

《基于OSPF协议的网络拓扑发现算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

15502011，Vo1．32，No．5计算机工程与设计ComputerEngineeringandDesign基于OSPF协议的网络拓扑发现算法潘楠，王勇，陶晓玲(1．桂林电子科技大学计算机与控制学院，广西桂林541004；2．桂林电子科技大学网络中心，广西桂林541004)摘要：基于SNMP和ICMP的网络拓扑发现算法采用主动探测手段，在获取拓扑信息时会注入额外的网络流量，易造成实时性较差、网络性能受影响等问题，因此，提出了一种基于OSPF协议的网络拓扑发现算法。该算法采用被动监测方式，通过Jpcap捕获OSPF协议中的链路状态更新报文，分析其中的Ro~erLSA和NetworkLSA，获得路由器之间的链路类型等网络拓扑信息，进而在不影响网络性能的前提下发现拓扑结构。实验结果表明，该算法能够快速准确地获得完整的网络拓扑结构。关键词：OSPF协议；网络拓扑；链路状态更新报文；RouterLsA；NetworkLSA中图法分类号：TP393文献标识码：A文章编号：1000—7024(2011)05—1550—04NetworktopologydiscoveryalgorithmbasedonOSPFPANNanWANGYong，TAOXiao1ing(1．CollegeofComputerandControl，GuilinUniversityofElectronicTechnology,Guilin541004，China；2．NetworkCenter，GuilinUniversityofElectronicTechnology,Guilin541004，China)Abstract：AimedattheshortagesofexistingnetworktopologydiscoverymethodsbasedonSNMPandICMPwhichareactivedetectionmethodsandtheextranetworktraficwillbeinjectedwhenobtainingthetopologyinformation．easilyleadtopoorreal—timeandincreasingthenetworkload，adiscoveryalgorithmfornetworktopologybasedonOSPFisproposed．Thealgorithmappliesthewayofpassivemonitoringtoobtainthelinkstateupdate(LSU)packetofOSPFprotocolthroughJpcap，andanalyzesthetopologyinformationwhichcanobtainthelinktypebetweenrouterscontainedintheRouterLSAandNetworkLSA．Experimentalresultillustratesthattheproposedalgorithmcanquicklyandaccuratelyobtaincompletenetworktopology．Keywords：OSPFprotocol；networktopology；linkstateupdatepacket；RouterLSA；NetworkLSA071言了仿真实验，并给出了实验结果。1网络拓扑发现算法由于网络中新技术和新设备的广泛使用，网络规模扩大以及结构复杂化，对网络管理的要求越来越高。如何有效地传统的网络拓扑发现方法大多是利用SNMP和ICMP协管理网络资源，实现优化网络、发现网络瓶颈，已日益成为网议的[I-2]这两种方法都采用主动探测手段获取用于构造网络络管理研究的热点。在网络管理的5大功能域中，配置管理拓扑的信息，会影响网络性能。此外，还有广泛应用于局域网是基础，其主要功能包括发现网络的拓扑结构、监视和管理网拓扑发现的基于ARP协议的方法：络设备的配置情况。其中，发现网络的拓扑结构是实现其它(1)基于SNMP协议的拓扑发现方法各项功能的基础。利用SNMP协议构建网络拓扑是目前比较常见的一种方网络拓扑发现是获取和维护网络节点的存在信息和它们法。通过对被管理设备的MIB库进行操作，提取出可利用的之间的连接关系信息，并在此基础上绘制出整个网络的拓扑信息构建拓扑。该方法发现效率较高，易于实现，但由于这种图。由于网络具有动态特性，并且技术发展更新较快，因此，方法需要遍历网络中所有路由器的路由表，对网络注入了额有关网络拓扑自动发现的相关研究层出不穷。外的流量，且实时性不好。本文提出一种基于OSPF协议的拓扑发现算法。该算法(2)基于ICMP协议的拓扑发现方法采用OSPF协议中的链路状态更新报文(1inkstateupdate，LSU)，利用ping／traceroute探测包可进行一定的拓扑发现。该方根据其中包含的拓扑信息，对网络进行拓扑发现。最后进行法易于实现，使用范围广，但网络负载较大，不能得到网络设收稿日期：2010—05—17；修订日期：2010—11-24。基金项目：国家自然科学基金项目(60872022)；广西研究生创新基金项目(2叭叭O59508l2M21)。作者简介：潘楠(1985一)，男，河南平顶山人，硕士研究生，研究方向为网络安全；王勇(1964一)，男，四川阆中人，博士，教授，研究方向为计算机网络；陶晓玲(1977一)，女，浙江金华人，硕士，工程师，研究方向为计算机网络。E-mail：pn8527@yahoo．tom．ca 潘楠，王勇，陶晓玲：基于OSPF协议的网络拓扑发现算法2011，Vo1．32，No．51551备之间的连接关系，若要构建完整的拓扑结构，还需与其它信息配合。(3)基于ARP协议的拓扑发现方法在局域网中运行的任何IP网络设备都支持地址解析协议(ARP)，并在本机维护着一张ARP表，实现IP地址与MAC地址间的地址解析。由于ARP表中的网络设备地址都是最近活动过的有效IP，因此采用此方法的发现效率很高。但对于大型网络，ARP表中的记录可能无法包括网络中实际存在的所有网络设备，因此该方法较适合发现局域网内的设备。(4)基于OSPF协议的拓扑发现方法OSPF协议是一种链路状态协议，目前应用较为广泛。该方法通过利用路由器自身互相交互，获得路由拓扑信息，构建图1OSPF网络模型网络拓扑。采用基于OSPF协议对网络进行拓扑发现的方法是全被动的，不增加网络负载，对网络行为没有影响，且实时性较好。VersionI4Packetlength目前，基于OSPF协议的网络拓扑发现算法在国内外得到RouterID了广泛的研究。在国外，AT&T实验室的AmanShaikh等人AreaIDChecksumAuType提出基于OSPF协议，在网络中部署监测点，被动接受LSA并Authen利用LSA构建网络拓扑；国内学者在这方面也有一些研究，文Authentcation献【5]采用OSPF协议，设计并实现了一个网络拓扑发现与显NumberofLSASLSA示系统，该系统能够快速的发现广域网且显示效果好；国防科技大学的倪勇提出了一种基于OSPF协议链路状态数据库进LSA行局域网拓扑构造算法，该算法能够有效地显示局域网拓扑结构；文献[7】利用OSPF协议中的数据库描述报文和链路状图2LSU报丈格式态更新报文来构造链路状态数据库，并且将数据按区域划分，LSU报文的主要字段描述如下：提高了网络拓扑算法的效率；文献[8]通过解析OSPF协议数(1)RouterID：始发该LSA的路由器ID。默认为路由器接据实现网络拓扑发现的算法，满足了拓扑算法应具有准确性、口地址中的最大值。完整性、实时性和低负载的要求。(2)AreaID：始发LSA的路由器所在的区域ID。2OSPF协议分析(3)NumberofLSAs：该报文包含的LSA数目。(4)LSA：该报文包含的LSA。2．1OSPF网络模型目前OSPF协议已经定义了11种LSA，本文提出的算法OSPF协议是一种链路状态协议，用于自治系统(autono．通过获取LSU报文中的RouterLSA和NetworkLSA，对网络进moussystem，AS)内。一个AS常被划分为多个区域(Area)，区行拓扑发现。域之间相对独立。区域是从逻辑上将路由器划分为不同的组，2．2．1RouterLSA每个组用区域号(AreaID)来标识。一个OSPF路由选择域可RouterLSA是每台路由器都会产生的LSA，这些数据包描划分成多个区域，所有区域都需要通过区域边界路由器(area述了路由器到达某个区域的链路状态，并且RouterLSA只在一boarderrouter，ABR)与一个称为OSPF骨干(backbone)的特殊区个区域内传播，不会穿越ABR。当路由器是一个ABR时，该路域直接相连。该特殊区域负责在不同区域间发布路由信息，由器会为每一个区域生成一个LSA：RouterLSA格式见图3。缺省标识为Area0。例如，一个OSPF路由选择域可划分为Area0-Area4这5个区域，Area0为OSPF骨干区域，Area1～LSageOptionsllArea4分别经区域边界路由器A，B，C和D与Area0直接相连。LinkstateIDAdvertisingrouter其OSPF网络模型如图1所示。LSSequencenumber2．2拓扑信息分析LSChecksumLength0lE0样Links每台OSPF路由器通过发送链路状态通告(1inkstateadver—LinkIDtisement，LSA)来描述与其相连链路的状态信息。这些链路状LinkDataTypeITOSMetric态信息包含了网络的拓扑结构信息。因此，只要获得并分析TOSl0TOSMetric这些LSA，就可实现网络拓扑发现。由于完整的LSA信息都LinkID被封装在LSU报文中，所以只需关注LSU报文即可。LinkDataLSU报文用来向其邻居路由器发送请求或更新LSA。其报文格式如图2所示。图3RouterLSA结构 15522011，Vo1．32，No．5计算机工程与设计ComputerEngineeringandDesign通过读取一条RouterLSA，可以获得用于拓扑发现的信系信息。通过两类LSA中得到的相同的DR接口IP地址，从息包括：一个路由器结点(Advertisingrouter)，该路由器结点的NetworkLSA获知的信息中寻找与RouterLSA中的路由器ID链路类型(Type)，以及与该路由器结点直接相连的邻居结点匹配的传输网地址，进而构成transit类型的完整连接关系信息。(LinkID)。Type的值分别代表路由器的4种不同链路类型。基于OSPF协议的网络拓扑发现算法的流程图如图5所示。具体链路信息见表1。开始表1链路状态信息类型将所有RouterLSA和NetworkLSA加入lsaListType描述LinkIDLinkData初始化连接关系列表connectList1point-to‘point邻居RouterID始发路由器的接口IP地址2仃ansitDR接口IP地址始发路由器的接口IP地址读取一条LSA3stubIP网络号子网掩码4virtuallink邻居RouterID始发路由器的接口IP地址断类获得linkStateld2．2．2NetworkLSA和networkMask室NetworkLSA只由网络中的指派路由器(designedrouter，计算与DR直接连接的DR)产生，同样只在一个区域里传播，不会穿越ABR。NetworktransitAddress和将advRouterII置linkType为l置linkTypeIl置linkType为1inkld加入llpoint-to-pointlI为stubI1virtuaI1inkLSA中记录了与某一传输网(transit)直接相连的所有路由器的RouterID，其格式如图4所示。将linkStateld和transitAddress分别将对应的routerld，linkld，加入transitMapBlinkData加入connectListLSagelOptionsl2LinkstateIDAdvertisingrooter<要二至LSSequencenumberLSChecksumILength得到transitMapA，transitMapB和connectListNetworkmaskAttachedrouter从transitMapA中读取一条映射关系，得到对应的linkld图4NetworkLSA结构由于NetworkLSA仅由DR产生，读取一条NetworkLSA主只能获得transit链路类型的拓扑信息。这些拓扑信息包括：一个DR结点，与DR直接相连的传输网地址，以及所有与此传输网直接相连的路由器ID。其中传输网地址需要通过Link置linkType为transitstateID和Networkmask计算得到，其它拓扑信息可以直接从NetworkLSA中的相关字段获得。将advRouter，linkld和transitAddress加入connectList3基于OSPF的网络拓扑发现算法一3．1算法描述本文提出的拓扑发现算法是在获得LSU报文中RouterLSA和NetworkLSA的基础上，通过分析两类LSA中包含的连接关系信息，进而实现网络拓扑发现。经过分析RouterLSA可以得到所有路由器结点及其连接关系信息。根据linkType值的不同，可将链路类型分为point-to—3．2算法实现point、stub、virtuallink和transit这4种。对前3种类型，可直接获基于OSPF协议的网络拓扑发现算法核心思想是分析收得包括路由器ID，LinkID和LinkData的完整网络连接关系信集到的LSA~O表lsaList中的每一条LSA，针对不同类型的LSA息。对于transit类型，只能得知路由器通过传输网与DR相连采取相应的操作，当处理完所有的LSA并得到完整的连接关接，包括路由器ID和DR接口IP地址信息，但无法获取具体的系列表connectList时算法结束。传输网地址，因此不能得到transit类型的完整连接关系信息。基于OSPF协议的网络拓扑发现算法的部分伪代码如下：经过分析NetworkLSA可以获知transit类型的连接关系for(1saList中的每个元素){信息。可直接得到DR通过传输网与哪些路由器相连接，通过if(是RouterLSA){计算还可得到包括DR接口IP地址和传输网地址信息，但无以routerld，linkId和linkData实例化一个Connect类的对象法获取除该DRP["与传输网相连的其它路由器的接口地址，因connect；此获得的transit类型连接关系信息也不完整。for(RouterLSA中的每条链路信息){整合所得到的transit类型信息，获得该类型的完整连接关根据linkType判断链路类型； 潘楠，王勇，陶晓玲：基于OSPF协议的网络拓扑发现算法2011，Vo1．32，No．51553switch(1inkType){可以通过一个网络接口发送任意数据包。case1：本文实验是在实验室单机上，基于Jpcap函数库捕获OSPF设置connect的linkType为point—to—point，将协议链路状态更新报文。通过调用getDeviceList()和open-其不重复地加入到connectList中；break；Device()方法选择网卡并打开设备；通过调用setFilter0方法case2：将过滤条件设置到IP层：最后调用processPacket0方法，将协将advRouter和linkld加入到transitMapA议号字段protocol设置为89，这样即可捕获OSPF协议链路中；break；状态更新报文。case3：4．2实验环境设置connect的linkType为stub，将其不重复本实验在单机上采用VMware安装了7台Linux虚拟机，的加入到connectList中；break；并在每台虚拟机上安装Zebra路由软件。这样，每台Linux虚case4：拟机就相当于一台路由器。通过Zebra分别对每台Linux虚拟设置connect的linkType为virtuallink，将其机进行OSPF协议配置，并启动OSPF协议，建立一个具有7台不重复的加入到connectLi~中；break；路由器，5个网段的仿真网络环境，其中包含4个区域和3台}区域边界路由器。}4．3实验结果分析}elseif(是NetworkLSA){在仿真网络环境中，通过调用Jpcap类库的processPacket()通过linkStateld和networkMask计算得到与该DR直方法捕获OSPF协议LSU报文，获得其中的RouterLSA和Net。接连接的传输网地址transitAddress；workLSA，采用提出的算法对仿真网络进行拓扑发现，实验结将linkStateld币口transitAddress力口入至0transitMapB中；果如图6所示。}}处理完所有RouterLSA和NetworkLSA后进行如下操作，得到完整的连接关系列表connectList：while(transitMapA非空){进行操作transitMapA．get(advRouter)后，得到该adv—Router对应的linkld；if(transitMapB．containsKey(1inkId)){得到该linkld对应的transitAddress；以advRouter,linkld和transitAddress实例化一个Connect类对象，并置该对象的linkType为transit，将其不重复的加入到connectList中；}图6实验结果)图6中每台路由器用唯一的RouterID表示，若为区域边4仿真实验及结果分析界路由器，则附有相应的ABR标识，传输网用网段号表示。通4．1实验工具过不同的图标，可以直观的反映出设备的类型以及它们之间(1)Zebra的连接关系。从图6可以看出，仿真网络中的7台路由器(其Zebra是一种TCP／IP路由软件，它支持BGP一4、BGP一4+、中3台为区域边界路由器)，5个网段及其连接关系全部被准OSPFv2、OSPFv3等协议。通过使用Zebra可以在Linux下配确的发现，说明该算法是行之有效的。置并运行OSPF协议，将安装Linux操作系统的PC机打造成5结束语一台“高级”路由器。(2)VMware本文提出了一种基于OSPF协议的网络拓扑发现算法。通过VMware可以在一台主机上模拟出多台计算机，利该算法通过对协议中的链路状态更新报文所携带的Router用虚拟机提供的虚拟网络设备如虚拟交换机、虚拟网卡，以及LSA和NetworkLSA进行分析，得到拓扑连接信息，从而进虚拟网络的连接方式，就可在单机上构建出虚拟的网络环境。行拓扑发现。基于OSPF协议的网络拓扑发现完全采用被(3)Jpcap动监测的方式获得数据，因此具有低负载的特点。但OSPFJpcap是一个能实现抓取与发送网络数据包的Java类库。没有提供端口级的拓扑连接信息，因此无法发现子网内部的Jpcap可以捕获以太网、IPv4、IPv6、ARP／RARP、TCP、UDP和拓扑结构。结合SNMP改进现有算法，对子网内部进行拓扑ICMPv4数据包。通过使用Jpcap，可以从一个网络接口获取发现，以获得更准确、完整的网络拓扑结构，将是下一步的数据包，并在Java运行环境下对它们进行分析和显示，同样也研究方向。(下转第1567页) 胡海明，董绍经，姜有田，等：第四代移动通信技术浅析2011，Vo1．32，No．51567(2)在计算机上进行多媒体处理的一个主要研究方向是凭借第四代移动通信技术高速率、高质量、大容量的多信源数据的编码，即在信息量不明显减少的情况下，研究如何媒体服务能力，可以展望在不久的将来，伴随人们出行的主提高数据的压缩效率以减少通信链路的负载。即使按照4G要通信工具手机和常用办公工具笔记本电脑或者其它娱乐系统对高速移动用户2Mbps的目标数据速率标准，当前绝大用途的数码音像设备将可以合而为一。人们带着这样一部多数的高质量的多媒体应用和服务也已经足够。计算机上多既可以看作是手机、电脑又可以被认为是电视或者相机的设媒体处理技术的发展重点将可以实现从高压缩比向高实时性备可以在全球的任何一个角落进行工作或者学习，人们的生的转变。活将基本不受到空间地理位置的限制。第四代移动通信技(3)网络就是计算机。现有的计算机通信网早已超越了铜术在影响和带动计算机技术发展的同时，也将显著改变人们线、光纤等有线概念的范畴。具有无线通信功能的外设、接口的生活方式，世界面貌将为之焕然一新!值得一提的是，中卡和接口模块正以迅猛的速度向每一台计算机扩张，未来的国由于主导了TD—LTE技术，有可能在这一次信息革命的浪4G将与Internet融合为一体。4G时代的手机将有越来越多的潮中占据先机。信息处理功能，移动计算机、手持式终端和平板电脑也将有越参考文献：来越强的通信功能，4G网络的用户终端将很难说到底是一部手机还是一台电脑。[1】MikiT,OhyaT,YoshinoH，eta1．Theoverviewofthe4thgenera·(4)伴随而来的一个问题是：未来将会是计算机占领手机tionmobilecommunicationsystem[C]．FifthInternationalCon—ferenceonInformation，CommunicationsandSignalProcessing，市场还是手机占领计算机市场?直观上，在计算机上增加一块无线网卡要远比把一部手机改造成一部电脑来得简单，实2005．际情况可能与设备制造商的技术力量以及用户现有的资源配[2]王芳，熊建设．4G中的MIMO．OFDM原理及关键技术[J]．中国置都有关系。对计算机工作者来说，不管情形如何，有意义的新通信，2009(23)：32．35．是，计算机的发展将不能离开4G独自进行，移动计算机成为[3]王军选．第四代移动通信系统及其关键技术研究[J]_电信科学，4G网络的用户终端只是时间上的早晚。同样，4G的进步和推2009(3)：90．93．广也离不开计算机技术的强大支持，软件技术、芯片技术等在【4】唐鹏，鲁东旭．无线通信中DSP和软件无线电技术的应用[J]．4G上的应用前景非常广阔。通信技术，2010，43(6)：224．226．[5]孔祥松，贾卓生．移动IPv6的切换技术[J]．计算机工程与设计，6结束语2006，27(8)：1453—1455．当今时代，计算机技术、通信技术和多媒体技术的相互[6]MorayRumney．LTEandtheevolutionto4Gwireless[M]．De-结合、彼此渗透已经是一个明显的事实。移动计算机，包括signandMeasurementChallenges，WileyPublishers，2009．平板电脑、智能手机和其它车载或者手持应用领域的嵌入式[7】闻立群．LTE技术的发展现状和演进趋势[J]．现代电信科技，终端设备，在市场上已经显示出强大的生命力。随着第四代2009(9)：37．42．移动通信技术的进一步发展和深入应用，移动计算机技术必【8]网易科技报道[EB／OL]．http：／／tech．163．corn／special／201lgsma／，将随之发生深刻而持久的变化。对移动计算机本身的研究20l1．O2．18．以及面向移动计算领域的开发已经成为当前计算机研发工[9]戢中东，王晖，赵新强，王少杰．数字化部队移动通信与指挥控制作的热点。装备技术研究[J]．计算机工程与设计，2006，27(3)：437．438．(上接第1553页)参考文献：[5】尤澜涛，朱巧明，李培锋．基于OSPF的网络拓扑快速发现系统【1】杨安义，朱华清，王继龙．一种改进的基于SNMP的网络拓扑发的设计[J]．计算机工程，2006，32(24)：l15．117．现算法及实现[J]．计算机应用，2009，27(10)：2412—2419．[6]倪勇，史怀洲，朱培栋．基于OSPF链路状态数据库构建网络拓【2】石永革，陈晓瑶．网络拓扑搜索算法的分析与优化[J]．计算机工扑[J]．计算机技术与发展，2009，19(3)：1．4．程与设计，2007，28(12)：2848—2850．[7]王慧，罗军勇，寇晓蕤．基于OSPF协议报文的网络拓扑分析算[3]王志刚，王汝传，王绍棣，等．网络拓扑发现算法的研究[J]．通信法[J]．计算机工程，2008，34(6)：103．105．学报，2004，25(8)：36—43．[8]赵天福，周丹平．基于OSPF协议的网络拓扑发现技术的实现[4]ShaikhA，GoyalM．AnOSPFtopologyserver：designandevalua—[J]．江南大学学报(自然科学版)，2008，7(2)：151-156．tion【JJ_IEEEJournalonSelectedAreasinCommunications，[9]KeitaFujii．Jpcap【EB／OL]．http：／／netresearch．ics．uci．edu／kfujii／2002．2O(4)：746．755．jpcap／doc／index．html，2010-01-06．