网络拓扑发现及显示技术研究
摘要
随着IPv4协议的空间匮乏、基于IPv6协议的下一代互联网发展势在必行。但IPv4已经过了几十年的发展,并不会很快退出历史舞台,IPv4和IPv6网络势必长期共存。由于针对IPv4网络的拓扑发现方法并不能直接应用到IPv6网络中,在这种情况下,非常有必要对IPv4/IPv6混合网络的拓扑发现技术进行研究。同时,目前的拓扑布局算法由于过度追求节点和边的不重叠性,忽视了网络本身的特性,没有考虑大型网络的层次性和扩展性,导致显示的结果不够直观。如何为网络管理员提供一个直观且易操作的拓扑图也是本文的重要研究内容。
首先,本文介绍了IPv4协议和IPv6协议的结构和特点,对两种主要的过渡技术：双栈技术和隧道技术的原理进行了详细的阐述。结合前人研究的理论基础,对IPv4网络拓扑发现的常用方法和IPv6网络拓扑发现的方法进行了分类,对比了各类方法的优缺点,并对IPv6网络拓扑发现常见的问题进行了总结。在此基础上,提出了过渡时期拓扑发现的机制和关键技术解决方案,采用分布式探测的方式,形成‘主控节点-代理节点”的层次结构,利用SNMP和ICMP协议相结合的方式进行拓扑发现。同时,为了应对大型网络拓扑布局的难题,提出了一种启发式网络拓扑布局算法-ACTL,利用蚁群算法对网络节点进行聚类,再利用张力—引力模型进行布局。当网络节点发生变化时,采用拓扑重构技术减少拓扑重新绘制的时间开销。
拓扑发现和显示的技术方案确定以后,本文设计了一套针对IPv4/IPv6混合网络的拓扑管理系统。该系统在考虑混合网络拓扑发现和显示特点的基础之上进行设计,以B/S架构、模块化、分布式架构,设计出整套混合网络拓扑管理系统,完善各功能模块实现及处理流程。
最后,本文进行了系统各功能模块的实验验证。结果表明系统的功能和性能均能满足对混合网络的拓扑发现和显示需求,界面友好,具有很好的实用性和扩展性。
As address space of IPv4is exhausting, it is essential to develop the next generation internet based on IPv6protocol. However, after the development of several decades, IPv4protocol would not be discarded immediately. Both IPv4and IPv6will play important roles for a long time. Moreover, those network topology discovery methods for IPv4networks can not be readily applied to IPv6networks. It is very necessary to develop new methods that are adequate for managing a network of IPv6and IPv4co-existence. Currently the topology discovery algorithms focus on managing the overlapped hosts, hierarchical and scalability of large-scale networks are ignored. The results of these methods are not intuitive. Another important research topic considered in this paper is how to provide an intuitive and handy topology map for network administrators.
In this paper, we introduce the structure and properties of IPv4and IPv6protocol. Both dual-stack and tunnelling technology are explained in details. Then we categorise and compare methods of topology discovery existing in previous works. Some common difficulties in IPv6topology discovery are summarised. Based on these studies, we propose a distributed topology detecting method with 'main node-agent node' hierarchical structures using ICMPv6protocol. At the same time, in handling the problem of large-scale topology map, we introduce a heuristic topology discovery algorithm (ACTL). The ACTL algorithm cluster network nodes with ant-colony algorithm and configure the layout with 'tension-gravitation model'. When network nodes changes, topology reconstruction method is used to reduce computational time.
With the solutions of topology discovery and visualisation technology, we also designed a system for IPv4/IPv6co-existing networks. The system follows B/S, modular and distributed architecture, implements a complete workflow for discovering and visualising network topology.
Finally, we evaluated each functional module of the system. The results showed that the system meets the requirements of discovering and visualising the topology of networks. Meanwhile, usability and extendability of the system is carefully considered.
首先,本文介绍了IPv4协议和IPv6协议的结构和特点,对两种主要的过渡技术：双栈技术和隧道技术的原理进行了详细的阐述。结合前人研究的理论基础,对IPv4网络拓扑发现的常用方法和IPv6网络拓扑发现的方法进行了分类,对比了各类方法的优缺点,并对IPv6网络拓扑发现常见的问题进行了总结。在此基础上,提出了过渡时期拓扑发现的机制和关键技术解决方案,采用分布式探测的方式,形成‘主控节点-代理节点”的层次结构,利用SNMP和ICMP协议相结合的方式进行拓扑发现。同时,为了应对大型网络拓扑布局的难题,提出了一种启发式网络拓扑布局算法-ACTL,利用蚁群算法对网络节点进行聚类,再利用张力—引力模型进行布局。当网络节点发生变化时,采用拓扑重构技术减少拓扑重新绘制的时间开销。
拓扑发现和显示的技术方案确定以后,本文设计了一套针对IPv4/IPv6混合网络的拓扑管理系统。该系统在考虑混合网络拓扑发现和显示特点的基础之上进行设计,以B/S架构、模块化、分布式架构,设计出整套混合网络拓扑管理系统,完善各功能模块实现及处理流程。
最后,本文进行了系统各功能模块的实验验证。结果表明系统的功能和性能均能满足对混合网络的拓扑发现和显示需求,界面友好,具有很好的实用性和扩展性。
As address space of IPv4is exhausting, it is essential to develop the next generation internet based on IPv6protocol. However, after the development of several decades, IPv4protocol would not be discarded immediately. Both IPv4and IPv6will play important roles for a long time. Moreover, those network topology discovery methods for IPv4networks can not be readily applied to IPv6networks. It is very necessary to develop new methods that are adequate for managing a network of IPv6and IPv4co-existence. Currently the topology discovery algorithms focus on managing the overlapped hosts, hierarchical and scalability of large-scale networks are ignored. The results of these methods are not intuitive. Another important research topic considered in this paper is how to provide an intuitive and handy topology map for network administrators.
In this paper, we introduce the structure and properties of IPv4and IPv6protocol. Both dual-stack and tunnelling technology are explained in details. Then we categorise and compare methods of topology discovery existing in previous works. Some common difficulties in IPv6topology discovery are summarised. Based on these studies, we propose a distributed topology detecting method with 'main node-agent node' hierarchical structures using ICMPv6protocol. At the same time, in handling the problem of large-scale topology map, we introduce a heuristic topology discovery algorithm (ACTL). The ACTL algorithm cluster network nodes with ant-colony algorithm and configure the layout with 'tension-gravitation model'. When network nodes changes, topology reconstruction method is used to reduce computational time.
With the solutions of topology discovery and visualisation technology, we also designed a system for IPv4/IPv6co-existing networks. The system follows B/S, modular and distributed architecture, implements a complete workflow for discovering and visualising network topology.
Finally, we evaluated each functional module of the system. The results showed that the system meets the requirements of discovering and visualising the topology of networks. Meanwhile, usability and extendability of the system is carefully considered.
引文
[1]Neil Spring, RatuI Mahajan, David Wetherall, and Thomas Anderson. Measuring ISP Topologies With Rocketfuel[J]. IEEE/ACM TRANSACTIONS ON NETWORKING,VOL.12,NO.1.FEBRUARY 2004.
[2]http://www.cheswick.com/ches/map/.
[3]http://www.caida.org/home/.
[4]Govindan R, Tangmunarunkit H. Heuristics for Internet map discovery [A]. Proc of IEEE INFOCOM 2000[C].TelAviv, Israel, March 2000.1371-1380.
[5]姜誉.Internet路由器级拓扑测量与分析技术研究[D]：[工学博士学位论文].哈尔滨：哈尔滨工业大学,2005.
[6]张晓平.网络拓扑发现技术的研究与实现[D].北京邮电大学'2010.
[7]徐成武.IPv4/IPv6混合网络拓扑自动发现研究[D].太原理工大学,
[8]徐前方.在IPv4/v6环境下网络拓扑发现的研究与实现[J].计算机工程与设计,2006,27(23)：4507-4509.
[9]仇伟明.基于IPv6网络拓扑结构自动发现方法的研究[D].南京理工大学,2006.
[10]李元臣,刘维群,薛雷等.IPv4/IPv6混合网络中一种过渡拓扑发现技术[J].武汉理工大学学报(交通科学与工程版),2009,33(4):760-763.DOI:10.3963/j.issn.1006-2823.2009.04.039.
[11]邱雪姣.IPv4/IPv6双协议栈下网络拓扑发现的研究[D].北京信息科技大学,2008.
[12]聂世忠.IPv4/v6混合环境下网络拓扑发现的研究与实现[D].北京邮电大学,2003.
[13]陈文峰,陆际光,王娟等.基于IPv4和IPv6混合网络环境下拓扑发现算法研究[J].电脑知识与技术,2008,4(34)：1585-1587.
[14]蓝集明,符长友.IPv6-in-IPv4隧道发现技术研究[J].四川理工学院学报(自然科学版),2009,22(2)：40-42.
[15]张玉健.IPv6网络拓扑发现技术的研究与应用[D].东南大学,2010.
[16]晏弼成,宋云,莫天虎等.一种IPv4/v6网络拓扑发现新算法[J].长沙理工大学学报(自然科学版),2009,6(4)：78-84.
[17]Vasileios Giotsas,Shi Zhou.Detecting and Assessing the Hybrid IPv4/IPv6 AS Relationships[J].Computer Communication Review,2011,41(4):424-425.
[18]MEI Yu-lin,WANG Xiao-ming,CHENG Geng-dong等.Binary discrete method of topology optimization[J].应用数学和力学(英文版),2007,28(6)：707-719.
[19]YeXU,HaiZHAO.AnImprovedBAModelforRouter-levelInternetMacroscopicTopology[J].IAE NGInternationalJournalofComputerScience,2009.
[20]ClaudiaG6mezSantillan,LauraCruz-Reyes,EustorgioMeza,TaniaTurrubiatesL6pez,MarcoA.A guirreLam,FlisaSchaeffer.ImprovingDistrlbutedResourceSearchthroughaStatisticalMethodolo gyofTopologicalFeatureSelection[J].JoumalofComputers,2009.
[21]XiangyangLiang,JiaZhao.Agent-basedTopologyDiscoveryforTacticallnteraet[J] .InformationT echnologyJournal,2011.
[22]YigalBejerano.Takingtheskeletonsoutoftheclosets:asimpleandefificienttopologydiscoverysche meforlargeethemetLANs.[J].IEEE/ACMTraiis.Netw.,2009,17.
[23]BrianEriksson,GautamDasarathy,PaulBarford,RobertNowak.EfficientNetworkTomographyfo rInternetTopologyDiscovery.[J].IEEE/ACMTrans.Netw.,2012,20.
[24]BenoitDonnet,TimnrFriedman.Intemettopologydiscovery:Asurvey.[J].IEEECommunications SurveysandTutorials,2007,9.
[25]LokeshB.Bhajantri,N.Nalini.Energyawarebasedfaulttoleranceapproachfortopologycontrolindi stributedsensometworks[J]. JoumalofHighSpeedNetwotks,2012,183:.
[26]R. Rohrer , E.Swing. Web-based information visualization IEEE Computer Graphics and Applications, 1997,52-59.
[27]Eades PA heuristic for graph drawing[J].Congressus Numerantium, 1984,42:149-160.
[28]程远,严伟,李晓明等.基于斥力-张力模型的网络拓扑图布局算法[J].计算机工程,2004,30(3)：104-105,188.
[29]孙小红,武伟磊.基于标量场的网络拓扑布局算法[C].中国计算机用户协会信息系统分会2008年信息交流大会论文集.2008：196-199.
[30]赵龙厚.大规模网络拓扑可视化工具的研究与实现[D].黑龙江大学,2009.
[31]蒲涛.网络拓扑可视化技术的研究[D].西安电子科技大学,2010.
[32]李云琪,杨家海,王继龙等.网络拓扑可视化工具的研究与实现[J].微电子学与计算机,2006,23(z1)：202-204.
[33]D.Archambau,T.Munzner,andD.Auber TopoLayout: Graph layout by topological features[J]. In IEEE Information Posters Compendium ,2005,3.4.
[34][EB/OL]http://www.cs.tau.ac.il/
[35][EB/OL]http://www.jgraph.corn/demo/mxgraph/editors/diagrameditor.html
[36]马世霞,刘丹,贾世杰等.基于蚁群算法的文本聚类算法[J].计算机工程,2010,36(8)：206-207,210.
[37]张云,冯博琴,麻首强等.蚁群-遗传融合的文本聚类算法[J].西安交通大学学报,2007,41(10)：1146-1150.
[38]李立云.基于Option自动生成的分层强化学习方法研究[D].长沙理工大学,2008.
[39]张建华,江贺,张宪超等.蚁群聚类算法综述[J].计算机工程与应用,2006,42(16)：171-174,211.
[40]刘建兴.基于信息熵的空间对象群聚类算法研究[D].南京师范大学,2011.
[41]Carmignani A,,Di Battista G.Visualization of the high level structure of the Internet withhermes. J of Graph Algorithms and Applications.2002.
[2]http://www.cheswick.com/ches/map/.
[3]http://www.caida.org/home/.
[4]Govindan R, Tangmunarunkit H. Heuristics for Internet map discovery [A]. Proc of IEEE INFOCOM 2000[C].TelAviv, Israel, March 2000.1371-1380.
[5]姜誉.Internet路由器级拓扑测量与分析技术研究[D]：[工学博士学位论文].哈尔滨：哈尔滨工业大学,2005.
[6]张晓平.网络拓扑发现技术的研究与实现[D].北京邮电大学'2010.
[7]徐成武.IPv4/IPv6混合网络拓扑自动发现研究[D].太原理工大学,
[8]徐前方.在IPv4/v6环境下网络拓扑发现的研究与实现[J].计算机工程与设计,2006,27(23)：4507-4509.
[9]仇伟明.基于IPv6网络拓扑结构自动发现方法的研究[D].南京理工大学,2006.
[10]李元臣,刘维群,薛雷等.IPv4/IPv6混合网络中一种过渡拓扑发现技术[J].武汉理工大学学报(交通科学与工程版),2009,33(4):760-763.DOI:10.3963/j.issn.1006-2823.2009.04.039.
[11]邱雪姣.IPv4/IPv6双协议栈下网络拓扑发现的研究[D].北京信息科技大学,2008.
[12]聂世忠.IPv4/v6混合环境下网络拓扑发现的研究与实现[D].北京邮电大学,2003.
[13]陈文峰,陆际光,王娟等.基于IPv4和IPv6混合网络环境下拓扑发现算法研究[J].电脑知识与技术,2008,4(34)：1585-1587.
[14]蓝集明,符长友.IPv6-in-IPv4隧道发现技术研究[J].四川理工学院学报(自然科学版),2009,22(2)：40-42.
[15]张玉健.IPv6网络拓扑发现技术的研究与应用[D].东南大学,2010.
[16]晏弼成,宋云,莫天虎等.一种IPv4/v6网络拓扑发现新算法[J].长沙理工大学学报(自然科学版),2009,6(4)：78-84.
[17]Vasileios Giotsas,Shi Zhou.Detecting and Assessing the Hybrid IPv4/IPv6 AS Relationships[J].Computer Communication Review,2011,41(4):424-425.
[18]MEI Yu-lin,WANG Xiao-ming,CHENG Geng-dong等.Binary discrete method of topology optimization[J].应用数学和力学(英文版),2007,28(6)：707-719.
[19]YeXU,HaiZHAO.AnImprovedBAModelforRouter-levelInternetMacroscopicTopology[J].IAE NGInternationalJournalofComputerScience,2009.
[20]ClaudiaG6mezSantillan,LauraCruz-Reyes,EustorgioMeza,TaniaTurrubiatesL6pez,MarcoA.A guirreLam,FlisaSchaeffer.ImprovingDistrlbutedResourceSearchthroughaStatisticalMethodolo gyofTopologicalFeatureSelection[J].JoumalofComputers,2009.
[21]XiangyangLiang,JiaZhao.Agent-basedTopologyDiscoveryforTacticallnteraet[J] .InformationT echnologyJournal,2011.
[22]YigalBejerano.Takingtheskeletonsoutoftheclosets:asimpleandefificienttopologydiscoverysche meforlargeethemetLANs.[J].IEEE/ACMTraiis.Netw.,2009,17.
[23]BrianEriksson,GautamDasarathy,PaulBarford,RobertNowak.EfficientNetworkTomographyfo rInternetTopologyDiscovery.[J].IEEE/ACMTrans.Netw.,2012,20.
[24]BenoitDonnet,TimnrFriedman.Intemettopologydiscovery:Asurvey.[J].IEEECommunications SurveysandTutorials,2007,9.
[25]LokeshB.Bhajantri,N.Nalini.Energyawarebasedfaulttoleranceapproachfortopologycontrolindi stributedsensometworks[J]. JoumalofHighSpeedNetwotks,2012,183:.
[26]R. Rohrer , E.Swing. Web-based information visualization IEEE Computer Graphics and Applications, 1997,52-59.
[27]Eades PA heuristic for graph drawing[J].Congressus Numerantium, 1984,42:149-160.
[28]程远,严伟,李晓明等.基于斥力-张力模型的网络拓扑图布局算法[J].计算机工程,2004,30(3)：104-105,188.
[29]孙小红,武伟磊.基于标量场的网络拓扑布局算法[C].中国计算机用户协会信息系统分会2008年信息交流大会论文集.2008：196-199.
[30]赵龙厚.大规模网络拓扑可视化工具的研究与实现[D].黑龙江大学,2009.
[31]蒲涛.网络拓扑可视化技术的研究[D].西安电子科技大学,2010.
[32]李云琪,杨家海,王继龙等.网络拓扑可视化工具的研究与实现[J].微电子学与计算机,2006,23(z1)：202-204.
[33]D.Archambau,T.Munzner,andD.Auber TopoLayout: Graph layout by topological features[J]. In IEEE Information Posters Compendium ,2005,3.4.
[34][EB/OL]http://www.cs.tau.ac.il/
[35][EB/OL]http://www.jgraph.corn/demo/mxgraph/editors/diagrameditor.html
[36]马世霞,刘丹,贾世杰等.基于蚁群算法的文本聚类算法[J].计算机工程,2010,36(8)：206-207,210.
[37]张云,冯博琴,麻首强等.蚁群-遗传融合的文本聚类算法[J].西安交通大学学报,2007,41(10)：1146-1150.
[38]李立云.基于Option自动生成的分层强化学习方法研究[D].长沙理工大学,2008.
[39]张建华,江贺,张宪超等.蚁群聚类算法综述[J].计算机工程与应用,2006,42(16)：171-174,211.
[40]刘建兴.基于信息熵的空间对象群聚类算法研究[D].南京师范大学,2011.
[41]Carmignani A,,Di Battista G.Visualization of the high level structure of the Internet withhermes. J of Graph Algorithms and Applications.2002.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |