Design And Implementation Of Internet Router-level Topology Discovery System

In recent years, Internet has been popularized rapidly and effective network management becomes more and more important for Internet. Network topology discovery technology is the basis of network management, how to discovery network topology structure accurately and completely is very important. Meanwhile,how to provide an intuitive topology map for the network administrator is also the focus of this thesis. An improved DoubleTree algorithm called IpDT Algorithm (Improved DoubleTree Algorithm) and an improved FR algorithm (Fruchterman Reingold Algorithm) called DHL Algorithm (Degree Hierarchical Layout Algorithm) are proposed after analyzing the advantages and disadvantages of DoubleTree algorithm and FR algorithm. And on these bases, a prototype system of network topology discovery and visualization is designed and implemented. The main works are listed below:(1) The characteristics and difficulties of topology discovery and layout are summarized in Internet router level topology, and the advantages and disadvantages of commonly used topology discovery and layout algorithm are analyzed.(2) In the topology discovery process, it is often difficult to choose the initial hop count, the communication traffic is fairly high in the existing DoubleTree algorithm. An improved DoubleTree algorithm called IpDT Algorithm is presented to solve the above problems. A reasonable detection rules are designed,the average number of hops is calculated as the initial hop count and Bloom filter is used to compress the global stop set. Simulation results show that the algorithm can effectively reduce redundancy and communication traffic, reaching the purpose of reducing the network load.(3) The execution time is fairly long and the layout don’t reflect the hierarchy of the network in the existing FR algorithm for visualizing the Internet topology. An improved FR algorithm called DHL Algorithm is presented to solve the above problems. Firstly, the nodes are divided into three categories according to power-law distribution of the node degree in Internet router level topology. Secondly, the nodes in the network are separated into multiple hierarchical layers after classification. Finally, the initial temperature and iterations are selected according to the different layers. The experimental results show that DHL algorithm can effectively reduce the execution time and the number of cross edges.(4) A prototype system of network topology discovery and visualization is designed and implemented. The system includes three modules:topology discovery module, data conversion and reading module and topology display module. Topology discovery module is the foundation of the whole system which is used to detect the target network and access the topology information, and the IpDT algorithm presented in the chapter three is adopted for topology discovery. The main function of data conversion and reading module is to process the probe data obtained by topology discovery module. The main function of the topology display module is to display the network topology by using topology layout algorithm, DHL algorithm presented in the chapter four is adopted for topology layout. Finally, the effectiveness of the proposed system is verified by testing the system.