dK Series Analysis on Annotated AS Topology Graph

Topology property analysis and topology generation are important tasks for the Internet topology researchers. The topology properties of the Internet and the generated topologies with the same properties of the Internet topology are valuable for many other research fields, such as routing protocol designing, network performance analyzing and next generation network constructing. The dK series is proved to be an efficient tool for systematic topology property analysis, and the d=2 case is sufficient for most practical purposes. When using the dK series, the Internet topology is described as an undirected graph. Whereas, the AS(autonomous system) level Internet topology is better described by a graph annotated by AS relationships, as the complicated commercial relationships between ASs. In this paper, based on the definition of the dK series, a new series called dK′ series is proposed to analyze the property of the annotated AS topology graph, and a novel approach is presented to generate graphs with a given 2K′ distribution. The generation approach is based on an improved 2K graph generation algorithm which outperforms the existing 2K graph generation algorithm. By analyzing the result of experiment, it is found that the d=2 case is sufficient to describe most important properties of annotated AS graph.