Realizing Fine-Grained Inference of AS Path With a Generative Measurable Process

In the global Internet, the paths between two autonomous systems (ASes), which are used for the exchange of traffic, are essential for understanding the behavior of the Internet routing system and they can help improve the performance of many applications of the Internet. Popular approaches to obtain the AS path between an AS pair (AP) are measurement based (e.g., Traceroute), but considering the size of the modern Internet and the limitations of measurement resources, only paths between a very small portion of APs can be measured. In recent years, a large body of path inference approaches has been proposed to bridge the gap in measurement resources. However, as we show with experiments, they perform poorly in accuracy and coverage. We propose a generative measurable path inference (GMPI) framework for AS-level path measurement, which performs well in accuracy and coverage. GMPI addresses two limitations of previous approaches: 1) Information incompleteness due to unrevealed real-world AS-level routing policies and insufficient measuring resources. 2) Knowledge isolation caused by distributed AS knowledge with different sources and inconsistent forms. To overcome these challenges, the data-driven GMPI framework invents heuristic path generation to address incompleteness and a dual-attention network to integrate the isolated knowledge. GMPI does not perform any measurement or impose any burden on the network. Our performance evaluation shows that our framework GMPI outperforms state-of-the-art approaches in terms of accuracy and coverage. In particular, compared to the state-of-the-art stitching-based baseline, GMPI provides a 42.45% improvement in coverage and a 39.97% improvement in accuracy. The experimental results demonstrate that GMPI can accurately infer paths for nearly arbitrary APs.