ISP Probing Reduction with Anaximander

Since the early 2000's, Internet topology discovery has been an active research topic, providing data for various studies such as Internet modeling, network management, or to assist and support network protocol design. Within this research area, ISP mapping at the router level has attracted little interest despite its utility to perform intra-domain routing evaluation. Since Rocketfuel (and, to a smaller extent, mrinfo), no new tool or method has emerged for systematically mapping intra-domain topologies.

In this paper, we introduce Anaximander, a new efficient approach for probing and discovering a targeted ISP in particular. Considering a given set of vantage points, we implement and combine several predictive strategies to mitigate the number of probes to be sent without sacrificing the ISP coverage. To assess the ability of our method to efficiently retrieve an ISP map, we rely on a large dataset of ISPs having distinct nature and demonstrate how Anaximander can be tuned with a simple parameter to control the trade-off between coverage and probing budget.