Systematic Analysis Technology On The Internet Topology

As the basic feature of the Internet, the Internet topology is critical for a variety of protocols and applications running on the Internet. Research on the Internet topology is of great significance for many other Internet-related researches. Systematic analysis technology on the Internet topology and the dK-series are the latest research results in the field of the Internet topology research. They have promoted the development of the research on the Internet topology analyzing and modeling. They are also important as reference for many other related researches, such as complex network research. The dK-series is composed of a series of metrics which are called the dK-properties. The dK-series can characterize more and more properties of a given graph when d increases. The technology, which employs a series of metrics to characterize the properties of the Internet topology, is called the systematic topology analysis technology. In this paper, an in-depth study on the systematic topology analysis technology is conducted on the basis of the dK-series. The innovations of this paper are as follows:Firstly, dK-graph constructing algorithms with better performance are proposed, and an algorithm that can increase the connectivity of a dK-graph is proposed. The dK-graph is defined as a graph that has the same dK-property with the graph being studied. As dK-series has strong topological characterization capabilities, so it is of great significance for the Internet topology research to study the dK-graph constructing algorithms. The shortcomings of the existing algorithms are that, their precisions are low, and the connectivities of the constructed graphs are poor. In this paper, an improved 2K-graph generation algorithm and a 3K-graph directly constructing algorithm are proposed. Experimental results show that, the precisions of the algorithms in this paper are better than that of existing algorithms, and so with the connectivities of constructed graphs. Further, an algorithm based on link reconnection is proposed, which can be used to increase the connectivity of a dK-graph. Experimental results show that, the algorithm can significantly reduce the number of non-connected sub-graphs of a dK-graph, which may be generated by any dK-graph constructing algorithm.Secondly, a fast algorithm for calculating the shortest paths and betweenness in the annotated AS (Autonomous System) graph is proposed. As the complicated routing relationships between ASes, the Internet AS level topology is usually presented as a semi-directed graph, where the links are annotated with the relationships between ASes. In such a semi-directed graph, the traditional algorithms for calculating the shortest paths and betweenness are no longer applicable. In this paper, an algorithm based on breadth first search(BFS) algorithm is proposed, which can be used to calculate the shortest paths and betweenness of the annotated AS graph. The time complexity of the algorithm is O(nm), which outperforms the existing algorithm with the time complexity of O(n3), so it is more suitable for the research on the Internet AS level topology(n is the number of nodes and m is the number of links in the graph).Thirdly, the systematic analysis technology on the annotated AS graph is studied. The definition of the dK-series is based on undirected graph, so it is not applicable to the annotated AS graph. In this paper, a new series called dK′-series is proposed, which can be used to analyze the characterization of the annotated AS graph. The dK′-series differs with the dK-series in that, the descriptions with the type of links are added. Further, the dK′-graph constructing algorithms are proposed by extending the dK-graph constructing algorithms. Experimental results show that, the dK′-series has the same capability as the dK-series. For the case of d=3, the graphs generated by 3K′-graph constructing algorithm are the same as the annotated AS graph on all kinds of important metrics.Forthly, a compact systematic topology analysis technology is proposed. One of the problems with the dK-series is that, the number of sub-graphs with d nodes grows significantly when d increases. The problem leads to the complication of the dK-graph constructing algorithms, and in the case of d>3, there is no effective dK-graph constructing algorithm. In this paper, the notion of the neighbor-graph is defined at first, and then a new series called dM-series is proposed based on the definition of the neighbor-graph. Further, the dM-graph constructing algorithms are proposed, which are much more sample than the dK-graph constructing algorithms. Further more, the dM-graph constructing algorithms are applicable for any case of d, so the dM-series is more suitable than the dK-series for analyzing large-scale topologies. Experimental results show that, as the dK-series, the dM-series is capable of capturing the properties of topologies systematically: it can characterize more and more properties of topologies when d increases. For the case of d=2, the 2M-graph is capable to characterize all kinds of important metrics of the given graph.