AS关系快速推断算法

AS Relationships Quick Inference Algorithm

准确的AS商业关系有助于深入研究因特网的结构及其网络行为,通常只能利用推断来获取AS关系。该文概述了几种AS关系推断算法,分析了各种方法的优缺点。定义了一种基于选路行为表征AS节点传输能力的新测度。该测度比节点度更适于描述AS节点在传输能力上的等级。基于该测度提出了一种快速推断算法,该算法通过比较节点的等级来推断AS关系。试验结果显示该算法与Dimitropolous算法在推断结果上具有良好的一致性,能够快速有效地推断基本AS关系。

Accurate knowledge of the autonomous system （AS） commercial relationships will contribute to research Internet structure and network behaviors intensively. Usually the AS relationships are obtained only by inference. Several algorithms on AS relationships inference are summarized and their advantages and disadvantages are discussed. A new metric is defined, which represents the transmission capability of an AS node based on its routing behaviors. The metric is more suitable to describe the level of AS nodes on transmission capability than the node degree. Based on the metric, a quick inference algorithm is presented which infers AS relationships by comparing the level of nodes. The experiment results show this algorithm has good consistency with Dimitropolous＇s algorithm on the inference results, and the basic AS relationships can be inferred quickly and efficiently by this algorithm.