小 型 微 型 计 算 机 系 统 Journal of Chinese Computer Systems2008 年 月 第 期 Vol.28 No. 2008图论在网络拓扑发现算法中的应用路连兵 1+，胡吉明 2，姜 岩 11，2，2(河海大学 计算机及信息工程学院,江苏 南京210098)E-mail ：famioo@摘要：网络拓扑发现技术已经广泛地应用在各种项目软件中。
然而，随着网络结构复杂度升级，这给拓扑发现带来了挑战。
所以我们越来越需要一种高效，准确的网络拓扑算法自动发现网络拓扑结构。
目前的拓扑算法主要集中在：(1)路 由层的发现。
这个层面的发现算法在技术上比较简单，只需要寻找路由与路由之间，或路由端口与子网之间的连接关系， 利用路由器的自身特性，很容易实现。
(2)链路层的发现。
直到目前为止，已有的厂商工具很难准确发现网络拓扑，已发 表的理论文献知识也只是理论上阐述，实际应用难度比较大。
本论文，提出一种基于图论的骨架树数据存储结构算法，可 以高效推断网络的拓扑关系。
关键词：骨架树;子网;地址转发表;图论；信任节点Topology Discovery in Networks Based on Graph Theory*LU Lian-Bing1+, HU Ji-Ming2，Jiang Yan1,21,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, Today's 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作者简介: 路连兵(1979－),男,江苏泗洪人,硕士。
主要研究网络自拓扑,软件项目管理,Perl 研究;胡吉明(1967－),男,硕导,副教授,主要研究 领域为计算机应用技术,网络安全,数据挖掘，Z 语言; 姜岩(1979-),男,硕士研究生,主要研究方向,网络应用,中间件2小 型 微 型 计 算 机 系 统2004 年1 网络拓扑的现状 Ethernet Local Area Networks (LANs) 是指在一区域内 将不同的网络设备通过传输光缆， 电缆连接起来， 实现网络 资源共享的网络。
但是由于网络设备种类众多， 而且同类产 品产自不同厂家也会在原理上有所区别， 所以管理员要能够 高效管理维护日益膨胀、 复杂的网络已经十分困难。
本课题 ——网络拓扑发现（Topology Discovery ，简称 TD）就 是从降低网络维护人员工作的难度、 准确高效反应网络结构 的角度而研究的。
TD 主要功能是尽可能真实反应不同设备 之间的物理连接关系。
有效的 TD 算法不但能够快速绘制出 网络实体互联关系， 而且能够准确的体现不可管理设备如集 线器 HUB（但目前有的 HUB 是可管理的）等。
这样网络管 理员就可以直接在网络拓扑图上得到网络故障， 流量瓶颈等 重要信息，对所发生的故障一目了然。
如果网络拓扑上显示 一条链路总处于满负荷传输状态， 那么扩大该条链路的容量 对提高网络性能将有很大帮助。
地连接， 甚至于插上线缆就可以建立一个局域网。
而这种连 接的简便性使得局域网对网络管理软件都是透明的。
但这并 不意味着第二层发现功能将无所作为。
关键基础设施的厂商 们已经开发出了自有的发现协议，可将数据存储于 SNMP 企业版，例如 Cisco 公司的 CDP 协议（Cisco Discovery Protocol ） Extreme Networks 的 EDP 协 议 （ Extreme 、 Discovery Protocol ） Enterasys Networks 的 CDP 协议 、（Cabletron Discovery Protocol）以及 Nortel Networks 的NDP 协议（Nortel Discovery Protocol）等。
这里的一个明 显问题是， 这些协议都不能工作在混合厂商设备集成的网络 环境下。
2 层网络设备交换机、网桥、集线器等与终端的主 机或上层的路由设备都是直接互联， 而且设备不记录相邻的 设备信息，仅有二层交换机上维护着一张表,记录着接收的 数据包应该从哪个端口转发出去,这张表就是 AFTs。
（ii）2 层网络中设备缺乏统一的标准。
2 层网络中存在亚元设备， 所谓亚元设备是指有些设备通过 SNMP Bridge MIB 很难实现获取 AFTs 信息，甚至不支持 SNMP 服务；有些 设备比如集线器（HUB）, 不具有类似于交换机的"智能记1.1 网络拓扑中几个难点至于难于拓扑第二层网络这种状况，其原因是多方面 的，下面介绍在网络拓扑发现算法设计的过程中， 仅仅借助 于 2 层的网络设备的 MIB 信息所存在的困难。
从国内外研 究得知，设计出好的网络拓扑算法， 主要是要解决一下几方 面的问题。
忆"能力和"学习"能力，它也不具备交换机所具有的 MAC(Media Access Control)地址表。
所以要准备发现网络中 这些设备，是网络拓扑算法设计的一大挑战。
（iii）多子网网络结构。
目前的 LANs 都支持划分多子网，在同一子网内的设备可以直接通讯， 不需要经过路由器。
而 不同子网内的设备之间通讯需要经过路由器数据转发 （即使（i）2 层网络设备的透明性。
二层拓扑困难其原因是多方面的，主要是建立这些网络十分容易。
因为交换机可以透明1 期图论在网络拓扑发现算法中的应用3物理上是连接直接连接） 同一子网内的设备构成了连接树。
。
见图 1-1 a） （ 。
它表示的典型的网络结构被分成三个子网结 构:N 1 { n1 , n 6 , n 7 , n8 , n13 , n14 , n15 , n 20 , n 25 } N 2 { n 3 , n 4 , n 5 , n 9 , n10 , n16 , n17 , n 21 , n 23 }n21 n3 n4 s5 n5 s11 h1 s1 s6 s8 s7 n10 s2 h2 n23N 3 { n 2 , n11 , n12 , n16 , n18 , n19 , n 22 , n 24 }s9 s10 n9 n17 n16图 1-1(c) 连接树其中 n i 表示主机节点， s i 表示交换机节点， h i 表示集线器 等共享设备，相应的网络无向树模型见图 1-1（b） 、图 1-1 （c） 、图 1-1（d） 。
n21 n3 n4 s5 n5 n13 n11 n24n19 s11 h1 s3 n12n20 n1 s1 s6 n18 n2 s7 s9 s4 s8 n10 h3 n14 s13 n16 s14 n15 n22 s2 h2 n7 n6 n8 n23n19 s11 h1 n24 n11 n12 s3 n2 s1 s6 n18 s7 s9 h3 n16 s14 n22s2 h2 n7 n6 n8II 网络模型 目前日益复杂的 LAN 主要由交换机（也称网桥） ，路由 图 1-1(d) 连接树s2 s4s10 n25 n9 n17 n16图 1-1(a) 网络模型n20 s11 s5 h1 n1 s1 s6 n13 s7 s9 s10 n14 h3 s13 n15图 1-1(b) 连接树器， 主机等组成， 由于本课题研究的 LAN 是一个连接实体， 在 2 层网络中，任意一对网络节点之间总会存在仅包含 2 层网络设备（交换机，HUB 等）的路径，且仅有一条。
路 径中的交换的活动端口(也称转发端口)可以通过生成树协 议判断。
子网生成树用无向树 G (V , E ) 表示。
其中 V 是网络节点n254小型微型计 算机DvN系统2008 年集， E 是任意两网络节点的活动端口的物理连接关系。
把 实际物理网络拓扑结构抽象表达成无向树 G (V , E ) ，是本 课题－网络拓扑发现的目标。
在无向树中， 交换机是无向树 内部节点，路由器和主机用无向树的叶节点表示。
2 层网 在 络拓扑中，发现路由器比较困难， 所以用一系列的主机表示 一个路由器。
由于子网生成树是无向树 G ，任意两节点之 间的数据传输都遵循生成树协议， 而路径选择由交换机活动 端口上的 AFT 信息决定。
换个角度描述，AFT 是端口接收 的一系列 Media Access Control (MAC)地址信息， 形成 MAC 地址表并维护它。
下面为了算法的描述方便，给出 TD 算法 和描述中所用到字符的原始定义：10.:节点 v 的所有活动端口，即如果 F N v , k 蛊N，则k Î Dv。