网络拓扑发现技术的研究中南大学硕士毕业论文

中南大学硕士学位论文网络拓扑发现技术的研究姓名李琳申请学位级别硕士专业计算机软件与理论指导教师李杰20080501摘要在网络管理中，网络拓扑信息是其它所有管理功能的基础。如何高完备性、高准确性、高效率地快速自动发现并获取网络拓扑信息是当今各网络研究机构共同关注的问题。本论文重点从网络层拓扑发现和数据链路层拓扑发现两级进行研究。关于网络层拓扑发现的工作，首先通过分析现有的基于ICMP、DNS、OSPF、SNMP的算法，总结了各自的优缺点和适用范围。然后通过深入学习MIB，对传统SNMP算法的不足提出了改进。通过合并路由器的多个IP地址，引入哈希链表数据结构，限制拓扑发现的范围，从而准确并高效地发现网络中的主干拓扑结构。链路层拓扑发现中的关键是发现交换机到交换机之间的连接关系。在对链路层进行拓扑发现的研究工作中，先是通过研究现有的链路层拓扑发现算法，引入了路径集合的形式，利用各路径集合相对独立的特点执行多线程并发，进而提出了一种基于路径集合的AFT链路层拓扑发现改进算法。该算法大大提高了拓扑发现的效率，并且不要求各个网桥FDB表的信息是完备的，但不能处理不支持生成树协议交换机的连接。针对这个不足，通过结合基于网桥转发表和基于网桥生成树两种算法的优点，提出了一种新的链路层拓扑发现算法。在网络中存在不可网管交换机或HUB的情况下该算法都能很好的发现子网中交换机与交换机、交换机与主机之间的连接关系，得到完整、正确的拓扑连接图，较之已有的拓扑发现算法具有更好的适用性、准确性和效率。关键词网络管理，拓扑发现，简单网管协议，地址转发表，生成树协议ABSTRACTINTHENETWORKMANAGEMENTSYSTEM，NETWORKTOPOLOGYINFORMATIONISTHEFOUNDATIONOFOTHERFUNCTIONSITISACOMMONISSUEFORTHOSENETWORKINSTITUTESTOAUTOMATICALLYDISCOVERANDOBTAINNETWORKTOPOLOGYINFORMATIONWITHCOMPLETENESS，ACCURACYANDEFFICIENCYTHISPAPERFOCUSESONTHESTUDYOFVARIOUSNETWORKTOPOLOGYDISCOVERYALGORITHMS，WHICHAREDIVIDEDINTOTWOPARTSNETWORKLAYERTOPOLOGYDISCOVERYANDLINKLAYERTOPOLOGYDISCOVERYONTHESTUDYOFNETWORKLAYERTOPOLOGYDISCOVERY,WEINTRODUCETHECURRENTNETWORKLAYERTOPOLOGYDISCOVERYMETHODSALGORITHMSBASEONICMP，DNS、OSPF，SNMPINVIEWOFTHESHORTAGEOFSNMP,WESTUDIEDMIB，ANDBRINGUPTHECORRESPONDINGSOLUTIONBYMERGINGIPADDRESS，INTRODUCINGDATASTRUCTURESUCHANDLIMITINGTHESCOPEOFTOPOLOGYDISCOVERY,WECANACCURATELYANDEFFICIENTLYDISCOVERTHECONNECTIONSBETWEENROUTERSANDSUBNETSTHEKEYOFTHELINKLAYERTOPOLOGYDISCOVERYINTHE2NDLAYERISTOFINDLINKSBETWEENSWITCHESANDSWITCHESONTHESTUDYOFLINKLAYERTOPOLOGYDISCOVERY,WEANALYZETHECURRENTLINKLAYERTOPOLOGYDISCOVERYALGORITHMINORDERTOIMPROVETHEIMPERFECT，ANOVELALGORITHMFORDATALINKLAYERTOPOLOGYDISCOVERYBASEDONADDRESSFORWARDINGTABLEISPROPOSEDTHEFORMOFPATHSETISINTRODUCEDINTOTHISALGORITHMBASEDONTHERELATIVELYINDEPENDENTCHARACTERISTICOFPATHSET，ITCARRIESOUTTHEMULTITHREADEDTOBECONCURRENTTHISALGORITHMIMPROVESTHEEFFICIENCYANDDOESNOTREQUIRETHEINFORMATIONOFEACHBRIDGEFDBTABLETOBECOMPLETEBUTITCANTFINDEQUIPMENTSTHATDONOTSUPPORTSNMPSUCHASDUMPSWITCHESAIMINGATTHISINSUFFICIENCY,THEPHYSICALTOPOLOGYDISCOVERYALGORITHMWASANALYZEDANDCOMPAREDRELYINGONSTANDARDSNMPMIBFDBANDTHEALGORITHMRELYINGONSTPINFORMATIONINTHEFIRSTPLACETHENANEWALGORITHMFORDISCOVERINGETHERNETTOPOLOGYWASPRESENTED，WHICHHADTHEADVANTAGESOFTHETWOALGORITHMSTHISALGORITHMCANFINDTHECONNECTIONSBETWEENSWITCHANDSWITCHSWITCHANDHOST，EVENTHOUGHTHEREEXISTSSWITCHORHUBWHICHDOESNOTSUPPORTSNMPPROTOCOLINTHESUBNETWORKANDTHENITCANOBTAININTACTANDCORRECTTOPOLOGYCONNECTIONGRAPHCOMPAREDWITHTHEEXISTINGTOPOLOGYDISCOVERYALGORITHM，THEALGORITHMWHICHWEPROPOSEHASBETTERAPPLICABILITY,VERACITYANDEFFICIENCYKEYWORDSNETWORKMANAGEMENT，TOPOLOGYDISCOVERY,SNMP,ADDRESSFORWARDINGTABLE，SPANNINGTREEPROTOCOLLII原创性声明本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。作者签名堕堑盎日期丝2星年月丘日学位论文版权使用授权书本人了解中南大学有关保留、使用学位论文的规定，即学校有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。作者签名蔓里选二导师签名日期兰墨年月丛日硕士学位论文第一章绪论11研究背景第一章绪论自20世纪90年代以来，随着INTERNET的发展，特别是宽带时代的到来，计算机网络己经渗透到社会生活的各个方面，并对社会的进步和经济的发展起着越发重要的作用。计算机网络在使得人们的工作和生活方式发生巨大变革的同时，也使得人们对它的依赖性越来越强。随着用户对网络性能及服务质量的要求越来越高，这就使得计算机网络本身运行的可靠性变得至关重要。有研究表明，在现有的技术条件下，一个普通的局域网在一年中平均出现重大故障二十次，由此产生的服务失效时问长达十六小时L。企业在分享计算机网络带来的高效率、低成本的同时，也不得不承受这些故障带来的损失。而一个高效的网络管理系统可以给网络管理员提供良好的信息来源，及时发现运行中出现的故障，找出性能瓶颈，缩短网络失效时间。因此，网络管理已成为网络发展中一个重要的关键技术，对网络的发展有着很大的影响。拓扑发现作为网络管理系统的一个重要组成部分，很多重要的网络管理任务，如网络资源管理、服务器部署、事件关联以及故障分析等都是以网络的拓扑结构为前提的【21。网络拓扑发现就是将搜索到的网络设备及其之间的动态连接关系用图形的方式直观地显示出来，从而网使络管理员可以了解到的全局网络的拓扑结构信息，有效地对网络设备进行监控和配置，对网络中出现的故障进行诊断，进而更好地优化整个网络。同时它也是衡量一个商业网管系统成败的重要尺度13儿41。因此，一个好的网络管理系统首先需要掌握整个被管网络的拓扑结构。网络拓扑信息作为网络管理的基础，它的重要性显而易见，如何高效、快速、完整、准确的自动发现并获取网络拓扑信息已成为计算机网络领域的研究热点。12研究的意义随着网络技术的发展，网络不仅渗透到企业、机关等工作领域，而且已经走进了我们的日常生活中，并且发挥着越来越重要的作用。在这个网络化的时代，人们的工作、学习、生活都已经与之息息相关，在很多方面甚至可以说是依赖网络的。同时随着网络规模越来越大，结构也越来越复杂，各企事业单位对网络的管理都面临着管理难、控制难、维护难等问题。尽管国外现在有IBM公司的NETVIEW、HP公司的OPENVIEW、SUN公司的SUNNETMANAGER等功能强大的商品化软件，但它们价格昂贵，并且无法充分满足我们实际网络环境中的具体要求，同时也存在很大的安全隐患。而目前国内的网络管理产品由于技术上的原因，或硕士学位论文第一章绪论多或少都存在着实用性或通用性不是很强，网络管理系统功能不够完善等问题120。如何更好的管理网络，使它们更好的为人们服务，是网络管理面临的紧迫问题，并已引起了人们的广泛重视，引发了新一轮的研究高潮。网络管理的目的就是通过运用自动化软件系统来达到对整个网络的监视和控制，并最大限度的保证计算机网络正常运行，从而提高效率，降低成本P】。因此，如何管理计算机网络，如何建立一个安全性高、功能全面、满足自己网络实际要求的网络管理系统，是当今网络管理技术人员必须要解决的问题。发现并跟踪一个网络的拓扑结构对于有效的网络管理来说是必不可少的，网络拓扑发现作为配置管理的核心与故障管理的基础，成为了整个网络管理系统中非常重要的组成部分。正是由于网络管理和网络应用的需要，网络拓扑发现技术逐渐成为网络管理领域的一个热点。网络拓扑为网络管理人员提供了从全局上把握网络状况的途径，使得对网络的设计、监控等活动更为有效和合理，进而大大提高网络管理的效率，故设计好的拓扑发现算法是一个很有意义的研究方向。由于网络具有层次性的特点，不同的管理者可能对网络层面的关注有所不同，有的需要了解骨干网络上设备之间的连接状况，而有的可能只对他自身所在的子网感兴趣。所以开发分层次的拓扑发现算法具有非常重要的现实意义。本论文正是在这个背景下进行选题，目的就是对网络管理域的网络拓扑发现算法进行深入的研究。此外，准确有效地实现网络的拓扑发现还有着很大的需求和应用前景。除应用于网络管理和规划之外，网络拓扑信息还可以用于服务器定位，帮助用户确定自身在网络中的位置，从而决定服务器的位置以及选择可以将时延最小化、可用带宽最大化的网络服务提供商15】。另外，拓扑信息还可应用于拓扑敏感算法中，使得一些新的协议和算法能够在得到网络拓扑信息的基础上改善网络性能。13国内外研究现状网络管理技术的系统研究是从八十年代中期开始的，美国在该领域一直处于领先地位。虽然国外的商用网管软件拥有出众的功能和性能，并且大多数还推出了第三方的开发平台，但昂贵的价格和对二次开发的限制还是使我们却步。近几年，网络管理技术在国内也得到了迅速地发展，但由于在获取最新技术和渠道、研发投入等方面的障碍，网络管理技术在我国还是起步阶段。国内的产品实现的功能还比较简单而且针对性比较强，离广泛应用还有很大的差距。随着拓扑发现在网管系统中的重要性得到越来越多的关注，目前大多数商用网管系统如惠普公司的OPENVIEW网管系统中的NNM60，CA的NETWORKLT，CISCO公司开发的CISCOWORKS2000与FLUKE公司的MAPSHOW中都集成了拓扑发现的2硕士学位论文第一章绪论功能120J。随着计算机网络的飞速发展，手工绘制网络拓扑图已经成为一件非常烦琐的工作，有时候甚至是不可能的。于是，人们开始了对网络拓扑自动发现的研究。1990年，IETF在RFCL157T61中正式公布了SNMP简单网络管理协议，一年后KMCCLOGHRIE和MROSE在RFCL213171中提出了基于TCPDP协议的因特网管理信息库MIBII，这些都充分考虑了网络管理中的拓扑发现需要，因此被广泛的支持和应用，目前，SNMP己成为网络管理领域中事实上的工业标准。网络层的拓扑发现，在早前较多采用的是基于ICMP的拓扑发现方法，如MERCATOR算法、CNRGCOMELLNETWORKRESEARCHGROUP算法都是利用TRACEROUTE的简单性及通用性发现网络层的拓扑结构。前者结合了启发式，进行多次有限跳的主动探测喁J；后者从BGPBORDERGATEWAYPROTOC01的路由信息丌始，逐步发现每个域的路由器与链路，最后将结果进行合并【5】。现在，随着主要的网络设备都提供对SNMP协议的支持，基于SNMP协议的网络层拓扑发现方法被广泛采用。该算法通过采集设备的MIB数据从中提取出关于网络拓扑的信息。国内在网络拓扑发现领域起步相对较晚，但到目前为止，也取得了一些成果。像北京华信亿码科技发展有限公司开发的网络管理软件EASYMANAGER就能正确地发现并以图形的方式显示网络层设备及连接关系。国内的许多高校和研究所包括象西安交通大学、华中科技大学等也对网络自动拓扑发现进行了深入的研究，但也主要集中于管理域内的逻辑拓扑发现。目前基于SNMP协议的网络层的拓扑发现算法相对比较成熟，基本都是通过分析第三层网络设备的路由表，采用广度优先搜索或者深度优先搜索来进行发现网络设备并确定与之的连接关系。随着大量的交换机被部署到网络中，链路层的拓扑结构对于网络管理也越来越重要了。近几年研究的人也比较多，目前用的较多的方法有基于地址转发表的拓扑发现算法、基于生成树的拓扑发现算法和基于端口流量的拓扑发现算法。其中基于地址转发表的拓扑发现算法对二层设备的ARP表具有很大的依赖性，如果从ARP表中能够获取完整的管理信息，发现效果会很好；反之，效果很差。并且，该算法的效率不如基于生成树的算法。基于生成树的算法简单、高效，但要求所有交换机均支持生成树协议，算法的通用性不强。到目前为至链路层的拓扑发现还没有成熟的技术和方法。因此，当前的链路层拓扑发现算法还存在许多需要改进的地方，很多方面还值得深入去研究。SNMP的出现也为数据链路层的拓扑发现算法提供了有力的工具，HWACHUNLIN等人在参考文献10QH开始利用BRIDGEMIBRFCL493LJ来获取交换机的连接信息，但是该方法的准确性不高。之后，贝尔实验室YURIBREITBART等和卡奈基梅隆大学BRUCELOWEKAMP与郑海等分别提出各自基于地址转发表的物理拓硕士学位论文第一章绪论扑发现算法。BREITBART算法【14J【15J主要通过查询桥地址转发表信息确定物理拓扑，要求各网桥的地址转发表的信息是完全的；BRUCE算法【12L主要解决在一个广播域内交换机之间出现使用HUB连接这种情况的拓扑问题；郑海等人提出的物理拓扑发现算法【13】【171需要通过在网络中注入额外流量来保证网络中的每一个节点的地址转发表信息是的完整，进而进行链路层设备的连接判断。14论文所做的工作本文开始就网络管理系统的功能和系统构成做了简单的介绍，然后，详细介绍了论文中用到的主要信息库和协议一一管理信息结构SMI、管理信息库MIB和SNMP协议。并对拓扑发现原型系统的总体架构和模块进行了设计。本文主要是针对网络拓扑发现系统的主要部分一一网络拓扑发现算法进行了研究。通过对已有算法的现状及原理的分析，分别提出了基于网路层和链路层的拓扑发现改进算法。拓扑发现包括网络层拓扑发现和数据链路层拓扑发现。网络层的拓扑发现，主要是利用SNMP协议和路由器MIBII变量中的I仃ABLE、IPADDRTABLE和IPROUTETABLE三张表来发现网络层OSI第三层设备及其之间的连接关系。该发现技术相对简单，准确性较高，目前的网管软件中普遍采用这种方法。而数据链路层的拓扑发现主要是指一个子网内部的链路层OSI第二层设备及其之间连接关系的发现。其中链路层设备间的连接关系包括路由器与交换机、交换机与交换机、交换机与主机等设备之间的连接关系。本文在对已有算法进行深入的研究的基础上，提出了网络层拓扑发现的改进算法。对传统算法中存在的路由器多IP地址识别和控制算法发现范围这两个问题提出了较好的解决方案，并对算法的时问复杂进行了对比分析，提高了算法的效率，并给出了具体的数据结构设计和流程设计。对于数据链路层拓扑发现，在分析比较现有的数据链路层拓扑发现算法的基础上，提出了一个基于路径集合的AFT拓扑发现改进算法。该算法利用集合中各路径的相对独立性，进行多线程并发执行判定交换机之间的互连关系，使得算法简单、高效，但算法的前提要求比较苛刻，算法的适用范围受到了限制，不能处理不支持生成树协议的交换机的问题。因此，本文在综合分析了基于地址转发表和基于生成树两种链路层拓扑发现算法的优缺点后，将两种算法相结合提出了一种改进的链路层拓扑发现算法，该算法的前提符合大部分网络的实际情况，适用范围广，并较好的解决了网络中存在“哑元”的问题。4硕士学位论文第一章绪论15论文的结构本文各章节的内容安排如下第一章绪论。主要介绍了当今网络管理、网络拓扑发现的背景和意义以及国内外发展现状。在总结现有成果的基础上，说明了本文的主要工作和章节安排。第二章网络管理概述。首先介绍了网络管理的相关知识以及网络管理的功能和系统结构，最后重点介绍了SNMP的体系结构。第三章网络层拓扑发现。介绍了几种目前已有的网络层拓扑发现算法，分析了各种算法的优缺点。重点对SNMP算法存在的问题进行处理和解决，提出了一个基于SNMP的改进网络层拓扑发现算法。第四章链路层拓扑发现。首先对相关的技术进行了论述。然后分析了现有的链路层拓扑发现算法。最后，重点提出了两个数据链路层拓扑发现改进算法，并详细论述了算法的实现，给出了实现流程图和算法分析。第五章拓扑发现原型系统设计。首先提出了一个层次化拓扑发现原型系统模型，作为拓扑管理实现的模型基础。然后，详细介绍了原型系统的模块组成结构及核心模块的设计。第六章结束语。对论文所作工作进行总结，并指出有待于今后进一步开展的工作。硕士学位论文第二章网络管理21网络管理概述第二章网络管理1969年伴随着世界上第一个计算机网络一一ARPANET的产生第一个计算机网络管理也产生了。但是，由于当时的网络规模小，复杂性不高，当时的网络管理系统还只是简单的专用网络管理系统。随着网络的发展，规模增大，复杂性增加，简单的专用网络管理系统越来越不适应网络异构互连的发展趋势。随着INTEMET的出现和发展更使人们意识到了这一点。INTERNET的核心机构IABINTERNETACTIVITIESBOARD随后推出了SNMP1988和CMOTCMIPCMISONTCPIP1989。由于CMIPCMIS的实现的复杂性和实现代价高而遇到了困难，而SNMP由于简单实用的特点一推出就得到了广泛的应用和支持【3】。目前，SNMP已成为网络管理领域中事实上的工业标准，大多数网络管理系统和平台都是基于SNMP的。网络管理就是为保证网络系统能够持续、稳定、安全、可靠和高效地运行，而对网络实施的一系列方法和措施。网络管理的复杂性取决于网络资源的数量和种类【2】【3】。1网络管理的功能ISO在ISOIEC74984文档中定义了网络管理的五大功能，并被广泛接受。网络管理的目的是为了更好地实现网络的五大管理功能。这五大功能是故障管理、计费管理、配置管理、性能管理和安全管理【2】【3】【16】【18】。1故障管理是网络管理中最基本的功能之一。故障管理又称失效管理，主要对来自硬件设备或路径节点的报警信息和故障进行监控、定位和处理。因此，网络故障管理包括故障检测、隔离和纠正三个方面。其中分析网络故障原因是网络故障管理的核心内容。2计费管理记录网络资源的使用，目的是控制和检测网络尤其是公共网络操作的费用和代价。一方面可以为网络管理者提供基于个人或团体用户的计费信息，保证了网络的运营和发展。另一方面可以根据计费管理的统计结果了解终端用户的网络访问流量的分布，更好的做到按需分配网络资源，提高网络资源的使用效率。3配置管理负责监控和管理整个网络的配置状态。它的目的是为了实现某个特定功能或使网络性能达到最优。配置管理包括拓扑管理、软件管理、网络规划和资源管理等，其中关键是设备管理。4配置管理关心的是网络是否在正常运行，而性能管理关心的则是网络运6硕士学位论文第二章网络管理行的好坏。性能管理就是通过测量网络中硬件和软件的性能指标来估计系统资源的运行情况和通信效率等系统性能，进而对网络资源进行优化，以保证网络的可靠性和连续的通信能力。5安全性一直是网络的薄弱环节之一，但用户对网络安全的要求却很高。安全管理有两层含义一方面，要保证网络用户和网络资源不被非法使用；另一方面，也要确保网络管理系统本身不被未经授权的用户访问。安全管理借助风险分析，使成本和风险达到最佳搭配，实现网络安全运行。2网络管理的系统结构网络管理系统原则上由以下四部分构成【3】1多个被管代理2至少一个网络管理者3一种通用的网络管理协议4一个或多个管理信息库MIBOSIE侈J的公共管理信息服务CMIS定义了管理应用程序所使用的公共过程和参数。对于INTEMET网络，使用的是SNMP协议。SNMP建立在由UDP和IP所提供的无连接服务之上。典型的网络管理体系结构组织模型如图21。竹理实体网络1瞒魏蝴简尚油L管理数据库LL管理教据库IL管理数据库L图21典型的网络管理体系结构组织模型任一网络管理域至少都应该有一个网络管理站用来负责网络管理的全部监视和控制工作。网络管理站和被管代理通过交换管理信息来获取网络信息，其中网络管理器定期轮询各被管代理，被管代理监听和响应来自网络管理器的网络管理查询和命令。这种信息交换通过一种网络管理协议来实现，信息分别驻留在管理工作站和被管理对象的管理信息库MIB中。这种管理协议与管理信息库一起协调工作，简化了网络管理的复杂过程【3L。22SNMP的体系结构基于TCPIP的互联网络使用IAB制度的网络管理体系，它由三个部分组成，即基于TCPIP互联网络的管理信息结构SMI，基于TCPIP互联网络的管7硕士学位论文第二章网络管理理信息库MIB和简单网络管理协议。1管理信息结构SMI网络资源被以对象的形式存放于管理信息库MIB的虚拟库中。对象在MIB中的存放形式被称为管理信息结构SMI。目前两个标准数据模型是INTEMETSMI和OSISMI。这两种SMI均采用ISO的抽象语法表示语言ASN1表示。SNMP的规范SMI为定义和构造MIB提供了一个通用框架。同时也规定了可以在MIB中使用的数据类型，说明了资源在MIB中怎样表示和命名【2们。每个MIB对象都有3个属性名字、语法和编码，这三个属性用来保证管理对象在SNMP实现中得到准确使用。1对象名字网络上的每个对象，不管是设备还是设备的功能，都必须有一个明确表示的名字，即对象标识。所有的管理对象形成一个树状的层次性的结构模型如图22，这棵树以一个没有名字的根节点开始，处于叶子位置上的对象是实际的被管对象。对象标识符用点分十进制整数字符表示。每个后继的十进制整数代表了下一层次。对象标识符有两种形式名字形式和数字形式。例如MIB对象SYSDESCR具有如下的标识名字形式ISOORGDODINTEMETMGMTMIB2SYSTEMSYSDESCR数字形式13612111夕”面厂鬈尊蔷齐舔H阿。，T。I。，呐“Z薷蔫霁滁CGPG。哼研州”LM玎F扯EF2IPF4，K甲15TCPL6UDP【7H。图22MIB树型结构2语法SMI使用的数据类型只是ASN1的一个子集，主要用来定义管理对象数据类型和起始列值的符号【23】。表示管理对象必须至少包括下面四个方面的属性对象类型、存取方式、状态和对象标识符。3编码8硕士学位论文第二章网络管理SMI规定由ASN1为消息定义抽象语句，基本编码原则BER提供传输语句。抽象语句定义资料标识的规范，传输语句定义语句中的组件的可传输编码。管理对象的实例在网络管理进程和代理进程之间传送时，使用BER编码规则进行编、解码，每个BER数据项包含3个部分标签TAG、长度LENGTH和值VALUE，称为TLV三元组。2管理信息库MIB所谓管理信息库MIB21122】【24J，就是所有代理进程包含的、并且能够被管理进程进行查询和设置的信息的集合。它规定了网络代理设备必须保存的数据项，数据类型，以及允许在每个数据项中的操作。通过对这些数据项目的存取访问，得到网关的统计信息，然后通过对统计信息进行综合分析来实现基本的网络管理。因此，MIB的访问是实现网络管理的关键。基于SNMP的网络层拓扑发现算法主要是通过SNMP协议来获得MIB中与网络拓扑相关的信息，然后通过对这些信息进行分析处理，得到网络的拓扑结构。算法要求所有的路由器都必须实现MIBII。MIBIIRFCL213T23】由很多不同的组组成，基于SNMP的网络层拓扑发现算法用到的组包括SYSTEM组，INTERFACES组和IP组。下面详细介绍这三个组中包含的主要对象。1系统SYSTEM组包括7个简单变量，分别为SYSDESCR、SYSOBJECTLD、SYSUPTIME、SYSCONTACT、SYSNAME、SYSLOCATION和SYSSERVICES。其中其中SYSDESCR描述了设备的相关信息，一般包括厂商，型号等。SYSOBJECTLD唯一标识特定厂商的特定类型设备。SYSSERVICE可用于判断设备类型，从其二进制形式最低位到第7位，如果某位为1则提供OSI对应层次服务，其中最低位对应于第一层。第3位为1则说明该节点提供路由功能，是路由器设备。2接口INTERFACES组包含关于该实体的物理接口方面的一般信息，包括配置信息和发生在每个接口的事件的统计信息。其中定义了一个表示本设备接口数量的简单变量IFNUMBER和一个接12表IITABLE，每个接121一行。表的索引项是IFINDEX，其取值范围是从1至LJIFNUMBER，并为每个接口分配一个唯一的序列号。IFDESCR为接12名称，ITTYPE表示接E1类型，亦即本接12所在子网的类型，常见如以太网6、8025令牌环9、FDDI15。可见，访问路由器接12表的ITTYPE值可确定与之相连子网的简单拓扑。3IP组LP组定义了许多简单变量，其IPFORWARDING为1时表示该节点具有IP转发功能，可作为路由器的判定依据。本组还定义了3个十分有用的表格变量IP地址表IPADDRTABLE、IP路由表IPROUTETABLEFSIARP地址转换表IPNETTOMEDIATABLE，9硕士学位论文第二章网络管理它们是网络层拓扑发现的重要信息来源。11IP地址表此表给出了节点自身所有接口的P地址信息，同时结合INTERFACES组的ITTABLE表，可以把接口和其IP地址一一对应起来。节点的每个IP地址对应表格中一行，每行有5个变量。其中将IPADENTADDR和IPADENTNETMASK按位与，便得到该接口所属子网的IP。可见，访问路由器的IP地址表，即可得到连接州，R，这是路由器级拓扑发现的关键。语法描述如下SEQUENCEOFLPADDRENTRYIPADDRENTRYSEQUENCEIPADENTADDRIPADDRESS，指定设备的IP地址信息IPADENTLFLNDEXINTEGER，各表目的接口号IPADENTNETMASKIPADDRESS，在IPADDRENTRY对象表中的IP子网掩码21IP路由表通常在路由器节点中该表才有意义，此表用于存放节点中的所有路由信息，网络层的拓扑发现算法主要就是利用该表来判断网络层的拓扑结构。子网与路由器以及路由器和路由器的关系都能从路由表中得出来。它包含了13个对象，发现逻辑拓扑时仅涉及其中的4项IPROUTEDEST，IPROUTELFLNDEX，IPROUTENEXTHOP，IPROUTETYPE。其中，路由的类型IPROUTETYPE有四种，当IPROUTETYPE值为LOTHER时，表示其他非后面三种类型的情况；值为2INVALID时，表示IFLNDEX所对应的接口已经无效；值为3DIRECT时，表示对应的IPROUTENEXTHOP变量中的IP地址是被访问结点自身接口的IP地址，IPROUTEDEST所表示的目标网络与此IP地址表示的接口直接相连值为4INDIRECT时，表示IPROUTELFLNDEX对应的接口与IPROUTEDEST表示的目标网络不直接相连，而是由路由器与路由器直接相连，从该接口到网络目标的下一跳路由是IPROUTENEXTHOPIP地址所表示的结点，通过这个IP地址，我们可以获得下一台路由设备上的路由信息。MIBII对路由表结构中各项描述如下IPROUTETABLEOBJECTTESYNTAXSEQUENCEOFIPROUTEENTRYLPROUTEENTRYSEQUENCEIPROUTEDESTLPADDRESS，路由器的目的地址。如为0000，说明该路由为缺省路由。IPROUTELFLNDEXINTEGER，路由的当地接口索引，与INTERFACE组中的IFINDEX相同都可以作为区分接口的标识符，LO硕士学位论文第二章网络管理即同一接口的这两个MIB变量值相同。IPROUTENEXTHOPIPADDRESS，路由器的下一个网关地址IPROUTETYPEINTEGER，路由的类型。有四种类型OTHER1，INVALID2，DIRECT3，INDIRCT4IPROUTEMASKIPADDRESS，路由目的地的子网掩码3ARP地址转换表提供了节点所在子网内设备IP地址到物理地址的对应转换。信息来自节点系统上ARP高速缓存。访问路由器的地址转换表，可迅速得出子网内设备IP地址，便于子网拓扑发现。语法描述如下SEQUENCEOFIPNETTOMEDIAENTRYIPNETTOMEDIAENTRY2SEQUENCEIPNETTOMEDIALFLNDEXINTEGER，IPNETTOMEDIA表中的接口号IPNETTOPHYSADDRESSPHYADDRESS，IPNETTOMEDIA表中的物理硬件地址IPNETTOMEDIANETADDRESSIPADDRESS，11,F17T应于IPNETTOMEDIA表中的物理地址的IP地址3SNMP协议SNMP126127】【28】|291是基于TCPIP网络的网络管理标准，用于监控网络性能，检测分析网络故障，并配置网络设备。它作为应用层上的协议，主要通过一组INTEMET协议及其所依附的资源提供网络管理服务。随着INTEMET的迅速发展SNMP也在不断发展以适应新的要求，到目前为止SNMP已历经了三个版本。SNMP的体系结构见图23主要包括管理站MANAGER，代理AGENT，管理信息库MIB，网络管理协议SNMP。为了确保SNMP协议的简单性，吣；J；拜图23SNMP体系结构硕士学位论文第二章网络管理目标，所以选择UDP为传输协议。在SNMP的体系结构中，有两种管理机制是很重要的，一种是SNMP的轮询机制，另一种是SNMP的管理机制，也就是代管。轮询管理信息库是通过若干MIB操作原语完成的，为了管理进程和代理进程之间交互信息，SNMP定义了五种报文130L，分别是GETREQUEST、GETNEXTREQUEST、SETREQUEST、GETRESPONSE、TRAP。拓扑发现主要是通过前两种操作来获取被管设备的信息，从而建立起拓扑关系图。利用SNMP进行拓扑发现可以快速地从MIB库中获取拓扑信息，并且MIB库中保存的是实时自动更新的信息。现在，SNMP协议已被绝大多数的网络设备所支持。故本文中的拓扑发现方法就是采用了基于SNMP获得MIB信息的技术。23本章小结本章是对网络管理研究的综述。在这一章里，我们首先对网络管理做了概述，介绍了网络管理系统的体系结构，并详细的介绍了拓扑发现算法中用到的简单网络管理的协议的体系结构，其中包括管理信息结构SMI、管理信息库MIB和SNMP协议。12硕士学位论文第三章网络层拓扑发现第三章网络层拓扑发现通常情况下，IP网络可划分成主干网和子网两级结构，他们分别对应于网络结构的第三层网络层和第二层数据链路层。主干网通过路由器把各个子网连接起来，而子网通常包括交换机、网桥、HUB和大量的主机。数据链路层网络拓扑发现则是在网络层拓扑发现基础上得到子网信息后再进行的二级拓扑发现，所以网络层拓扑发现对于最终得到的整个网络拓扑结构的准确性起着非常重要的作用。下面将对目前现有的几种网络层拓扑发现算法分别进行讨论，并分析它们的优缺点，最后详细描述了一种基于SNMP协议的网络层拓扑发现改进算法。31现有网络层拓扑发现算法网络层拓扑发现方法多种多样，目前常用的网络层拓扑发现算法主要有四种，分别基于ICMP协议、DNS、OSPF协议、SNMP协议实现。它们各具特点，但其中以PING和TRACEROUTE应用范围最广，以SNMP最高效。1基于ICMP的拓扑发现算法1算法说明ICMPL33J是用于网关和主机传送控制信息或差错信息的协议，常用的工具就是“PING”。PING报文很小，给网络带来的负载也小，而且容易实现，在网络拓扑发现中常用来获取在线设备的信息。通过PING发送ICMP“回应请求”包报文，可以测试网络设备的活动状态和可达性，通常用异步PING的请求方式来提高探测的速度，同时不会导致网络阻塞。通常进行拓扑发现还要结合“TRACEROUTE工具，用来分析网络的连接情况。2算法的优缺点分析该方法理论简单，实现也比较可靠。几乎所有基于TCPIP协议体系结构的网络设备都支持该协议，PINGTRACEROUTE都采用主动探测手段，适用范围广，通用性强。但采用此方法也存在着些问题1发现方法本身具有一定的盲目性，虽然可以高效地发现活动的网络设备，但是利用“PING”操作得到的结果只能说明从管理站到所测试IP之间是否可以到达，而中间经过哪些路由器并不能确定。在用“TRACEROUTE”操作后，可以知道从管理站到测试IP中间经过了哪些路由器，但是路由器之间连接情况的分析却非常麻烦。2“PING”操作对于活动的主机IP来说效率较高，返回的速度较快，但是13硕士学位论文第三章网络层拓扑发现如果该目的地址不存在，则算法将遭遇很长的延时甚至可以达到20秒。而且“TRACEROUT“操作也需要较长的反应时间，对于网络负载也有较大的影响。3在当前的网络中我们不能使用PING的定向广播特性。这个特性是网络的一个安全漏洞，因为它可能被拒绝服务攻击所利用。因此，基于ICMP拓扑发现方法对于快速发现网络设备的连接关系比较困难。它一般适用于子网内拓扑的发现。2基于DNS的拓扑发现算法1算法说明域名服务器DNS134】是一个非常庞大的分布式数据库，在这个数据库中保存有用户计算机和一些网络设备的信息。它维持了一个域内每个名字到其IP地址的映射关系，大多数域名服务器通过域名转换命令ZONETRANSFER可以返回该域内名字的列表。因此“ZONETRANSFER”经常被用来发现域中的主机和路由器。因此理论上讲，利用DNS的这一特性可以发现域内的所有的主机和路由器设备。这个算法需要假定的前提条件是网域内允许DNS服务器的域转换功能和广播PING。其工作过程如下首先由DNS做一次域转换，获得本网域内所有主机名和路由器的列表，然后再根据一定的算法获得子网信息。但是，通常我们得到这份本网域内的主机、路由器的列表同实际的主机、路由器情况是不完全一样的因为DNS给出了它最近一次存储的信息，因此接下来就要有两个工作来做了1消除无效的主机名。2验证获得的子网信息。2算法的优缺点分析使用区域传送技术可以方便的发现域内的主机和路由器，这些设备可以做其它算法的起点，而且这种方法负载低，速度也比较快。并且算法的实现条件较为简单、方便。当然DNS也存在许多缺陷首先，此算法极度依赖于DNS域转换，使得发现结果不够准确，因为用动态主机配置协议DHCP获取IP地址的主机并没有DNS服务。而出于安全因素，有些网络并不支持DNS域转换。这种情况下，这个算法就无法运行。其次，存储于DNS数据库中的信息可能并不一致，这意味着存在于数据库中设备可能不再有效，或者可能有些设备虽然有效，但是却没有在数据库中登记。因此总的来说，基于DNS的拓扑发现算法虽然实现简单，但是并不能达到很好的效果，因此对此算法并不推荐。3基于OSPF的拓扑发现算法1算法说明OSPF开放最短路径优先是IAB推荐的内部网关协议，是一种链路状态协议，该协议不要求路由器与其邻站交换距离信息。它采用的是每个路由器主动探14硕士学位论文第三章网络层拓扑发现测与其邻站相连的链路状态，并将这些信息发送给它的相邻站，而邻站将这些信息在自治系统中传播，每个路由器接收这些链路状态信息，这样所有的路由器都保存一份完整的网络链路状态图。因此所有结点不必以分布方式计算“最佳路由“，而是使所有路由器结点存放一个完整的网络链路状态图。所有的路由器通过这个链路状态图，然后用DIJKSTRA最短路径算法，获得到达目标结点的最短路径。因此，链路状态协议最实质的内容便是维护这张链路状态图，通过路由器之间的通信来交换彼此链路状态图，不断更新其内容，保持所有路由器的链路状态图的一致性。基于OSPF的发现算澍36】引进了OSPF协议的原理，通过实现OSPF协议，与路由设备通信，利用与路由设备通信的时候得到的路由信息来构筑网络拓扑图。2算法的优缺点分析由于基于OSPF的发现算法只需要访问主干区域的路由器就可以得到拓扑发现信息，利用OSPF路由信息协议，可以从路由设备中提取通过该设备的所有IP地址或IP子网的路由信息表，构造出拓扑信息连接表，因此算法具有速度快、性能高的特点，在一般不超过一个自治系统的企业网络中具有较大的适用性。但是实现起来难度比较大，而且搜索只能限定在某个范围内进行，并且要求该范围内的网络设备都支持OSPF协议。此外，OSPF没有端口级的拓扑连接信息。4基于SNMP的拓扑发现算法1算法说明SNMP是TCPIP网络中应用最广泛的网络管理协议。它的基本思想是所有的网络设备维护一个MIB库保存其所有运行进程的相关信息，并对管理工作站的查询进行响应。在网络设备的MIB库中含有网络连接的信息，基于SNMP的网络拓扑发现算法就是通过采集设备的MIB数据从中提取出关于网络拓扑的信息。因此，基于SNMP的拓扑发现算法方法，其基本思想就是从管理中心的缺省路由开始，采用广度优先搜索遍历的方法，对整个网络中的路由进行广度搜索，用SNMP获取每台被搜索到的路由器的路由表信息，然后进行综合分析，从而发现网络中的路由拓扑结构。然后进行子网搜索，确定子网内各网络设备的状态、类型等等。2算法的优缺点分析基于SNMP拓扑发现的主要优点是，当网络中发生变化，信息会即时自动地随之变化；而且提取信息的整个过程相当迅速，这在很多方面加快了拓扑发现的速度，因此发现过程和算法快速简单，目标明确。同时由于SNMP的简单易硕士学位论文第三章网络层拓扑发现于实现的特点，并且随着SNMP协议的发展，一般的机器都支持这个协议，也使其成为了事实上的标准，因此该算法的使用范围最为广泛，而且发现效率高，对网络负载和系统开销相对较小。由于从路由表可以获得下一站地址的信息，因此对于受到访问限制的网络，仍然可以获得其第一级路由器，得到比较完整的网路拓扑关系。但是，该方法也存在一些不足之处1要求设备必须支持SNMP协议，无法发现网络中无路由功能的网络设备，包括交换机和主机设备。2因为路由表是通过唯一的IP地址作为记录因素，而一个路由器往往对应多个IP地址。这样，由于基于路由表的发现方法是基于IP地址的，所以对于路由器的多IP可能导致路由器发现与实际情况不合。通过对各种拓扑算法比较发现，SNMP算法具有较大的通用性，适合大范围的拓扑发现，并将在未来的拓扑发现领域中占有重要的位置。32基于SNMP网络层拓扑发现的改进算法321关键技术问题1路由器“多IP”地址及已访问网关判定问题路由器一般拥有多个接口，每个接口都有相应的IP地址，通过其中的任意一个IP地址通常都可以访问该路由器。这样就存在同一个路由器被多次访问的问题，并且容易被混淆成为有多个路由器。对于路由器多IP地址合并问题，当前存在的一些解决方法有1利用MIB中的SYSLOCATION和SYSOBJECTLD这两个变量来唯一标识一个路由器设备。但是这种方法需要人工的参与，不能保证和先前的设备的区别，不适合单独采取这种方式来标识路由器。2ICMP探测法。这类算法通用性强，但是大量的应用PING和TRACEROUTE对网络的负载影响较大。已访问网关的判定问题主要是由于骨干网中的路由器之间通常会有回路存在，如果不对当前路由器是否已访问过进行判断的话，当对网络中的路由器进行广度优先遍历拓扑发现时就可能出现重复循环访问路由器的问题，造成拓扑算法无法结束。对已访问网关的判定作为网络层拓扑发现算法里重要的环节，它的时间复杂度也决定着整个拓扑发现算法的时间复杂度的高低。本文的算法，是通过引入标识IP和哈希链表这种数据结构来解决路由器多IP及已访问网关的判定问题。因此，在路由器数据结构中增加了一个标识IP和一个哈希编号NO变量。地址表中的IPADENTADDR对应路由器一个接EL的网关地址。通过查询IPADENTADDR就知道哪些IP地址对应同一个路由器设备。同时IPADDRTABLE中的对象都是只读的。考虑到当前的实际情况是存在一些不合法的子网，例如16硕士学位论文第三章网络层拓扑发现用一个代理进行地址转换将一个子网内的所有不合法的地址转换为一个合法的IP地址再与外界进行通信。所以，选择IPADDTABLE中的最大的IP更合理，取得的IP地址是合法的可能性更大。因此，我们将路由器接口表IPADENTADDR最大的IP地址作为该路由器的标记，即为它的标识IP。考虑到不同路由器的IP地址的最低字节的十进制数分布通常较均匀，所以哈希编号NO我们取的是标识IP的最低一个字节的十进制数，如标识IP为202117981L，那么哈希编号NO就为11。对于已访问网关采用哈