Network Topology Inference Based On Active Measurement

With the rapid development of information technology,computer networks have been widely used in various fields.Though network topology plays an important role in many fields such as network management,network fault diagnosis etc.,the topology within the network is usually invisible for kinds of reasons.Therefore,the research of network topology inference has important academic significance and extensive practical value.The main research content of this thesis is the traceroute-based network topology inference under active measurement.In the non-cooperative network environment,there are two problems must be resolved: anonymous route problem and IP alias problems.Although domestic and foreign scholars have conducted some research on these two issues and proposed some solutions,there are still some shortcomings in these methods.For example,in the case of anonymous router,the existing algorithm has problems such as loops and error merging of non-anonymous routers in the phase of inference etc.,which lead to the inaccuracy of the inferred network topology.In the case of IP alias,the existing algorithms also have some problems such as high computational complexity,a lot of unnecessary calculations,not suitable for large-scale network,etc.Therefore,this thesis studies the network topology inference based on traceroute under active measurement.The main work includes the following two aspects:1.In the aspect of anonymous router,this thesis firstly makes a deep research on the existing algorithms,analyzes and points out five problems of the i Top algorithm such as loop and non-anonymous routers error merging,etc.Secondly,to solve the above problems,the GBAR algorithm is proposed.Finally,the GBAR algorithm and existing algorithms are analyzed experimentally from several indicators on the public data set CAIDA.It is indicated that the GBAR algorithm can improve the accuracy of the existing algorithm which ensuring the time complexity.2.In the aspect of IP alias,it is normal classify IP alias resolution techniques into two types fingerprint techniques and analytical techniques.In this thesis,through the analysis of existing algorithms,it is pointed out that the kapar algorithm has a large amount of computation and excessive dependence on the traceroute.To optimizes the kapar algorithm for these problems,the ICAR algorithm is proposed by using the fingerprint techniques and analytical techniques together and by adding a filter mechanism.Finally this thesis gives an theoretical analysis on ICAR,which indicates that the ICAR algorithm reduces the computation amount and improves the completeness of IP alias recognition.