TY - GEN

T1 - Stable and Practical AS Relationship Inference with ProbLink

AU - Jin, Yuchen

AU - Scott, Colin

AU - Dhamdhere, Amogh

AU - Giotsas, Vasileios

AU - Krishnamurthy, Arvind

AU - Shenker, Scott

PY - 2019/2/26

Y1 - 2019/2/26

N2 - Knowledge of the business relationships between Autonomous Systems (ASes) is essential to understanding the behavior of the Internet routing system. Despite significant progress in the development of sophisticated relationship inference algorithms, the resulting datasets are impractical for many critical real-world applications, cannot offer adequate predictability in the configuration of routing policies, and suffer from inference oscillations. To achieve more practical and stable relationship inferences we first illuminate the root causes of the contradictions between these shortcomings and the near-perfect validation results of AS-Rank, the state-of-the-art relationship inference algorithm. Using a "naive" inference approach as a benchmark, we find that the available validation datasets over-represent AS links with easier inference requirements. We identify which types of links are harder to infer, and we develop appropriate validation subsets to enable more representative evaluation.We then develop a probabilistic algorithm, ProbLink, to overcome the inference barriers for hard links, such as non-valley-free routing, limited visibility, and non-conventional peering practices. To this end, we identify key interconnection features that provide stochastically informative and highly predictive relationship inference signals. Compared to AS-Rank, our approach reduces the error rate for all links by 1.6\times×, and importantly, by up to 6.1 times for different types of hard links. We demonstrate the practical significance of our improvements by evaluating their impact on three applications. Compared to the current state-of-the-art, ProbLink increases the precision and recall of route leak detection by 4.1 times and 3.4 times respectively, reveals 27% more complex relationships, and increases the precision of predicting the impact of selective advertisements by 34%.

AB - Knowledge of the business relationships between Autonomous Systems (ASes) is essential to understanding the behavior of the Internet routing system. Despite significant progress in the development of sophisticated relationship inference algorithms, the resulting datasets are impractical for many critical real-world applications, cannot offer adequate predictability in the configuration of routing policies, and suffer from inference oscillations. To achieve more practical and stable relationship inferences we first illuminate the root causes of the contradictions between these shortcomings and the near-perfect validation results of AS-Rank, the state-of-the-art relationship inference algorithm. Using a "naive" inference approach as a benchmark, we find that the available validation datasets over-represent AS links with easier inference requirements. We identify which types of links are harder to infer, and we develop appropriate validation subsets to enable more representative evaluation.We then develop a probabilistic algorithm, ProbLink, to overcome the inference barriers for hard links, such as non-valley-free routing, limited visibility, and non-conventional peering practices. To this end, we identify key interconnection features that provide stochastically informative and highly predictive relationship inference signals. Compared to AS-Rank, our approach reduces the error rate for all links by 1.6\times×, and importantly, by up to 6.1 times for different types of hard links. We demonstrate the practical significance of our improvements by evaluating their impact on three applications. Compared to the current state-of-the-art, ProbLink increases the precision and recall of route leak detection by 4.1 times and 3.4 times respectively, reveals 27% more complex relationships, and increases the precision of predicting the impact of selective advertisements by 34%.

M3 - Conference contribution/Paper

SN - 9781931971492

SP - 581

EP - 597

BT - 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI'19)

PB - USENIX Association

ER -