摘要
随着计算机网络技术的发展,网络规模不断扩大,复杂性不断增加,网络的异构性越来越高,计算机网络管理技术也成为一个非常重要的研究课题。网络自动拓扑发现作为网络管理的一部分有着重要的研究意义。除了网络管理以外,网络自动拓扑发现还有许多新的应用领域比如服务器定位、网络规划等。
目前的网络自动拓扑发现多采用基于路由表的网络层拓扑发现算法。然而,由于交换机等数据链路层设备越来越多地分布在IP网络中形成子网段,越来越多的网络结构对于网络层拓扑发现是不可见的,使得现有的网络层拓扑发现算法远远不能满足实际需求。数据链路层拓扑发现也因此成为一个网络自动拓扑发现系统不可缺少的部分。一些特有的困难使得数据链路层拓扑发现研究远远滞后于网络层拓扑发现,因而,也成为近些年来网络自动拓扑发现方面的一个研究热点和难点。
本文首先对当前数据链路层自动拓扑发现的研究现状进行详细分析,指出现有的数据链路层拓扑发现方法在通用性、完整性等方面不够完善。论文系统地总结了基于地址转发表的发现方法和基于生成树协议的发现方法各自的实现原理,比较了它们存在的不足,提出了综合地址转发表和生成树协议的拓扑发现算法,有效解决了冗余连接的发现问题。
在论文的算法实现中,引入了边缘交换机的概念,把数据链路层拓扑发现分为交换机网络发现和主机网络发现,简化了拓扑发现过程。论文设计了一种拓扑显示方案,解决了拓扑图显示的抖动问题,采用虚拟交换机的概念使得拓扑显示更具有层次性。
论文独立开发了一个数据链路层拓扑发现原型系统,验证了本文所提出的算法,可作为数据链路层拓扑发现进一步研究的基础。
实验证明,本文提出的数据链路层拓扑发现算法在单子网管理域环境中具有很好的效果。下一步的研究工作将针对多子网管理域和采用虚拟局域网技术的网络,并进一步探讨本文提出的算法与网络层拓扑发现算法的无缝衔接。
With the development of computer network technologies, the scale of computer networks is getting bulky and complex and the heterogeneity of networks is getting higher and higher. The technique of network management has also become a very important issue. Network automatic topology discovery as an important part of network management has special research significance. In addition to network management, network automatic topology discovery can be used in many new application areas such as server locating, network planning, etc.
At present, most of the network automatic topology discovery algorithms are developed to discover IP layer topology based on routing tables obtained from SNMP. But, more and more data-link layer devices as switches are deployed in IP networks. Such devices become subnet segmentation. Thus, more and more network infrastructures are invisible to a layer-3 mapping, so present layer-3 network automatic topology discovery algorithm can’t satisfy network management requirement. The data-link layer topology discovery becomes an indispensable part of a network automatic topology discovery system. Some unique difficulties of data-link layer topology discovery make it fall behind the research of layer-3 network automatic topology discovery. So, it has become the focus and difficulty of the research on network automatic topology discovery.
In this thesis the current achievements of data-link layer topology discovery are analyzed in detail, their shortages in popularity and integrity are indicated. The implementation of discovery based on address forwarding tables and spanning tree protocol is systematically summed up. Respective deficiencies of the two algorithms are compared. A new data-link layer topology discovery algorithm integrating the above two methods is proposed. The new algorithm can discover redundant physical connections.
In the implementation of the algorithm, the concept of edge switch is introduced. So the data-link layer topology discovery is divided into switches network topology discovery and hosts network topology discovery. Thus, the topology discovery process is simplified. Meanwhile a design of topology map display is presented, in which the map jitter problem was solved. The application of virtual switch makes the topology map more hierachical.
A data-link topology discovery prototype system is developed for research. The feasibility of the data-link topology discovery algorithm presented in this paper was fully verified by the prototype system.
The final test results show that the data-link layer automatic topology discovery algorithm designed in this paper worked well in single subnet management domain. The further research work will be the topology discovery in multi-subnet management domain and the topology discovery in virtual local area network. Besides, how to combine presented algorithm together with IP layer topology discovery is also a challenging issue.
引文
[1] Miniwatts Marketing Group. World Internet Usage Statistics News and World Population Stats. http://www.internetworldstats.com/stats.htm,2008-3
[2]中国互联网络信息中心.中国互联网发展状况统计报告. http://www.cnnic.cn/uploadfiles/pdf/2008/1/17/104156.pdf,2008-1
[3] Simon Znaty,Jean Sclavos. Annotated Bibliography on Network Management[J]. Computer Communication Review,1994, 24(1):37-56
[4] Simon Znaty, Jean Sclavos. Network Management Viewpoints: A New Way of Encompassing the Network Management Complexity[J]. Computer Communication Review,1994, 24(3):63-79
[5]徐大海,刘新,王奇等.网络拓扑自动发现自动算法的研究[J].计算机应用,1999,19 (2):4-6
[6] R.Siamwalla, R.Sharma, and S.Keshav. Discovering Internet Topology. http://www.cs.cornell.edu/skeshav/papers/discovery.pdf,1999
[7] Kc.Claffy. Internet measurement and data analysis: topology, workload, performance and routing statistics. http://www.caida.org/Papers/Nae,1999
[8] C.Faloutsos, M.Faloutsos, and P. Faloutsos. What does Internet look like? Empirical Laws of the Internet Topology[J]. ACM SIGCOMM,1999, 48(5):411-426
[9]沈俊,顾冠群,罗军舟.网络管理的研究和发展[J].计算机研究与发展,2002 (10):1153-1167
[10]凌军,曹阳,李莉等.基于ARP和SNMP的网络拓扑自动发现算法[J].武汉大学学报,2001 (1 ):67-70
[11]谢希仁.计算机网络(第四版)[M].北京:电子工业出版社,2003: 302-314
[12]刘珠,李成忠.网络自动拓扑发现算法的研究与设计[J].计算机应用研究, 2001 (2):51-53
[13] J. Schonwalder, H. Langedorfer. How to Keep Track of Your Network Configuration. In: Proceedings of the the 1993 LISA VII Conference. Monterey, California 1993, 101-105
[14] G.Mansfield, M.Ouchi, K.Jayanthi, et al. Techniques for Automated Network Map Generation Using SNMP[J]. IEEE INFOCOM, 1996: 473-480
[15] Hwa-Chun Lin, Shou-Chuan Lai, and Ping-Wen Chen. An Algorithm for Automatic Topology Discovery of IP Networks. In: Proc of IEEE ICC, 1998: 857-862
[16] HP’s OpenView. Insight Integration for HP OpenView Network Node Manager.http://h18013.www1.hp.com/products/servers/management/openview/index.html? jumpid=reg_R1002_USEN, 2007
[17] IBM’s Tivoli. IBM Tivoli NetView. http://www-306.ibm.com/software/sysmgmt/products/support/IBMTivoliNetView.html,2008
[18] Dartmouth University. Intermapper: An intranet mapping and snmp monitoring program for the macintosh. http://www.dartware.com/intermapper/, 2007
[19] K.Obraczka and G. Gheorghiu. The performance of a service for network-aware applications. In: Proceedings of the ACM Sigmetrics SPDT’98,1998,107-114
[20] P. Francis, S.Jamin, C.Jin, et al. IDMAPs: A Global Internet Host Distance Estimation Service[J]. IEEE/ACM Trans On Networking, Oct 2001,32(4):562-664
[21] S.Jamin, C Jin, Y Jin, et al. On the placement of Internet instrumentation[J]. IEEE INFOCOM 2000, Tel Aviv, Israel, March 2000,63(5):301-307
[22] W. Theilmann and K.Rothermel. Dynamic distance maps of the internet[J]. IEEE INFOCOM 2000, Tel aviv Israel, March 2000,63(4):512-514
[23] Project Octopus at Cornell. Network Topology Discovery. http://www.cs.cornell.edu/cnrg/topology_aware/topology/default.html, 2005
[24] R. Govindan and H. Tangmunarunkit. Heuristics for Internet Map Discovery[J]. IEEE INFOCOM 2000, Tel Aviv, Israel, March 2000,63(13):211-215
[25] Center for Intelligent Systems of UC Berkeley. Wide-area Network Measurement and Monitoring Services. http://www.cs.berkeley.edu/~yanchen/research/wnmms/, 2000
[26] Hal Burch and Bill Cheswick. Mapping the Internet[J]. IEEE Computer, April 1999, 32(4):97-98
[27] CAIDA Web Site. Topology discovery by active probing. http://www.caida.org/publications/papers/2002/SkitterOverview/skitter_overview.pdf, 2002
[28] K.C. Claffy and D. McRobb. Measurement and Visualization of Internet Connectivity and Performance. http://www.caida.org/Tools/Skitter, 2001
[29] Cisco Systems Inc. Monitor Your Network Topology at Cisco. http://www.cisco.com/en/US/products/hw/optical/ps2011/products_configuration_guide_chapter09186a0080133db7.html, 2004
[30] Peregrine’s Infratools software. Product manual. http://www.peregrine.com/us/default.htm, 2001
[31] Micromuse Tech Inc. Micromuse’Netcool/Precision application. http://www.micromuse.com/index.html, 1999
[32] IEEE 802.1AB - 2005. IEEE Standard for Local andmetropolitan area networks Station and Media Access Control ConnectivityDiscovery. http://ieee802.org/1/pages/802.1ab.html, 2006-7-26
[33] Yuri Breibart, Minos Garofalakis, Cliff Martin, et al. Topology Discovery in Heterogeneous IP Networks[J]. IEEE INFOCOM 2000, 2000, 18(3):265-274
[34] Bruce Lowekamp, David R. O’Hallaron, and Thomas R. Gross. Topology Discovery for Large Ethernet Networks[J]. ACM SIGCOMM 2001, 2001,53(17):237-248
[35] Yigal Bejerano, Yuri Breitbart, Minos Garofalakis, et al. Physical Topology Discovery for Large Multi-Subnet Networks[J]. IEEE INFOCOM 2003, 2003, 39(2):342-352
[36]郑海,张国清.物理网络拓扑发现算法的研究[J].计算机研究与发展,2002, 39(3):264-268
[37]张国强,张国清,李仰耀.物理网络拓扑发现算法的研究和系统实现[J].小型微型计算机系统,2006,27(1):12-16
[38] Myung-Hee Son, Bheom-Soon Joo, Byung-Chul Kim, et al. Physical Topology Discovery for Metro Ethernet Networks[J]. ETRI Journal, 2005,27(4):355-366
[39]肖位枢.图论及其算法[M].北京:航空工业出版社,1993 :302-315
[40] J.Case. A Simple Network Management Protocol(SNMP)(RFC1157). http://www.faqs.org/rfcs/rfc1157.html,1990
[41]岑贤道,安常青.网络管理协议及应用开发[M].北京:清华大学出版社,1998,211-230
[42] Mark A. Miller. Managing Internetworks with SNMP(Third Edition)[M]. M & T Books, 2001,303-346
[43]林瑶,蒋慧,杜蔚轩等译.用TCP/IP进行网际互联(第1卷):原理、协议与结构(第4版)[M].北京:电子工业出版社,2003,245-260
[44]白英彩.计算机网络管理系统设计与应用[M].北京:清华大学出版社,1998,208-222
[45]莱姆勒,奎因,魏巍. CCNP:交换学习指南[M].北京:电子工业出版社,2003,206-231
[46]安恒公司. 802.1AB链路层发现协议——LLDP网络维护好助手. http://lldp.anheng.com.cn/news/html/network_administration/435.html, 2003
[47] IEEE 802.1D. Standard for Local and Metropolitan Area Networks:Media Access Control (MAC) Bridges. http://ieeexplore.ieee.org/iel5/9155/29062/01309630.pdf, 1998
[48] AdventNet, Inc. AdventNet SNMP API Release 3.3 Product Documentation. http://snmp.adventnet.com/help/snmpapi/snmpv3/javadocs/index.html, 2006
[49]谢红漫,钱德沛,栾钟治等.基于分层的网络拓扑结构可视化方法研究[J].北京航空航天大学学报,2004,30(6):529-533
[50]宋维维,陈淑珍,孙晓安. Java语言中的多线程和双缓冲技术[J].计算机工程,1998,24(12):30-31
[51]杨祎.网络自动拓扑发现研究:[华中师范大学硕士论文].武汉:华中师范大学,2005,38-41
[52] Kaihua Xu, Jiwei Cao, Yuhua Li, et al. An Algorithm of Topology Discovery in Large Multi-Subnet Physical Network. In: Proceedings of the First International Multi-Symposiums on Computer and Computational Sciences. Hangzhou,2006, 34-39
[53]郭瑜茹,张斌,石冰心. VLAN拓扑发现算法研究[J].计算机研究与发展,1999,36(6):745-750