Research On Probe Deployment Method In Network Topology Detection

With the development of network technology as well as the growth and change of users' needs for network,the structure and scale of the network are constantly complicated and expanded.In order to monitor the network effectively,to optimize the network structure,and to analyze the network behavior further to prevent network attacks,the full knowledge of network topology is needed.Therefore,the network topology identification becomes the basis and the focus of the network research.At present,the research on network topology mainly focuses on the improvement and innovation of detection methods,but few on the probe deployment in the network.Therefor,the work of this thesis focuses on the method of the probe deployment.Due to the complexity of the network topology,the detection results from a single source node or destination node can only reflect a small part of the overall network topology.In order to get the overall network topology,the results of multi-source multi-purpose detection must be combined.As the information detected by different probes is not the same,and the deployment of probes in the network requires a certain amount of overhead,how to reduce the number of probes and increase the size of the network can be detected is worthy of research.In order to correctly analyze the influence of the relationship between the overall network topology and the probe detection range on the probe deployment location,it is necessary to study the probe deployment problem under the condition that the network topology is fully known.In order to apply the method in the actual detection process,it is necessary to study the probe deployment problem under the condition that the network topology is unfully known.The problems of node deployment in the above two cases are studied in this thesis and the results include the following two aspects:1.Putting forward a heuristic probe deployment method for network topology identification.Based on the analysis of the relationship between the overall network topology and the detection range of the single source node,the problem is abstracted into a set covering problem,and a heuristic method of probe deployment is put forward by improving the set cover greedy algorithm.This method can effectively reduce the number of the probes compared with the set cover greedy algorithm.The method can also be applied to the probe deployment of network performance detection with the same detection range.2.Putting forward a probe deployment method based on complex network characteristics.Based on the analysis of the complex network characteristics of the router-level network topology,a method is designed to generate the topology similar to the overall topology by using the characteristics of partial network topologies.By using the topology generation method and the heuristic probe deployment method,a probe deployment method under the incompletely known network topology is designed.The method is an improvement over the previous method so that it can be used in the actual network.The topologies generated by the router-level network topology generators and the NS3 simulation tool are used to test and simulate probe deployment method and topology identification process mentioned above.The experimental results show the effectiveness of the method and the process.When the topology is completely known,compared with the set coverage greedy algorithm,the effect of the probe deployment method in this thesis is better.When the topology is incompletely known,the effect of the probe deployment method is close to the effect in the case of the completely known topology.