网络拓扑发现技术的研究
|
摘要
在网络管理中,网络拓扑信息是其它所有管理功能的基础。如何高完备性、高准确性、高效率地快速自动发现并获取网络拓扑信息是当今各网络研究机构共同关注的问题。本论文重点从网络层拓扑发现和数据链路层拓扑发现两级进行研究。
关于网络层拓扑发现的工作,首先通过分析现有的基于ICMP、DNS、OSPF、SNMP的算法,总结了各自的优缺点和适用范围。然后通过深入学习MIB,对传统SNMP算法的不足提出了改进。通过合并路由器的多个IP地址,引入哈希链表数据结构,限制拓扑发现的范围,从而准确并高效地发现网络中的主干拓扑结构。
链路层拓扑发现中的关键是发现交换机到交换机之间的连接关系。在对链路层进行拓扑发现的研究工作中,先是通过研究现有的链路层拓扑发现算法,引入了路径集合的形式,利用各路径集合相对独立的特点执行多线程并发,进而提出了一种基于路径集合的AFT链路层拓扑发现改进算法。该算法大大提高了拓扑发现的效率,并且不要求各个网桥FDB表的信息是完备的,但不能处理不支持生成树协议交换机的连接。针对这个不足,通过结合基于网桥转发表和基于网桥生成树两种算法的优点,提出了一种新的链路层拓扑发现算法。在网络中存在不可网管交换机或HUB的情况下该算法都能很好的发现子网中交换机与交换机、交换机与主机之间的连接关系,得到完整、正确的拓扑连接图,较之已有的拓扑发现算法具有更好的适用性、准确性和效率。
In the network management system, network topology information is the foundation of other functions. It is a common issue for those network institutes to automatically discover and obtain network topology information with completeness, accuracy and efficiency. This paper focuses on the study of various network topology discovery algorithms, which are divided into two parts: network layer topology discovery and link layer topology discovery.
On the study of network layer topology discovery, we introduce the current network layer topology discovery methods: algorithms base on ICMP、DNS、OSPF、SNMP. In view of the shortage of SNMP, we studied MIB, and bring up the corresponding solution. By merging IP address, introducing data structure such and limiting the scope of topology discovery, we can accurately and efficiently discover the connections between routers and subnets.
The key of the link layer topology discovery in the 2nd layer is to find links between switches and switches. On the study of link layer topology discovery, we analyze the current link layer topology discovery algorithm. In order to improve the imperfect, a novel algorithm for data link layer topology discovery based on Address Forwarding Table is proposed. The form of path set is introduced into this algorithm. Based on the relatively independent characteristic of path set, it carries out the multi-threaded to be concurrent. This algorithm improves the efficiency and does not require the information of each bridge FDB table to be complete. But it can't find equipments that do not support SNMP such as dump switches. Aiming at this insufficiency, the physical topology discovery algorithm was analyzed and compared relying on standard SNMP MIB FDB and the algorithm relying on STP information in the first place. Then a new algorithm for discovering Ethernet topology was presented, which had the advantages of the two algorithms. This algorithm can find the connections between switch and switch switch and host, even though there exists switch or HUB which does not support SNMP protocol in the sub network. And then it can obtain intact and correct topology connection graph. Compared with the existing topology discovery algorithm, the algorithm which we propose has better applicability, veracity and efficiency.
关于网络层拓扑发现的工作,首先通过分析现有的基于ICMP、DNS、OSPF、SNMP的算法,总结了各自的优缺点和适用范围。然后通过深入学习MIB,对传统SNMP算法的不足提出了改进。通过合并路由器的多个IP地址,引入哈希链表数据结构,限制拓扑发现的范围,从而准确并高效地发现网络中的主干拓扑结构。
链路层拓扑发现中的关键是发现交换机到交换机之间的连接关系。在对链路层进行拓扑发现的研究工作中,先是通过研究现有的链路层拓扑发现算法,引入了路径集合的形式,利用各路径集合相对独立的特点执行多线程并发,进而提出了一种基于路径集合的AFT链路层拓扑发现改进算法。该算法大大提高了拓扑发现的效率,并且不要求各个网桥FDB表的信息是完备的,但不能处理不支持生成树协议交换机的连接。针对这个不足,通过结合基于网桥转发表和基于网桥生成树两种算法的优点,提出了一种新的链路层拓扑发现算法。在网络中存在不可网管交换机或HUB的情况下该算法都能很好的发现子网中交换机与交换机、交换机与主机之间的连接关系,得到完整、正确的拓扑连接图,较之已有的拓扑发现算法具有更好的适用性、准确性和效率。
In the network management system, network topology information is the foundation of other functions. It is a common issue for those network institutes to automatically discover and obtain network topology information with completeness, accuracy and efficiency. This paper focuses on the study of various network topology discovery algorithms, which are divided into two parts: network layer topology discovery and link layer topology discovery.
On the study of network layer topology discovery, we introduce the current network layer topology discovery methods: algorithms base on ICMP、DNS、OSPF、SNMP. In view of the shortage of SNMP, we studied MIB, and bring up the corresponding solution. By merging IP address, introducing data structure such and limiting the scope of topology discovery, we can accurately and efficiently discover the connections between routers and subnets.
The key of the link layer topology discovery in the 2nd layer is to find links between switches and switches. On the study of link layer topology discovery, we analyze the current link layer topology discovery algorithm. In order to improve the imperfect, a novel algorithm for data link layer topology discovery based on Address Forwarding Table is proposed. The form of path set is introduced into this algorithm. Based on the relatively independent characteristic of path set, it carries out the multi-threaded to be concurrent. This algorithm improves the efficiency and does not require the information of each bridge FDB table to be complete. But it can't find equipments that do not support SNMP such as dump switches. Aiming at this insufficiency, the physical topology discovery algorithm was analyzed and compared relying on standard SNMP MIB FDB and the algorithm relying on STP information in the first place. Then a new algorithm for discovering Ethernet topology was presented, which had the advantages of the two algorithms. This algorithm can find the connections between switch and switch switch and host, even though there exists switch or HUB which does not support SNMP protocol in the sub network. And then it can obtain intact and correct topology connection graph. Compared with the existing topology discovery algorithm, the algorithm which we propose has better applicability, veracity and efficiency.
引文
[1]STALLINGS W.SNMP网络管理.北京:中国电力出版社,2001
[2]杨家海,任宪坤,王沛瑜.网络管理原理与实现技术.北京:清华大学出版社,2000
[3]白彩英.计算机网络管理系统设计与实现.北京:清华大学出版社,1998
[4]D.Schenkel,M.Slavitch,andN.Dawes.Method of determining topology of a network of objects which compares the similarity of the traffic sequences/volumes of a pair of devices.U.S.Patent 5,926,462,July 20,1999
[5]R.Siamwalla,R.Sharma,and S.Keshav.Discovering Internet Topology.http://www.cs.cornell.edu/skeshav/papers/discovery.pdf,1999
[6]J.D.Case,M.Fedor,M.Schoffstall,J.Davin.A Simple Network Management Protocol (SNMP).RFC 1157,1990.5
[7]K.McCloghrie,M.Rose.Management Information Base for Network Management of TCP/IP-based internets:MIB-Ⅱ.RFC 1213,1991.5
[8]R.Govindan,H.Tangmunartmkit.Heuristics for Internet Map Discovery.Proceedings of IEEE INFOCOM,2000,1371-1380
[9]李延冰,马跃,王博等.IEEE三种生成树技术的分析与比较.计算机应用,2005,25(11):2499-2501
[10]Hwa-Chun Lin,Hsin_Liang Lai,Shou-Chuan Lai.Automatic Link layer Topology Discovery of IP Networks.IEEE ICC'99,1999.6
[11]E.Decker.Definitions of Managed Objects for Bridges.RFC 1493,1993.7
[12]Bruce Lowekamp,David R.O'Hallaron D R,Gross T R.Topology Discovery for Large Ethernet Networks,New York:ACM Press,2000:237-248.
[13]郑海,张国清,李鸿和.一种基于构件技术实现物理网络拓扑发现的方法.计算机工程与应用,2002,10:143-145
[14]Y.Breitbart,M.Garofalakis,C.Martin,et al.Topology discovery in heterogeneous IP networks.IEEE INFOCOM 2000,2000.3
[15]Y.Breitbart,M.Garofalakis,B.Jai.Topology Discovery in Heterogeneous IP Networks:The Netlnventory System.IEEE/ACM Trans.Networking,2004,12(3):401-404
[16]Simon Znaty,Jean Sclavos.Annotated Bibliography on Network Management.Computer Communication Review,January 1994,24(1):37-56
[17]郑海,张国清.物理网络拓扑发现算法的研究.计算机研究与发展,2002,39(3):264-268
[18]Simon Znaty,Jean Sclavos.Annotated.Network Management Viewpoints A New Way of Encompassing the Network Management Complexity.Computer Communication Review,January 1994,24(3):63-79
[19]ISO 10040.Information Processing Systems-Open Systems Interconnection-Systems Management Overview,Geneva,1992
[20]沈俊,顾冠群,罗军舟.网络管理的研究和发展.计算机研究与发展,2002(10):1153-1167
[21]J.Case,M.Rose,K.McCloghrie.Structure and Identification of Management Information for TCP/IP-based Intemets.RFC 1155,1990.5
[22]M.Rose,K.McCloghrie.Concise MIB Definitions.RFC 1212,1991.5
[23]M.Rose,K.McCloghrie.Management information base for network management of TCP/IP-based Internets:MIB-Ⅱ,IETF,Internet RFC 1213,1991,5
[24]J.Case,M.Rose,K.McCloghrie,S.Waldbusser.Management Information Base for Version 2 of the Simple Network Management Protocol(SNMPv2).RFC 1907,1996.1
[25]李涛.基于SNMP的网管系统中拓扑管理的研究与实现:[硕士论文].北京:中国科学院软件研究所,2003
[26]J.D.Case,M.Fedor,M.Schoffstall,et al.A Simple Network Management Protocol (SNMP).RFC 1157,1990.5
[27]J.Case,M.Rose,K.McCloghrie.Structure of Management Information for Version 2 of the Simple Network Management Protocol(SNMP v2).RFC 1902,1996.1
[28]J.Galvin,K.McCloghrie.Administrative Model for version 2 of the Simple Network Management Protocol(SNMPv2).RFC 1445,1993.4
[29]William Stallings,胡成松,汪凯.SNMP网络管理.北京:中国电力出版社,2001.9
[30]J.Case,M.Rose,K.McCloghrie.Protocol Operations for Version 2 of theSimple Network Management Protocol(SNMPv2).RFC 1905,1996.1
[31]杨国正,陆余良,夏阳.计算机网络拓扑发现技术研究.计算机工程与设计,2006,27(24):4710-4712
[32]杨安义,朱华清,王继龙.一种改进的基于SNMP的网络拓扑发现算法及实现.计算机应用,2007,27(10):2412-2413
[33]W.Richard Stevens著,范建华译.TCP/IP详解卷1:协议.北京:机械工业出版社,2000
[34]Eastlake D.RFC2541,DNS Operational Security Considerations.1999
[35]黄晓波.网络拓扑发现的算法研究与实现:[硕士论文].杭州:浙江大学,2006
[36]徐大海,黄健强,吴克喜,等.基于OSPF的网络拓扑搜索.计算机工程与科学, 1999(6):17-21
[37]陈锦葵.网络管理系统中拓扑发现算法的研究:[硕士论文].西安:西安电子科技大学,2007
[38]刘妹,李成忠.网络自动拓扑发现算法的研究与设计.计算机应用研究,2001(2):51-53
[39]刘玉华,余胜生,周敬利.基于AFT的链路层自动拓扑发现算法小型微型计算机系统,2004,25(12):2211-2214
[40]Liam B.Quinn,Richard G.Russell著.邝坚,龚向阳,刘晓梅译.快速以太网.北京:人民邮电出版社,1999
[41]吴功宜,吴英著.计算机网络应用技术教程.北京:清华大学出版社,2002
[42]E.Decker,P.Langille,A.Rijsinghani,et al.Definitions of Managed Objects for Bridges.RFC 1493,1993.7
[43]ANS/IEEE Standard 802.1D-1990,MAC Bridges,IEEE Project 802 Local and Metropolitan Area Networks March 8,1991
[44]赵文光.网络冗余链路管理的实现.中国教育网络,2006(7):58-59
[45]郭彦伟,郑建德.生成树协议与交换网络环路研究.厦门大学学报(自然科学版),2006,5(45):301-304
[46]李延冰,马跃,王炜等.基于生成树的链路层拓扑发现算法.计算机工程,2006,32(18):109-113
[47]王震宇,马晓军,蒋烈辉.STP协议与生成树设计优化.信息工程大学学报,2003,3(4):66-68
[48]E.Decker.Definitions of Managed Objects for Bridges.RFC 1493,1993.7
[49]邱林,张建忠,吴功宜.基于端口流量的物理网络拓扑发现方法研究.计算机工程与应用,2002,22:171-172
[50]Brace L.Discovery and application of network information.Pittsburgh,PA:School of Computer Science,Carnegie Mellon University,2001
[51]Computer Science,Carnegie Mellon University,2001 Y Breitbart,M Garofalak is,C Martin et al.Topology discovery in heterogeneous IP networks.In:Proc of IN FOCOM2000.Tel Aviv Israel,2000
[52]Bruce Lowekamp.Discovery and application of network information[Ph D dissertation].School of Computer Science Carnegie Mellon University,Pittsburgh,PA,2001
[53]张国强,张国清,李仰耀.物理网络拓扑发现算法的研究和系统实现.小型微型计算机系统,2006,27(1):12-16
[54]杨丽娜.物理层网络拓扑自动发现算法研究:[硕士论文].杭州:浙江大学,2007
[55]黄锦亮,杜旭.基于SNMP的以太网拓扑发现.计算机应用,2006,26(1):37-39
[56]孙延涛,吴志美,石志强.基于地址转发表的交换式以太网拓扑发现方法.软件学报,2006,17(12):2565-2576
[57]李波,杨松龄,赵文娟.数据链路层拓扑发现算法的研究.计算机工程与设计,2004,25(10):1738-1741
[58]郑洪方,王玉峰,王光兴等.基于IP网络的物理拓扑自动发现算法.小型微型计算机系统,2006,27(1):17-21
[59]戴曙君.基于SNMP综合网络管理系统数据采集模块的设计和实现:[硕士论文].长沙:国防科学技术大学,2007
[60]董宏亮,杨英杰,姜增良.网络拓扑自动发现系统的设计与实现.计算机应用,2007,27(7):1587-1590
[2]杨家海,任宪坤,王沛瑜.网络管理原理与实现技术.北京:清华大学出版社,2000
[3]白彩英.计算机网络管理系统设计与实现.北京:清华大学出版社,1998
[4]D.Schenkel,M.Slavitch,andN.Dawes.Method of determining topology of a network of objects which compares the similarity of the traffic sequences/volumes of a pair of devices.U.S.Patent 5,926,462,July 20,1999
[5]R.Siamwalla,R.Sharma,and S.Keshav.Discovering Internet Topology.http://www.cs.cornell.edu/skeshav/papers/discovery.pdf,1999
[6]J.D.Case,M.Fedor,M.Schoffstall,J.Davin.A Simple Network Management Protocol (SNMP).RFC 1157,1990.5
[7]K.McCloghrie,M.Rose.Management Information Base for Network Management of TCP/IP-based internets:MIB-Ⅱ.RFC 1213,1991.5
[8]R.Govindan,H.Tangmunartmkit.Heuristics for Internet Map Discovery.Proceedings of IEEE INFOCOM,2000,1371-1380
[9]李延冰,马跃,王博等.IEEE三种生成树技术的分析与比较.计算机应用,2005,25(11):2499-2501
[10]Hwa-Chun Lin,Hsin_Liang Lai,Shou-Chuan Lai.Automatic Link layer Topology Discovery of IP Networks.IEEE ICC'99,1999.6
[11]E.Decker.Definitions of Managed Objects for Bridges.RFC 1493,1993.7
[12]Bruce Lowekamp,David R.O'Hallaron D R,Gross T R.Topology Discovery for Large Ethernet Networks,New York:ACM Press,2000:237-248.
[13]郑海,张国清,李鸿和.一种基于构件技术实现物理网络拓扑发现的方法.计算机工程与应用,2002,10:143-145
[14]Y.Breitbart,M.Garofalakis,C.Martin,et al.Topology discovery in heterogeneous IP networks.IEEE INFOCOM 2000,2000.3
[15]Y.Breitbart,M.Garofalakis,B.Jai.Topology Discovery in Heterogeneous IP Networks:The Netlnventory System.IEEE/ACM Trans.Networking,2004,12(3):401-404
[16]Simon Znaty,Jean Sclavos.Annotated Bibliography on Network Management.Computer Communication Review,January 1994,24(1):37-56
[17]郑海,张国清.物理网络拓扑发现算法的研究.计算机研究与发展,2002,39(3):264-268
[18]Simon Znaty,Jean Sclavos.Annotated.Network Management Viewpoints A New Way of Encompassing the Network Management Complexity.Computer Communication Review,January 1994,24(3):63-79
[19]ISO 10040.Information Processing Systems-Open Systems Interconnection-Systems Management Overview,Geneva,1992
[20]沈俊,顾冠群,罗军舟.网络管理的研究和发展.计算机研究与发展,2002(10):1153-1167
[21]J.Case,M.Rose,K.McCloghrie.Structure and Identification of Management Information for TCP/IP-based Intemets.RFC 1155,1990.5
[22]M.Rose,K.McCloghrie.Concise MIB Definitions.RFC 1212,1991.5
[23]M.Rose,K.McCloghrie.Management information base for network management of TCP/IP-based Internets:MIB-Ⅱ,IETF,Internet RFC 1213,1991,5
[24]J.Case,M.Rose,K.McCloghrie,S.Waldbusser.Management Information Base for Version 2 of the Simple Network Management Protocol(SNMPv2).RFC 1907,1996.1
[25]李涛.基于SNMP的网管系统中拓扑管理的研究与实现:[硕士论文].北京:中国科学院软件研究所,2003
[26]J.D.Case,M.Fedor,M.Schoffstall,et al.A Simple Network Management Protocol (SNMP).RFC 1157,1990.5
[27]J.Case,M.Rose,K.McCloghrie.Structure of Management Information for Version 2 of the Simple Network Management Protocol(SNMP v2).RFC 1902,1996.1
[28]J.Galvin,K.McCloghrie.Administrative Model for version 2 of the Simple Network Management Protocol(SNMPv2).RFC 1445,1993.4
[29]William Stallings,胡成松,汪凯.SNMP网络管理.北京:中国电力出版社,2001.9
[30]J.Case,M.Rose,K.McCloghrie.Protocol Operations for Version 2 of theSimple Network Management Protocol(SNMPv2).RFC 1905,1996.1
[31]杨国正,陆余良,夏阳.计算机网络拓扑发现技术研究.计算机工程与设计,2006,27(24):4710-4712
[32]杨安义,朱华清,王继龙.一种改进的基于SNMP的网络拓扑发现算法及实现.计算机应用,2007,27(10):2412-2413
[33]W.Richard Stevens著,范建华译.TCP/IP详解卷1:协议.北京:机械工业出版社,2000
[34]Eastlake D.RFC2541,DNS Operational Security Considerations.1999
[35]黄晓波.网络拓扑发现的算法研究与实现:[硕士论文].杭州:浙江大学,2006
[36]徐大海,黄健强,吴克喜,等.基于OSPF的网络拓扑搜索.计算机工程与科学, 1999(6):17-21
[37]陈锦葵.网络管理系统中拓扑发现算法的研究:[硕士论文].西安:西安电子科技大学,2007
[38]刘妹,李成忠.网络自动拓扑发现算法的研究与设计.计算机应用研究,2001(2):51-53
[39]刘玉华,余胜生,周敬利.基于AFT的链路层自动拓扑发现算法小型微型计算机系统,2004,25(12):2211-2214
[40]Liam B.Quinn,Richard G.Russell著.邝坚,龚向阳,刘晓梅译.快速以太网.北京:人民邮电出版社,1999
[41]吴功宜,吴英著.计算机网络应用技术教程.北京:清华大学出版社,2002
[42]E.Decker,P.Langille,A.Rijsinghani,et al.Definitions of Managed Objects for Bridges.RFC 1493,1993.7
[43]ANS/IEEE Standard 802.1D-1990,MAC Bridges,IEEE Project 802 Local and Metropolitan Area Networks March 8,1991
[44]赵文光.网络冗余链路管理的实现.中国教育网络,2006(7):58-59
[45]郭彦伟,郑建德.生成树协议与交换网络环路研究.厦门大学学报(自然科学版),2006,5(45):301-304
[46]李延冰,马跃,王炜等.基于生成树的链路层拓扑发现算法.计算机工程,2006,32(18):109-113
[47]王震宇,马晓军,蒋烈辉.STP协议与生成树设计优化.信息工程大学学报,2003,3(4):66-68
[48]E.Decker.Definitions of Managed Objects for Bridges.RFC 1493,1993.7
[49]邱林,张建忠,吴功宜.基于端口流量的物理网络拓扑发现方法研究.计算机工程与应用,2002,22:171-172
[50]Brace L.Discovery and application of network information.Pittsburgh,PA:School of Computer Science,Carnegie Mellon University,2001
[51]Computer Science,Carnegie Mellon University,2001 Y Breitbart,M Garofalak is,C Martin et al.Topology discovery in heterogeneous IP networks.In:Proc of IN FOCOM2000.Tel Aviv Israel,2000
[52]Bruce Lowekamp.Discovery and application of network information[Ph D dissertation].School of Computer Science Carnegie Mellon University,Pittsburgh,PA,2001
[53]张国强,张国清,李仰耀.物理网络拓扑发现算法的研究和系统实现.小型微型计算机系统,2006,27(1):12-16
[54]杨丽娜.物理层网络拓扑自动发现算法研究:[硕士论文].杭州:浙江大学,2007
[55]黄锦亮,杜旭.基于SNMP的以太网拓扑发现.计算机应用,2006,26(1):37-39
[56]孙延涛,吴志美,石志强.基于地址转发表的交换式以太网拓扑发现方法.软件学报,2006,17(12):2565-2576
[57]李波,杨松龄,赵文娟.数据链路层拓扑发现算法的研究.计算机工程与设计,2004,25(10):1738-1741
[58]郑洪方,王玉峰,王光兴等.基于IP网络的物理拓扑自动发现算法.小型微型计算机系统,2006,27(1):17-21
[59]戴曙君.基于SNMP综合网络管理系统数据采集模块的设计和实现:[硕士论文].长沙:国防科学技术大学,2007
[60]董宏亮,杨英杰,姜增良.网络拓扑自动发现系统的设计与实现.计算机应用,2007,27(7):1587-1590