Network Topology Identification Method, The Traditional Measurement And Tomography

Traditional method of network topology inference is mainly based on the collaboration of protocols and information feedback by the routers. However, it's more and more difficult to get the collaboration of protocols and information feedback by the routers due to the demand of network security. Network topology inference based on network tomography can infer the whole topology of network without the collaboration of router protocols and internal nodes. However, the method of network topology inference based on tomography often takes too much time in calculating because of the need to send a large number of probe packets to calculate the statistical characteristics. In our opinions, traditional methods of network topology inference depend on the feedback of the routers, which is often difficult to apply in the actual large-scale networks; tomography based topology inference assume that all routers are uncooperative, which make the measuring work much more difficult. There are not only collaborative routers but also uncooperative routers in the actual networks. Therefore, this paper introduces a method of topology inference combine the traditional methods of topology inference and topology inference based on tomography, which not only be able to speed up the process of topology inference and reduce the number of packets according to the feedback information from the coordinate node in the network but also be able to make use of tomography technology for topology inference dynamically to the non-collaborative part of the network.In this paper, we introduce three aspects of research results through the study on traditional methods of topology inference as well as tomography-based topology inference:(1)At the aspect of algorithm to topology inference, we improve the existed topology inference methods and introduce a new method of topology inference based on tomography using"sandwich"probe, which measure the difference of the arrive time of the two small packets of the"sandwich"packet-group in order to infer the length of the shared path. This kind of method includes the hierarchical clustering algorithm based on the smallest similarity as well as the division of leaf nodes algorithm. The division of leaf nodes algorithm can be divided into division of leaf nodes algorithm for general topology tree and division of leaf nodes algorithm for binary topology tree according to the type of topology. This method reduces the computational complexity and improves the accuracy as well.(2)At the aspect of measure method, we introduce the new"sandwich"probe based on TTL variable packet to solve the problem of common"sandwich"probe. The common"sandwich"probe infer the length of the shared path by using the similarity data. The accuracy of the length will be affected by the error of the similarity data. The"sandwich"probe based on TTL variable packet can obtain the exact length of the shared path by compare of the similarities which are obtained by sending"sandwich"probe with different TTL. This method reduces the number of packets to only 10% compare to the original number and the accuracy is also greatly improved.(3)Finally, we propose a comprehensive solution by the combination of the traditional inference methods with traceroute and improved algorithms and measurement methods. This method firstly obtains some of the topology information from the coordinate nodes in the network and then proposes an incomplete initial topological structure by using the initial topology construct algorithm. Finally, we use anonymous node process algorithm to identify the incorrect or incomplete part of the initial topological structure to get the final topology. This method further reduces the number of packets and further improves the inference accuracy.Using NS2 simulations we have proved that the combination of traditional methods and topology inference based on tomography not only reduce the complexity and the number of packets to be send but also improve the inference accuracy of topology.