网络拓扑发现新算法及其实现  

New Algorithms on IP Network Topology Discovery and Its Implement

作　　者：陈福[1] 杨家海[2] 杨扬[1] 

机构地区：[1]北京科技大学计算机科学与技术系,北京100083 [2]清华大学信息网络工程研究中心

出　　处：《电子学报》2008年第8期1620-1625,共6页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60673160,No.90412012,No.60473083);国家863高技术研究发展计划(No.2007AA01Z234,No.2005AA103110-2)

摘　　要：本文首先提出一种面向IP主干网的启发式网络拓扑发现算法.该算法基于启发式、贪心法的思想,具有IP地址的自动推理和查找范围的自我调整,因而具备较强的自适应性.进而提出了一个数据链路层拓扑发现算法.该算法与已有的算法相比重点解决了无生成树协议工作下数据链路层拓扑发现、主机的拓扑构造以及集线器或无IP地址的交换机等所谓的哑设备发现问题.同时阐述了一种新的数据结构类型并给出其数学定义、专有操作及该数据结构在算法中的应用.算法已经实现并应用到我们自己开发的软件中,同时在清华大学网络研究中心实验网络环境中进行了实际测试和验证,达到了很好的效果.In this paper,we present two novel algorithms,one for discovery logical topology,the other one for discovering physical topology in heterogeneous IP networks. The algorithm for logical network, which adopt heurism／greedy algorithms,can be applied to large scale IP network.For the algorithm can self deduce IP addresses,adjust the search domain,it has strong adaptabilities. Another novel algorithm is presented for physical topology, which includes switches, hosts and hubs. At the same time, a new data structure named Treelike_ Graphics for topology discovery is presented with precise mathematic definition, relationship set and proprietary operation on this data structure. The algorithm, which we present in this paper, does no base on the STP protocol to get the information of topology. So, there are few preconditions to the algorithm. We have implemented the algorithm presented in this paper in Perl in Tsinghua University own research network. The experimental results clearly validate our algorithm, demonstrating that our algorithm can consistently discover the accurate physical network topology with reasonably small running-time requiremerits.

关 键 词：拓扑发现 树型图 网络层 数据链路层 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]