A measurement study of AS paths: Methods and tools

Many Internet applications are designed and deployed as overlay applications. The potential mismatch between the application overlay and the network underlay has driven the demand for designing locality-aware applications in order to reduce emerging huge inter-domain traffic load. In this paper, we study a fundamental problem of measuring AS paths between two Internet hosts using three methods including traceroute-based direct measurement, BGP-based indirect inference and graph-based shortest AS path. We conducted a measurement study of AS paths to evaluated the accuracy and complexity of the above three AS path measurement methods and the corresponding tools. Inspired from our experiment results, we proposed a hybrid progressive method to combine the traceroute probes and the BGP tables to enhance the IP-to-AS mapping process to achieve a more accurate estimation of AS paths. We also found that the missing IP addresses in the traceroute measurement decrease the accuracy of the traceroute-based method; however, this performance degradation can be compensated using BGP tables. Our study leads a more accurate IP-to-AS mapping tool and it can provide a solid support for locality-aware Internet applications.