网络拓扑发现技术研究
|
摘要
随着计算机网络技术的飞速发展,各组织机构对计算机网络的高度依赖性使得网络运行的可靠性变得至关重要。从而对网络管理提出了更高的要求。在网络管理中,网络拓扑信息是其它所有管理功能的基础。只有在掌握了被管理网络正确、完整的拓扑结构之后,才能对网络进行正确、有效的管理操作。如何快速、高效并准确地发现网络拓扑信息是当前网络管理领域关注的重要问题。
本论文重点研究了网络拓扑发现中的各种算法,完整的网络拓扑发现必须分两个层次来进行：逻辑拓扑发现和物理拓扑发现。
本文首先分析了现有的主流逻辑拓扑发现算法,系统、详细地总结了这些算法的优缺点,并针对这些算法的不足提出了逻辑拓扑发现的改进方案,解决了传统算法中存在的诸多问题。
其次,本文就物理拓扑发现问题,重点分析了被广泛关注的基于地址转发表的物理拓扑发现算法,并总结了该类算法的局限性。给出了一套基于生成树协议的用于推导物理设备端口间连接关系的定理与规则,并基于这些规则设计了相应的拓扑发现算法。该算法不依赖于地址转发表的完整性,不需要注入附加的流量,能够发现被生成树协议阻塞的连接和不支持SNMP的设备,拓扑发现的准确度高。
最后本文基于以上提出的改进算法,设计实现了一个用于拓扑发现的原型系统。并在实际的网络环境中进行了测试,测试所生成的网络拓扑与实际的网络拓扑相符,验证了本文提出的改进算法的正确性和有效性。
VLAN技术的广泛应用和IPv6各项技术的逐渐成熟,已向网络拓扑发现提出了新的挑战。含VLAN的物理拓扑发现,及IPv6网络环境下的拓扑发现都是值得进一步研究的重要内容。
With the rapid development of network technology, all kinds of organization depend on network so much that the operational reliability of network become vital. Therefore, It sets higher demands for network management. Network topology information is the fundament of all other management function in network management. Only by grasping the accurate and complete topology information can we make the suitable and efficient network management. How to discover network topology information rapidly and efficiently is the focus of attention in network management field.
In this paper we focus on all kinds of algorithm of network topology discovery, the result show that we can discover comprehensive network topology by two layers: logical network topology discovery and physical network topology discovery.
Firstly, this paper analyzes current mainstream algorithm of logical network topology discovery and summarizes the advantages and disadvantages in detail. We propose several improved methods about those disadvantages and solved some problems of classic algorithm.
Secondly, this paper investigates the physical network topology algorithm based on address forwarding table and summarizes the restriction of the algorithm. This paper gives some theorems and rules based on Spanning Tree Protocol which are used to infer the connections between network node's ports. A physical network topology discovery algoritlim based on those rules was designed.The algorithm does not depend on address forwarding table completion and do not need extra network traffic.It can discovery the blocked connections and non-SNMP equipments. Accuracy of the algorithm is higher.
Finally, a prototype system based on these improved algorithms has been designed and implemented in this paper. The prototype system has been tested in actual network environment. The experimental result is in conformity with actual network topology, verifying that our algorithm can efficiently discover the accurate network topology.
With the development of VLAN technology and IPv6 technology, network topology discovery is confronted with new challenges. Physical topology discovery in network with VLAN and topology discovery in IPv6 network are worth further researching.
本论文重点研究了网络拓扑发现中的各种算法,完整的网络拓扑发现必须分两个层次来进行：逻辑拓扑发现和物理拓扑发现。
本文首先分析了现有的主流逻辑拓扑发现算法,系统、详细地总结了这些算法的优缺点,并针对这些算法的不足提出了逻辑拓扑发现的改进方案,解决了传统算法中存在的诸多问题。
其次,本文就物理拓扑发现问题,重点分析了被广泛关注的基于地址转发表的物理拓扑发现算法,并总结了该类算法的局限性。给出了一套基于生成树协议的用于推导物理设备端口间连接关系的定理与规则,并基于这些规则设计了相应的拓扑发现算法。该算法不依赖于地址转发表的完整性,不需要注入附加的流量,能够发现被生成树协议阻塞的连接和不支持SNMP的设备,拓扑发现的准确度高。
最后本文基于以上提出的改进算法,设计实现了一个用于拓扑发现的原型系统。并在实际的网络环境中进行了测试,测试所生成的网络拓扑与实际的网络拓扑相符,验证了本文提出的改进算法的正确性和有效性。
VLAN技术的广泛应用和IPv6各项技术的逐渐成熟,已向网络拓扑发现提出了新的挑战。含VLAN的物理拓扑发现,及IPv6网络环境下的拓扑发现都是值得进一步研究的重要内容。
With the rapid development of network technology, all kinds of organization depend on network so much that the operational reliability of network become vital. Therefore, It sets higher demands for network management. Network topology information is the fundament of all other management function in network management. Only by grasping the accurate and complete topology information can we make the suitable and efficient network management. How to discover network topology information rapidly and efficiently is the focus of attention in network management field.
In this paper we focus on all kinds of algorithm of network topology discovery, the result show that we can discover comprehensive network topology by two layers: logical network topology discovery and physical network topology discovery.
Firstly, this paper analyzes current mainstream algorithm of logical network topology discovery and summarizes the advantages and disadvantages in detail. We propose several improved methods about those disadvantages and solved some problems of classic algorithm.
Secondly, this paper investigates the physical network topology algorithm based on address forwarding table and summarizes the restriction of the algorithm. This paper gives some theorems and rules based on Spanning Tree Protocol which are used to infer the connections between network node's ports. A physical network topology discovery algoritlim based on those rules was designed.The algorithm does not depend on address forwarding table completion and do not need extra network traffic.It can discovery the blocked connections and non-SNMP equipments. Accuracy of the algorithm is higher.
Finally, a prototype system based on these improved algorithms has been designed and implemented in this paper. The prototype system has been tested in actual network environment. The experimental result is in conformity with actual network topology, verifying that our algorithm can efficiently discover the accurate network topology.
With the development of VLAN technology and IPv6 technology, network topology discovery is confronted with new challenges. Physical topology discovery in network with VLAN and topology discovery in IPv6 network are worth further researching.
引文
[1]R.Siamwalla, R.Sharma, S.Keshav. Discovering Internet Topology. http://www.cs.cornell.edu/skeshav/papers/discovery.pdf.1999
[2]Case.J, Fedor.M, Schoffstall.M, et al.A Simple Network Management Protocol (SNMP). RFC 1157.1990,5
[3]Mansfield.G, Ouchi.M, Jayanthi.K et al. Techniques for automated Network Map Generation using SNMP. IEEE INFOCOM'96.1996,3,473-480
[4]张宏莉,方滨兴,胡铭曾等. Internet测量与分析综述.软件学报.2003,14(1).110-116.
[5]Donnet.B, Raoult.P, Friedman.T, et al. Efficient Algorithms for Large-Scale Topology Discovery. ACM SIGMETRICS 2005.2005,6,33(1).327-338
[6]Donnet.B, Raoult.P, Friedman.T, et al. Improved Algorithms for network topology discovery. Springer Berlin Heidelberg.2005,149-162
[7]Govindan.R, Tangmunarunkit.H. Heuristics for Internet map Discovery. IEEE INFOCOM 2000.1371-1380
[8]Siamwalla.R, Sharma.S. Discovering Internet Topology[EB/OL]. http://www.cs.comell.edu/skeshav/papers/discovery.pdf
[9]韩涛,毕于深,刘峰.网络拓扑发现算法设计.抚顺石油学院学报.2003,23(4).72-74.
[10]蔡伟鸿,舒兆港,刘震.基于SNMP协议的以太网拓扑自动发现算法研究计算机工程与应用.2005,41(14).156-160
[11]叶小涛,魏海平,王福威等.基于SNMP的网络拓扑发现研究与实现.石油化工高等学校学报.2005,9,18(3).82-86
[12]Bierman.A, Jones.K. Physical topology MIB. RFC2922.2000,9
[13]Breitbart.Y, Garofalakis.M, Martin.C, et al. Topology discovery in heterogeneous IP networks. INFOCOM 2000.265-274
[14]Breitbart.Y, Garofalakis.M, Jai.B, et al. Topology discovery in heterogeneous IP networks:The Netlnventory system. IEEE/ACM Transaction on Networking.2004,6,12 (3).401-414
[15]郑海,张国清.物理拓扑发现算法的研究.计算机研究与发展.2002,39(3).264-268
[16]Bejerano.Y, Breitbart.Y, Garofalakis.M, et al. Physical topology discovery for large multisubnet networks. IEEE INFOCOM 2003.342-352
[17]Bruce Lowekamp, David R.O'Hallaron, Thomas R.Gross. Topology discovery for large ethernet networks. ACM SIGCOMM 2001.237-248
[18]Yantao Sun, Zhiqiang Shi, Zhimei Wu. A Discovery Algorithm for Physical Topology in Switched Networks. Proceedings of the IEEE Conference on Local Computer Networks.2005,11.311-317
[19]Black.R, Donnelly.A, Fournet.C. Ethernet topology discovery without network assistance. Proceedings of the 12th IEEE International Conference on Network Protocols(ICNP).2004,10.328-339
[20]Son.MH, Joo.BS, Kim.BC, et al. Physical topology discovery for metro ethernet networks. ETRI Journal.2005,8,27(4).355-366
[21]Tao Li, Zhiqiang Shi, Zhimei Wu. Discovering layer-2 topology in bridged local area networks. Computer Science.2003,30(12).6-8,15
[22]郭瑜茹,张斌,石冰心VLAN拓扑发现算法研究.计算机研究与发展.1999,36(6).745-750
[23]Astic.I, Festor.O. A Hierarchical Topology Discovery Service for IPv6 Networks. IEEE/IFIP Network Operations and Management Symposium 2002.497-510
[24]李琳,李杰.基于SNMP的网络拓扑发现算法.计算机工程与设计.2008,3,29(6).1345-1347
[25]R.Siamwalla, R.Sharma, S.Keshav. Discovering Internet Topology.IEEE INFOCOM'99.567-570
[26]Hwa-chun Lin, Shou-chuan Lai, Ping-wen Chen. An algorithm for automatic topology discovery of ip networks. IEEE ICC'98.1192-1196
[27]J.Schonwalder, H. Langendorger. How to keep Track of Your Network Configuration. Proc.7th Conference on Large Installation System Administration (LISA Ⅶ).1993,11.101-105
[28]H.Burch, B.Cheswick. Internet watch:Mapping the Internet. Computer. 1999,4,32(4).97-98
[29]谢希仁.计算机网络.第5版.电子工业出版社.2008,1.140-143
[30]J.Case, K.McCloghrie, M.Rose. Structure of Management Information for Version 2 of the Simple Network Management Protocol(SNMP v2). RFC1902.1996,1
[31]J.Galvin, K.McCloghrie. Administrative Model for version 2 of the Simple Network Management Protocol(SNMP v2). RFC 1445.1993,4
[32]K.McCloghrie, M.Rose. Management Information Base for Network Management of TCP/IP-based internets:MIB-Ⅱ. RFC 1213.1991,5
[33]E.Decker. Definitions of Managed Objects for Bridges. RFC1493.1993,7
[34]谢晓燕,赵婧如,马素刚.网络安全与管理实验教程.西安电子科技大学出版社.2008,8.250-251
[35]凌军,曹阳,李莉等.基于ARP和SNMP的网络拓扑自动发现算法.2001,47(1).67-70
[36]郑洪方,王玉峰,王光兴等.基于IP网络的物理拓扑自动发现算法.小型微型计算机系统.2006,27(1).17-21.
[37]刘亚莉,孙亚民.基于SNMP的网络拓扑结构自动发现研究.微型机与应用.2004,23(4).28-31
[38]李可,薛质,铁玲.IP网络拓扑自动发现研究.计算机工程.2004,30(5).66-68,187
[39]由维昭,刘强,韦卫等.多方位网络拓扑发现的通用算法与技术实现.计算机应用研究.2004,21(12).257-261
[40]邱建林,何鹏.一种改进的网络拓扑发现方法.计算机应用.2005,25(4).891-893
[41]R.Braden. Requirements for Internet Hosts-Communication Layers. RFC1122. 1989,10
[42]张伟明,罗军勇等.网络拓扑发现中的路由器别名识别技术研究与实现.计算机工程与应用,2004,40(13).143-146
[43]刘妹,李成忠.网络自动拓扑发现算法的研究与设计.计算机应用研究.2002,19(2).51-53
[44]Froom.R, Sivasubramanian.B, Frahim. E. Building Cisco Multilayer Switched Networks(BSMSN). Second Edition. 人民邮电出版社.2004,11.305-308
[45]IEEE 802.1d-1998. Part 3:Media Access Control (MAC) bridges. ANSI/IEEE Std.802.ID.1998 edition.1998.
[46]赵小蓉,吕斌,宋凯.基于SNMP网络管理协议的MIB库分析及存取实现.电脑开发与应用.2001,14(7).39-40,43
[47]刘玉华,肖德宝等.园区网络自动拓扑发现显示系统的设计与实现.计算机应用.2003,23(11).56-58,114
[48]瞿宏阳.层次式网络拓扑显示方法的设计与Web实现.微电子学与计算机.2002,19(4).60-62
[2]Case.J, Fedor.M, Schoffstall.M, et al.A Simple Network Management Protocol (SNMP). RFC 1157.1990,5
[3]Mansfield.G, Ouchi.M, Jayanthi.K et al. Techniques for automated Network Map Generation using SNMP. IEEE INFOCOM'96.1996,3,473-480
[4]张宏莉,方滨兴,胡铭曾等. Internet测量与分析综述.软件学报.2003,14(1).110-116.
[5]Donnet.B, Raoult.P, Friedman.T, et al. Efficient Algorithms for Large-Scale Topology Discovery. ACM SIGMETRICS 2005.2005,6,33(1).327-338
[6]Donnet.B, Raoult.P, Friedman.T, et al. Improved Algorithms for network topology discovery. Springer Berlin Heidelberg.2005,149-162
[7]Govindan.R, Tangmunarunkit.H. Heuristics for Internet map Discovery. IEEE INFOCOM 2000.1371-1380
[8]Siamwalla.R, Sharma.S. Discovering Internet Topology[EB/OL]. http://www.cs.comell.edu/skeshav/papers/discovery.pdf
[9]韩涛,毕于深,刘峰.网络拓扑发现算法设计.抚顺石油学院学报.2003,23(4).72-74.
[10]蔡伟鸿,舒兆港,刘震.基于SNMP协议的以太网拓扑自动发现算法研究计算机工程与应用.2005,41(14).156-160
[11]叶小涛,魏海平,王福威等.基于SNMP的网络拓扑发现研究与实现.石油化工高等学校学报.2005,9,18(3).82-86
[12]Bierman.A, Jones.K. Physical topology MIB. RFC2922.2000,9
[13]Breitbart.Y, Garofalakis.M, Martin.C, et al. Topology discovery in heterogeneous IP networks. INFOCOM 2000.265-274
[14]Breitbart.Y, Garofalakis.M, Jai.B, et al. Topology discovery in heterogeneous IP networks:The Netlnventory system. IEEE/ACM Transaction on Networking.2004,6,12 (3).401-414
[15]郑海,张国清.物理拓扑发现算法的研究.计算机研究与发展.2002,39(3).264-268
[16]Bejerano.Y, Breitbart.Y, Garofalakis.M, et al. Physical topology discovery for large multisubnet networks. IEEE INFOCOM 2003.342-352
[17]Bruce Lowekamp, David R.O'Hallaron, Thomas R.Gross. Topology discovery for large ethernet networks. ACM SIGCOMM 2001.237-248
[18]Yantao Sun, Zhiqiang Shi, Zhimei Wu. A Discovery Algorithm for Physical Topology in Switched Networks. Proceedings of the IEEE Conference on Local Computer Networks.2005,11.311-317
[19]Black.R, Donnelly.A, Fournet.C. Ethernet topology discovery without network assistance. Proceedings of the 12th IEEE International Conference on Network Protocols(ICNP).2004,10.328-339
[20]Son.MH, Joo.BS, Kim.BC, et al. Physical topology discovery for metro ethernet networks. ETRI Journal.2005,8,27(4).355-366
[21]Tao Li, Zhiqiang Shi, Zhimei Wu. Discovering layer-2 topology in bridged local area networks. Computer Science.2003,30(12).6-8,15
[22]郭瑜茹,张斌,石冰心VLAN拓扑发现算法研究.计算机研究与发展.1999,36(6).745-750
[23]Astic.I, Festor.O. A Hierarchical Topology Discovery Service for IPv6 Networks. IEEE/IFIP Network Operations and Management Symposium 2002.497-510
[24]李琳,李杰.基于SNMP的网络拓扑发现算法.计算机工程与设计.2008,3,29(6).1345-1347
[25]R.Siamwalla, R.Sharma, S.Keshav. Discovering Internet Topology.IEEE INFOCOM'99.567-570
[26]Hwa-chun Lin, Shou-chuan Lai, Ping-wen Chen. An algorithm for automatic topology discovery of ip networks. IEEE ICC'98.1192-1196
[27]J.Schonwalder, H. Langendorger. How to keep Track of Your Network Configuration. Proc.7th Conference on Large Installation System Administration (LISA Ⅶ).1993,11.101-105
[28]H.Burch, B.Cheswick. Internet watch:Mapping the Internet. Computer. 1999,4,32(4).97-98
[29]谢希仁.计算机网络.第5版.电子工业出版社.2008,1.140-143
[30]J.Case, K.McCloghrie, M.Rose. Structure of Management Information for Version 2 of the Simple Network Management Protocol(SNMP v2). RFC1902.1996,1
[31]J.Galvin, K.McCloghrie. Administrative Model for version 2 of the Simple Network Management Protocol(SNMP v2). RFC 1445.1993,4
[32]K.McCloghrie, M.Rose. Management Information Base for Network Management of TCP/IP-based internets:MIB-Ⅱ. RFC 1213.1991,5
[33]E.Decker. Definitions of Managed Objects for Bridges. RFC1493.1993,7
[34]谢晓燕,赵婧如,马素刚.网络安全与管理实验教程.西安电子科技大学出版社.2008,8.250-251
[35]凌军,曹阳,李莉等.基于ARP和SNMP的网络拓扑自动发现算法.2001,47(1).67-70
[36]郑洪方,王玉峰,王光兴等.基于IP网络的物理拓扑自动发现算法.小型微型计算机系统.2006,27(1).17-21.
[37]刘亚莉,孙亚民.基于SNMP的网络拓扑结构自动发现研究.微型机与应用.2004,23(4).28-31
[38]李可,薛质,铁玲.IP网络拓扑自动发现研究.计算机工程.2004,30(5).66-68,187
[39]由维昭,刘强,韦卫等.多方位网络拓扑发现的通用算法与技术实现.计算机应用研究.2004,21(12).257-261
[40]邱建林,何鹏.一种改进的网络拓扑发现方法.计算机应用.2005,25(4).891-893
[41]R.Braden. Requirements for Internet Hosts-Communication Layers. RFC1122. 1989,10
[42]张伟明,罗军勇等.网络拓扑发现中的路由器别名识别技术研究与实现.计算机工程与应用,2004,40(13).143-146
[43]刘妹,李成忠.网络自动拓扑发现算法的研究与设计.计算机应用研究.2002,19(2).51-53
[44]Froom.R, Sivasubramanian.B, Frahim. E. Building Cisco Multilayer Switched Networks(BSMSN). Second Edition. 人民邮电出版社.2004,11.305-308
[45]IEEE 802.1d-1998. Part 3:Media Access Control (MAC) bridges. ANSI/IEEE Std.802.ID.1998 edition.1998.
[46]赵小蓉,吕斌,宋凯.基于SNMP网络管理协议的MIB库分析及存取实现.电脑开发与应用.2001,14(7).39-40,43
[47]刘玉华,肖德宝等.园区网络自动拓扑发现显示系统的设计与实现.计算机应用.2003,23(11).56-58,114
[48]瞿宏阳.层次式网络拓扑显示方法的设计与Web实现.微电子学与计算机.2002,19(4).60-62