Which way to go? Inferring Fine-Grained AS Paths with PathRadar

Accurate comprehension of routing paths, i.e., how packets are routed from a source AS to a destination, is critical for analyzing and understanding the Internet. Previous path inference algorithms often oversimplify the complexity of Internet topology and routing policies, so they often fail to differentiate between paths to different prefixes within the same AS, and tend to be either inaccurate or incomplete. Based on an in-depth anal-ysis of observable routing behaviors, we introduce PathRadar, a novel framework for fine-grained AS path inference. PathRadar designs a Progressive Learning Process (PLP) that employs different inference models for different AS categories, leading to higher accuracy and completeness than existing methods. It also captures the intrinsic features of a large portion of non valley-free paths, and can accurately infer such paths which no existing method can infer. We evaluate PathRadar with comprehensive data collected by multiple measurement platforms. Compared with the latest algorithms, PathRadar can improve the accuracy and completeness of AS-level path inference by up to 6.7x, improve the accuracy for prefix-specific paths by up to 8.9 x, and reach the accuracy of 90% for non valley-free paths.