Fast Internet Topology Discovery

Abstract

To this day, performing Internet-scale probing campaigns in order to obtain a "snapshot" of the Internet topology remains a laborious task both in terms of time and accuracy. Indeed, probing substantial parts of the IPv4 address space using classical Traceroute-based approaches can take up to several days. However, being able to obtain topological maps is of great importance as numerous network researchers and administrators rely on these maps to prevent infrastructure problems or even to develop security policies for instance. In 2016, Robert Beverly introduced YARRP. YARRP stands for "Yelling At Random Routers Progressively". It is a new way of probing that can considerably reduce the required probing time thanks to stateless operations. This Master thesis heavily relies on the tool that was introduced by this paper. By using it, we hope to address one of the major issue related to current large-scale probing techniques: the speed. Indeed, as we will see, YARRP enables quite fast large-scale probing campaigns owing to stateless operations.

However, YARRP is subject to a major flaw: its redundancy. Indeed, by re-implementing YARRP as described in Dr. Berverly's paper, we have found that even though it enables fast probing campaigns to be made, it is a very aggressive probing method in terms of redundancy. That is why, in this Master thesis, we first propose to re-implement YARRP from scratch in order to validate it (we will call it "the original version"). Then, we will try to improve it in no less than three different ways. Obviously, we will evaluate the impact of each of these improvements independently as well as discuss their advantages and drawbacks. Lastly, we will carry out a larger measurement campaign using our improved version of YARRP in order to see how well it performs compared to the original version.

In the end, we have been able to develop an improved version of YARRP that is stable as well as less aggressive than the original one. For instance, we have doubled the uniqueness rate and increased the response rate from 34\% to more than 80\%. Obviously, all the improvements have been made by keeping in mind that the probing step should remain as fast as in the original version of YARRP.