Internet Topology Discovery Based On Multi-source Information Fusion

Since the emergence of the Internet,Internet topology discovery has been a hot issue in the network research field.Accurate Internet topology is the basis of many network science researches,and also helps network managers to maintain and optimize the Internet architecture more effectively.Now through Internet topology measurement and public databases query,researchers can obtain many different types of topological information.However,due to the complex structure and large scale of Internet topology,and the lack of dedicated protocols or tools for topology discovery,each type of topology information acquired now has different degrees of loss and error.And most of the existing topology discovery methods use only one type of topology information to generate the Internet topology,so the completeness and accuracy of the Internet topology generated now still need to be improvedTo solve this problem,this paper proposes using multi-source information fusion method for Internet topology discovery.On the base of the full analysis of the existing Internet topology information,this paper start from different topology discovery problems themselves,and fuse multi-type topology information to obtain a more complete and accurate Internet topology.This paper chooses to make a preliminary attempt in the topology discovery problems of AS and PoP levels and the main work is as follows:(1)A two-type information fusion based IP-to-AS mapping table refining method is proposed.Different from the existing methods of refining IP-to-AS mapping table which only depende on one type of data,this method combines alias resolution data and traceroute-BGP path pairs,and extract four kinds of information from them to identify the owner AS of each router to refine the original IP-to-AS mapping table.The results show that compared with the existing methods,the method based on two-type information fusion achieves a higher accuracy,and is more stable when the amount of input data decreases and the error rate of input data increases.At the same time,the steps of the algorithm are adjusted slightly to ensure the convergence of the method.(2)A link clustering based Internet PoP-level map inferring method is proposed.This method takes into account the two characteristics of close connection and close geographical location of routers in a PoP,and draws lessons from the idea of link detection algorithm.Firstly,the similarity of router-level link pairs is calculated,then router-level links are clustered hierarchically to obtain the link clusters,after that they are transformed into router clusters(i.e.PoP)by some heuristic algorithms.Finally,this method determines the geographic location of each PoP based on the geographic location of the routers within the PoP,and draw the PoP-level topology map.This method is used to draw the global PoP-level topology map of AS174.The coverage rate is higher than that of the existing method,and the location accuracy reaches 76.1% when the error range is 100 km.In addition,this paper also evaluates the influence of incomplete probe and incorrect location information on PoP-level topology map discovery through simulation experiments.