Research And Implementation On Network Topology Discovery

With the rapid development of computer networks and communication technology, computer network has been applied to government, business, military, education and other social areas. It is becoming increasingly important to successfully manage network, improve the performance of networks and quality of service and ensure information security and reliable transmission.The function model of network management has five modules, including fault management, performance management, security management, configuration management and billing management. A good network management system needs to grasp the topology of the managed network. Network configuration management is the process to discover and configure network equipments which are meaningful to network management, and network topology discovery is the core of configuration management, the foundation of fault management and performance management, and the important measure for a commercial network management system. Therefore, the design of the topology discovery algorithm takes a key role in the development of a network management system.At present, most of the network topology discovery use SNMP protocol to implement the logical topology algorithms in autonomy networks based on routing table. However, switches and other equipment are increasingly distributed in IP networks to form micro-segmentations, which make the network structure become invisible to the 3rd layer– logical topological discovery. In addition, the delay of research on Internet topology discovery has caused a bottleneck for nearly all wide-area network applications, server selection and placement, which make the Internet topology discovery and performance measurement receive increasing attention. Evidently, it can be seen that present logical topology discovery algorithms are far away from meeting the needs of these requirements. The paper not only studies the physical and logical topology discovery of the autonomy network, but also expands the scope of topology discovery greatly into Internet router level.Firstly, the paper introduces some tools that topology discovery algorithms often use, such as Ping, Traceroute, SNMP, DNS, and some comparisons and analyses are made about these tools, which points that an appropriate tool or a combination of some tools should be selected according to the specific network condition in practical application. Then the paper introduces the structure of the autonomy network. Different network structure view can be seen from OSI Reference Model. In this paper, the autonomy network is abstracted as the undirected graph.The logical topology discovery of autonomy network is to find relationship in network layer devices (routers), including the connections between router and router and the connections between the port of router and the local subnet. The primary functions of a router are to form the routing links among the routers connected to each other, to receive and transmit network layer data packets on the links, and to provide the services of transporting data from host to host.The router makes use of configured routing protocol (BGP, OSPF, etc.) to produce the routing table, and the routing table records the local port and the address of next hop to different destinations. Therefore, according to the routing table, it can be known not only the host or subnet that the local port connects to, but also the next router that the local port connects to. Starting from a router R, all other routers, such as R1, R2,…, Rm, which connects to R can be found accordingly. Do the same process on R1, R2,…, Rm as on R. Keep doing the process until all routers has been founded. Then a logical topology graph can be got. That is the whole process that implements the logical topology discovery algorithm of an autonomy network. This algorithm can find the whole logical topology graph rapidly, based on the breadth-first traversal theory in undirected graph. Experiments show that the algorithm can be used to find the logical topology graph of autonomy network more rapid and complete. The physical network topology of autonomy network is the actual physical links (the equipment links in the second lower layers of OSI Reference Model) between physical entities in autonomy network. In the network topology graph, the physical network topology is represented by adding links between switches and switches, switches and routers, and switches and hosts on the basis of former logical topology. The key of the physical topology discovery in the 2nd layer is to find links between switches and switches.Currently, most of the Ethernet physical topology discovery algorithms depend on the address forwarding table (FDB) of the bridge. These algorithms, based on the MAC address forwarding table, can get the network topology. However, because the records in the address forwarding table are dynamic and incomplete, it is necessary to add additional flow to network to ensure its integrity before running the topology discovery algorithm. Thereby, these algorithms have limitations to some extent. Based on the analysis of the existing algorithms of MAC address forwarding table, the paper presents a new physical topology discovery algorithm relying on spanning tree protocol. This algorithm gets spanning tree status information of each switch by SNMP. According to STP, we derive physical topology of the network. The algorithm doesn't need to add additional flow to network, and can be applied to the Ethernet including multiple subnets. It can not only find backup links between bridges, but also find equipments that do not support SNMP such as Hub and dump switches.Network structure is changing continually, because of the complexity of the network, diversity of business and randomicity of accessing to network. Network security management in state level requires deep understanding of the Internet topology and analyzing structural actions, in order to present reasonable suggestions to optimize network configurations. Therefore, Internet topology detection becomes a new research scope.Theoretically, topology discovery algorithms for autonomy networks can also be applied to Internet topology discovery in router level. However, they are very different with each other actually, because some protocols which are often used in topology discovery of autonomy network can only be used in an autonomy system, including SNMP, DNS. So these protocols cannot be applied to the Internet topology discovery in router level, and to detect many packets'forwarding paths by Traceroute is the most effective way of the Internet topology discovery in router level.In order to obtain a more complete Internet router-level topology, the paper adopts a multi-source Traceroute detecting method. Before Traceroute detecting, it is necessary to determine the measurement of coverage at first. Then, to find the source addresses set and the destination addresses set in the appropriate scope. There are many factors influencing the completeness of the topology measurement in router level, one of which is the destination selection. If the destination selection method is inappropriate, the measurement result can not be complete.Most of existing destination selection methods takes IP address as the sampling granularity during random selecting destinations. The sampling probabilities of different IP addresses are same in existing methods, but it is not in stub network. As a result, not all of the stub networks in measuring range are covered by selecting destinations. Therefore, a viewpoint that taking the stub network as the sampling granularity instead of the IP address is put forward in this paper and a self-contained destination selection method that is termed as stub networks complete coverage and random destination selection is presented. This method can greatly improve the integrity of Internet topology discovery in router level.