《链路层拓扑发现方法的设计与实现.doc》由会员分享，可在线阅读，更多相关《链路层拓扑发现方法的设计与实现.doc（4页珍藏版）》请在三一办公上搜索。
1、精品论文链路层拓扑发现方法的设计与实现童力 大连理工大学计算机科学技术系，大连 (100044) E-mail：tongli03摘要：本文首先介绍了链路层拓扑发现的基本概念，接着介绍了以太网链路层交换机的工 作原理，给出了交换机地址转发表的原理和读取的方法。之后介绍了基于判断交换机的地址转发表提出的互联的直接连接定理和间接连接定理, 并介绍了传统的基于上述定理的方法。 在分析了传统方法的不足之后，提出了一种简化版的基于交换机地址转发表的拓扑发现算法。最后介绍了生成树协议，以及基于生成树协议的链路层拓扑发现方法，将该方法与基于 地址转发表的方法结合，进一步明确设备间的互联关系，并给出了伪码描述。
2、实验结果证明了方法的有效性。 关键词：局域网；SNMP；拓扑发现；生成树中图分类号：TN911.731引言在实际应用中在大多数情况下, 仅仅发现网络层的拓扑结构是不够的, 还需要发现数据 链路层的拓扑结构, 即子网内的设备及其连接关系。局域网拓扑发现的复杂性在于以太交换机硬件的内在透明性: 对于链路层信息来说，网 络用户无法知道网络中交换设备的存在。这些交换机设备仅仅在执行生成树802.1D协议(STP) 时才和邻居设备交换信息, 况且这种协议也不是在所有环境下都使用。交换机能保留的唯一 状态是它的地址转发表, 它的作用是把收到的数据包转发到适当的端口上去。这些信息对于 局域网的拓扑发现来说是
3、足够的, 并且可以通过SNMP 的标准Bridge MIB5 来访问。局域 网中, 交换机是网络中的关节节点，以交换机为中心就能推导出以太网络的链接信息。2地址转发表和连接关系图 1 为链路层的网络模型图, 其中的节点包括交换机和主机。交换机通过它们的端口相 连, 主机通过集线器或者简单交换机的端口连接局域网。图 1 链路层网络在交换域中设备可以被划分为交换机集合 S 和主机集合 H。如图 1 所示, S=S1,S2,S3, H= H1,H2,H3，其中简单交换机可以等同于 hub。在交换式网络中，交换机不断学习每个 插口 frame 中的目的地址和源地址，记录地址转发表，然后根据 frame
4、 的目的地址将 frame- 4 -转发（交换）到合适的插口上去。以图 1 为例，S1 的地址转表包括 A13 和 A14，其中A13=S2,H1,H2，A14=S3,H3。 文献23提出了两个基本定理可以用于判断连接关系。其中Aij表示交换机i的第j个插口的地址转发集合。定理 2.1：如果 Aij U Akl = I （I 表示全体交换机的集合）且 Aij I Akl与端口 Skl 直连。= ，则端口 Sij定理 2.2：若路由器 R 与交换机 Si 的 Sij 端口直接相连当且仅当 Sij 是叶端口，且 Sij 的 地址转发表中包含路由器 R 的 MAC 地址。具体算法是通过定理 2 确定
5、直接与路由器，也就是网关相连的交换机，通过定理 2 确定 交换机之间的连接关系。虽然根据定理 1 可以确定交换机端口之间的连接关系。但是因为 在整个过程中，需要将一个交换机上的端口和其它所有交换机上的端口进行比较判断。如果 交换机很多，端口数量为 P（很大）时，基本上要进行 P2 次运算，使得运算量很大。3改进的基于地址转发表的算法主要思想是算法是约简掉 MAC 地址。首先扫描出所有 MAC 地址的集合 M。当交换机 的 Aij 中没有其他交换机的 MAC 时，可以认为主机是直接连接在交换机上，集合 M 中约掉 主机 MAC。具体算法如下：1.网络扫描子网中所有的 IP 地址，使得交换机的地址
6、转发表中保存转发的地址集合。2.通过 SNMP 查询得到各个交换机的地址转发表 Ai。3.以 MAC 地址做 hash 表。令 Sm 表示交换机的 MAC 地址表集合，Smi 表示第 i 台 交换机的 MAC 地址。令 Ai 表示第 i 台交换机的地址转发表，Aij 是第 i 台交换机 的第 j 口上转发的地址。4.找到 Ak 使得 Sm I Ak = 。则 Ak 中所有的主机都是和第 k 台交换机直接相连。5.在所有交换机的 Ai 中约简掉 Ak 包含的地址，同时将 Smk 从 Sm 集合中删除，将 其当成一个主机节点。6.重复过程 4，直到找不到 Ak 为止。上述算法中，在第 4 步中可以
7、逐渐推出一颗生成树，其运算相对较小，为 O(n)其中 n是子网中所有网络节点的数量。 在实际中根据上述算法编写了实用网络拓扑软件已经取得良好的效果。图 2 界面演示4. 基于生成树的拓扑发现方法4.1 生成树协议简介使用生成树协议，交换机之间传输一种特殊的消息，称为网桥协议数据单元（BPDU）， 此信息用于计算一颗生成树的结构。这些消息有如下用途：1.选择一个交换机为根交换机（Root Bridge）2.确定交换机到根交换机的最短路径。3.在每个网段上选出一个指定交换机（designated bridge），该网段只有通过该交换机 才能向根交换机方向发送数据。4.在每个交换机内选定一个根端口（
8、Root Port），只有通过该端口才能向根交换机方 向发送数据。5.确定交换机各端口的状态。6.每个网段的指定交换机（designated bridge）必有一个端口与该网段相连，称作该 网段的指定端口（designated port）。交换机之间不断交流这些信息，确定自己在生成树中的位置。通过这些信息，能够进行 链路层拓扑的探测。4.2 算法的实现定理 4.1：如果交换机 Ds 的 FDB 中有一个物理地址 M 的记录属于 Is,i 端口, 并且该端 口不是中继端口，那么该物理地址 M 对应的设备是直接连接在 Is,i 端口上。其中 Is,i 表示 设备 Ds 和 Di 直接连接，称为两个
9、设备的中继连接。性质 4.1: 如果交换机 Ds 有一个有效的转发记录 F(s,M)在生成树的前向边缘（与 root 相 反的方向）, 那么该记录对应的主机一定定位在以 Is,i=F(s,M)为根的子树下面。性质 4.2: 如果交换机 Ds 有一个有效的转发记录 F(s,M)在生成树的后向边缘(与 root 相 同的方向) , 那么该记录对应的主机不可能在生成树的 Ds 下面。基于上面的定理和性质, 当遍历时有如下四种情况:1.如果 F(s,M)不是中继端口, 那么主机一定是直接连接在该端口上（定理 2.1）。遍历 算法成功返回真值。2.如果 F(s,M)是在一个前向连接端口上，那么主机一定定
10、位在生成树的子树 Is,i 下面（性质 4.1）。3.如果 F(s,M)是在一个后向连接端口上，那么主机不可能定位在 Is,i 下面（性质 4.2）。4.如果 F(s,M)=, 那么遍历 Ds 的所有子树。根据上面的 4 中情况，有如下算法：1.定位根 SRoot,M2.初始化 location, region_root3.定位主机 Scur, M4.p=F(Scur,M)zScur, P 不是树干：location.switch=Scur, location.port=P, return 1;zP 是树干且，Scur,P 是前向边：foreach Snext On P do local_ho
11、st_helper(Snext,M), return 1zP 是树干且，Scur,P 是后向边：append(Scur,P)zP 是空：foreach Snext do local_host_helper(Snext,M), return 15总结和展望网络拓扑发现是进行网络管理的重要手段和工具，网络拓扑图为网络管理人员提供了一 个了解全局网络连接的直观手段要实现网络拓扑图形的生成，首先要搜索构造网络拓扑图 的各种信息。目前主要是利用各种网络拓扑搜索算法和相关协议来获取整个网络中的每个设 备的拓扑信息，本论文在介绍链路拓扑发现技术之后，详细的分析了基于的 SNMP 的链路 拓扑发现算法，并对此
12、算法进行研究，对其存在的问题进行了改进，并结合基于生成树的算 法进一步加强了该算法。实验结果显示了算法的有效性。本论文整个算法都是基于协议，发现的是开通服务的网络设备,但对那些没有开通协议 的设备不能进行信息采集，所以如果发现那些没有开通协议的设备，还需要结合其他的技术 来进行拓扑发现。参考文献1 K.McCloghrie. Definitions of Managed Objects for Bridges，InternetRFC1286.1991，12.2 Brue Lowekamp, David R.OHallaron, Thomas R.Gross, Topology Discover
13、y for Large Ethernet NetworksSIGCOMM 2001, 2001.83 Y.Breitbart, M.Garofalakis, C.Martin. Topology Discovery in Heterogeneous IP NetworksJ.IEEE INFOCOM-00，2000,3,1(26).265-2744 乐洁,寇晓蕤,罗军勇. Traceroute 及其在网络拓扑发现中的应用J,微计算机信息, 2005,4:228- 230. IEEETENCON905 Decker, E. , L angille, P. , R ijsinghani, A ,
14、and K. M c2Cloghrie. Definitions of Managed Objects for B ridges. RFC 1493, July 1993.6 郭建波, 李志明, 链路层拓扑发现算法, 微计算机信, 2006 年 09 期Design and Implementation of Topology Discovery inData-link LayerTong LiDepartment of Computer Science and Technology, Dalian University of Technology, Dalian(116023)Abstrac
15、tFirst, this paper introduces the link layer topology discovery of the basic concepts, then introduces theEthernet link layer switch operating principle, gives the address of the switch to make the principles and read. Second, switching to judge based on the address delivered to propose a direct Int
16、ernet connection and indirect connection theorem, and introduces the traditional view of the above theorem. Third, analyzing the shortcomings of traditional methods, a simplified version of the switch based on the address delivered to the topology discovery algorithm. Finally, spanning tree protocol
17、, based on the spanning tree protocol, as well as the link layer topology discovery methods, the methods based on the address delivered to the methods, equipment, further clarified the relationship between the Internet and gives the false description of the code. The results proved that the method is effective.Keywords: SNMP; Network; topology discovery; Spain tree
