AS-Level Topology Discovery: Measurement strategies tailored for crowdsourcing systems

The rise of crowdsourcing systems for network measurements fosters the design of new measurement paradigms to cope with the limitations of such systems, i.e. devices with scarce resources. In this paper we address the problem of running active measurements for discovering the Internet topology at the autonomous system level of abstraction with crowdsourcing systems. We show how to obtain meaningful results with an extremely low number of measurements. We devise two classes of measurement strategies based on different approaches: topological and historical. We experimentally validate our strategies by comparing them with measurements collected with a broad strategy by Portolan, a crowdsourcing system based on mobile devices. We show that the number of measurements can be reduced up to over 80%, at the cost of a negligible loss of useful information. We finally provide pros and cons of the two classes of strategies along with a detailed analysis of the reasons why the (small) loss of information happens.