ISSN 1000-1239 CN 11-1777/TP

• 论文 • 上一篇    下一篇

AS关系标注的因特网拓扑图的dK序列分析技术

杨国强 窦强 窦文华   

  1. (国防科学技术大学计算机学院 长沙 410073) (hmilyyangguoqiang@tom.com)
  • 出版日期: 2010-09-15

dK Series Analysis on Annotated AS Topology Graph

Yang Guoqiang, Dou Qiang, and Dou Wenhua   

  1. (College of Computer, National University of Defense Technology, Changsha 410073)
  • Online: 2010-09-15

摘要: 拓扑特征分析和拓扑图生成是因特网拓扑研究的一个重要研究方向.dK特征序列被证明是一种有效的系统化拓扑特征分析方法,2K图已经能够在各种重要的拓扑度量方面与实际因特网拓扑图保持一致.在使用dK特征序列分析因特网拓扑时是用无向图来对因特网拓扑进行抽象的,然而对于自治系统(AS)级拓扑,由于AS之间存在复杂的商业关系,使用AS关系标注的拓扑图才能更精确地描述AS级拓扑特征.对dK特征序列进行了改进,提出了能够分析AS关系标注的拓扑图的dK′特征序列,并给出了生成满足指定2K′特征的拓扑图的算法.分析实验结果发现,2K′特征已经能够描述AS关系标注的拓扑图的各种重要特征.

关键词: 因特网, 网络拓扑, 自治系统, AS关系标注的拓扑图, dK序列

Abstract: 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.

Key words: Internet, network topology, autonomous system(AS), annotated AS topology, dK series