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

图论在网络拓扑发现算法中的应用( 路连兵1+，胡吉明2，姜 岩1，2 1，2(河海大学 计算机及信息工程学院,江苏 南京 210098) E-mail ：famioo@ 摘　要：网络拓扑发现技术已经广泛地应用在各种项目软件中。然而，随着网络结构复杂度升级，这给拓扑发现带来了挑战。所以我们越来越需要一种高效，准确的网络拓扑算法自动发现网络拓扑结构。目前的拓扑算法主要集中在：(1)路由层的发现。这个层面的发现算法在技术上比较简单，只需要寻找路由与路由之间，或路由端口与子网之间的连接关系，利用路由器的自身特性，很容易实现。(2)链路层的发现。直到目前为止，已有的厂商工具很难准确发现网络拓扑，已发表的理论文献知识也只是理论上阐述，实际应用难度比较大。本论文，提出一种基于图论的骨架树数据存储结构算法，可以高效推断网络的拓扑关系。 关键词：骨架树;子网;地址转发表;图论；信任节点 Topology Discovery in Networks Based on Graph Theory* LU Lian-Bing1+, HU Ji-Ming2，Jiang Yan1,2 1,2(School of Computer Science and Information, Hohai University, Nanjing Jiangsu 210098, China) Abstract: Topology discovery systems are starting to be introduced in the form of easily and widely deployed software. However, Todays IP network is complex and dynamic. Keeping track of topology information efficiently is a difficult task. So, we need effective algorithms for automatically discovering physical network topology. Earlier work has typically focused on: (1) Layer-3 (network layer) topology, which can only router-to-router interconnections and router interface-to-subnet relationships. This work is relatively easy and has lots of systems can do it. (2)Layer-2(link layer), till now, no tools can discovery the network topology exactly because of bad algorithm. In this paper, Skeleton-tree based on Graph theory is proposed to infer the connections between network nodes. Key words: Skeleton-tree; subnets; Address Forwarding Table; Graph Theory；Trust Node 1 网络拓扑的现状 Ethernet Local Area Networks (LANs) 是指在一区域内将不同的网络设备通过传输光缆，电缆连接起来，实现网络资源共享的网络。但是由于网络设备种类众多，而且同类产品产自不同厂家也会在原理上有所区别，所以管理员要能够高效管理维护日益膨胀、复杂的网络已经十分困难。本课题——网络拓扑发现（Topology Discovery ，简称TD）就是从降低网络维护人员工作的难度、准确高效反应网络结构的角度而研究的。TD主要功能是尽可能真实反应不同设备之间的物理连接关系。有效的TD算法不但能够快速绘制出网络实体互联关系，而且能够准确的体现不可管理设备如集线器HUB（但目前有的HUB是可管理的）等。这样网络管理员就可以直接在网络拓扑图上得到网络故障，流量瓶颈等重要信息，对所发生的故障一目了然。如果网络拓扑上显示一条链路总处于满负荷传输状态，那么扩大该条链路的容量对提高网络性能将有很大帮助。 1.1网络拓扑中几个难点 至于难于第二层网络这种状况，其原因是多方面的缺乏统一的标准Media Access Control)地址表。所以要准备发现网络中这些设备，是网络拓扑算法设计的一大挑战。 （iii）多子网网络结构。目前的LANs都支持划