Research On IP Network Router Level Topology Based On Network Tomography

With the rapid progress of network technology, network has been one of the most important infrastructures and has infiltrated every aspect of our society. The network router level topology can characterize connection between routers, and it can also provide useful data for network programming, optimization, management, which are the foundation of constructing credible and secure network.The existing router level topology recognition methods mainly rely on the measuring tools, such as traceroute, to collect original data and then analysing the data to construct router level topology. Howvever, many network nodes won’t give a reponse to the measuring data packets emited by measuring tools for security reasons, which leads to lots of anonymous routers.So it’s impossible to accurately recognify the router level topology. In order to solve this problem, some international scholars proposed network tomography to estimate router level topology.This method emits probe packets among the network edge nodes, and then used statistical method to infer the structure of router level topology. The biggest advantage of network tomography is that it can infer router level topology without internal node collaboration, so it is not subject to anonymous routers. But only tree topology can network tomography get instead of the net topology.For defects of the existing methods, this paper combines the traditional anonymous recognition methods with network tomography, which makes the tree topology as constraint to recognify anonymous routers. By using this new method can we finally construct a relative perfect network topology.The main contribution of this paper including:Firstly, proposing the anonymous router clustering method based on graph modeling. The aim of anonymous router clustering is gathering the anonymous routers which have similar location.Anonymous routers clustering is helpful for designing reasonable probe packets transmission scheme and cover anonymous routers which are required to be identified. This paper proposes the clustering method based on graph modeling. By analysing and summarizing the original measuring data, this paper conclude three kinds of anonymous routers clustering graph model. The three graph models are all according to the connections between known start nodes and end nodes,so anonymous routers location can be determined and clustered.Secondly, proposing an anonymous router’s recognition method based on network tomograph.Network tomography designed probe packets transmission scheme using known nodes, and use covariance of time delay to construct tree topology. So we make use of statical time delay covariance and construct tree topology. This tree topology is used as constrained codition, moreover according to the characteristics of network tomograph, this paper put forward anonymous routers recognition rules. According to the tree topology and recognition rules, a equation can be obtained about anonymous routers’ distribution at each link. By interatively solving the equation all answers about anonymous routers’ distribution can be obtained.This paper chooses real network measure data, which downloads from i Plane and CAIDA, to verify the clustering method and anonymous routers’ recognition method based on network tomograpg. And the result of experiment show that the clustering method can cluster anonymous routers effectively and anonymous routers’ recognition method can recognize anonymous routers effectively. Therefore, the methods proposed by this paper can get router level topology accurately in the presence of large numbers of anonymous routers.