A hierarchy and probability-based approach for inferring AS relationships

The commercial relationships between Autonomous Systems (ASes) are of great importance to understand the Internet reachability and calculate the AS-level paths. Several algorithms have been proposed to solve the AS relationship inference problem and applied to the data of IPv4 network. In assuming that the provider is typically larger than its customers, and the peers usually have comparable sizes, the suggested algorithms exploit the AS degree information to infer AS relationships. In analysis of the AS relationships in the IPv6 network, however, we find that quite a few of the inference results induced by the present approaches are different from the inferences in the IPv4 network. With respect to this observation, we analyze the root cause of the discrepancy and propose an algorithm which combines the AS hierarchy information, an inherent nature of the Internet structure that we can hardly neglect while analyzing the AS relationships, with the optimization model of Type-of-Relationship (ToR) problem to infer the AS relationships more realistically and stably. In this paper, we first present a methodology to classify ASes into four hierarchies, and then use the AS hierarchy information to infer AS relationships. By taking advantage of these partial AS relationship information, we introduce an improved algorithm to solve the ToR problem for the remaining AS pairs. The experimental results support our algorithm in two aspects. On one hand, the comparison with previous works in the IPv4 network shows that most of our inferring AS relationships are consistent with their inferences, while more inferences of our approach are confirmed by the export policies stored in the Internet Routing Registry (IRR) databases. On the other hand, 94.82% of our inference relationships in the IPv6 network are consistent with the inferences in the IPv4 network, which illustrates that our algorithm is more stable than previous algorithms.