图论在网络拓扑发现算法中的应用

《图论在网络拓扑发现算法中的应用》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1期　　　　　　　　　　　　　　　　　作者一　等：文章题目　　　　　　　　13　　　　　　　　图论在网络拓扑发现算法中的应用路连兵1+，胡吉明2，姜岩1，21，2(河海大学计算机及信息工程学院,江苏南京210098)E-mail：famioo@yahoo.cn摘　要：网络拓扑发现技术已经广泛地应用在各种项目软件中。然而，随着网络结构复杂度升级，这给拓扑发现带来了挑战。所以我们越来越需要一种高效，准确的网络拓扑算法自动发现网络拓扑结构。目前的拓扑算法主要集中在：(1)路由层的发现。这个层面的发现算法在技术上

2、比较简单，只需要寻找路由与路由之间，或路由端口与子网之间的连接关系，利用路由器的自身特性，很容易实现。(2)链路层的发现。直到目前为止，已有的厂商工具很难准确发现网络拓扑，已发表的理论文献知识也只是理论上阐述，实际应用难度比较大。本论文，提出一种基于图论的骨架树数据存储结构算法，可以高效推断网络的拓扑关系。关键词：骨架树;子网;地址转发表;图论；信任节点TopologyDiscoveryinNetworksBasedonGraphTheory*LULian-Bing1+,HUJi-Ming2，JiangY

3、an1,21,2(SchoolofComputerScienceandInformation,HohaiUniversity,NanjingJiangsu210098,China)Abstract:Topologydiscoverysystemsarestartingtobeintroducedintheformofeasilyandwidelydeployedsoftware.However,Today'sIPnetworkiscomplexanddynamic.Keepingtrackoftopolo

4、gyinformationefficientlyisadifficulttask.So,weneedeffectivealgorithmsforautomaticallydiscoveringphysicalnetworktopology.Earlierworkhastypicallyfocusedon:(1)Layer-3(networklayer)topology,whichcanonlyrouter-to-routerinterconnectionsandrouterinterface-to-sub

5、netrelationships.Thisworkisrelativelyeasyandhaslotsofsystemscandoit.(2)Layer-2(linklayer),tillnow,notoolscandiscoverythenetworktopologyexactlybecauseofbadalgorithm.Inthispaper,Skeleton-treebasedonGraphtheoryisproposedtoinfertheconnectionsbetweennetworknod

6、es.Keywords:Skeleton-tree;subnets;AddressForwardingTable;GraphTheory；TrustNode1期　　　　　　　　　　　　　　　　　作者一　等：文章题目　　　　　　　　13　　　　　　　　1期　　　　　　　　　　　图论在网络拓扑发现算法中的应用　　　　　　9　　　　　　　　1网络拓扑的现状EthernetLocalAreaNetworks(LANs)是指在一区域内将不同的网络设备通过传输光缆，电缆连接起来，实现网络资源共享的网络。但是由于网络设

7、备种类众多，而且同类产品产自不同厂家也会在原理上有所区别，所以管理员要能够高效管理维护日益膨胀、复杂的网络已经十分困难。本课题——网络拓扑发现（TopologyDiscovery，简称TD）就是从降低网络维护人员工作的难度、准确高效反应网络结构的角度而研究的。TD主要功能是尽可能真实反应不同设备之间的物理连接关系。有效的TD算法不但能够快速绘制出网络实体互联关系，而且能够准确的体现不可管理设备如集线器HUB（但目前有的HUB是可管理的）等。这样网络管理员就可以直接在网络拓扑图上得到网络故障，流量瓶颈等重要

8、信息，对所发生的故障一目了然。如果网络拓扑上显示一条链路总处于满负荷传输状态，那么扩大该条链路的容量对提高网络性能将有很大帮助。1.1网络拓扑中几个难点至于难于拓扑第二层网络这种状况，其原因是多方面的，下面介绍在网络拓扑发现算法设计的过程中，仅仅借助于2层的网络设备的MIB信息所存在的困难。从国内外研究得知，设计出好的网络拓扑算法，主要是要解决一下几方面的问题。（i）2层网络设备的透明性。二层拓扑困难其原因是多方面的，主要是建