Sharp Snapshots of the Internet’s Graph with HONE

Measuring, diagnosing, and debugging the Internet is surprisingly difficult. The end-to-end argument that pushes complexity to the network edge to ease evolution makes these goals harder by restricting network observables. A consequence has been the inability to address the challenge, posed to the networking community for nearly two decades, of taking accurate snapshots of the Internet graph. Heuristic Optimization of Network Estimation (HONE), described in this thesis, creates accurate graph snapshots that delineate the borders between Internet networks and illuminate interdomain links. Three novel technical contributions lead to HONE’s success. First, HONE establishes a novel iterative constraint satisfaction framework that extracts constraints from traceroute collections; until HONE previous approaches relied on outside constraints. Second, the HONE framework is easily extended to incorporate new heuristics and data sources, making it inherently “future-proof.” Third, HONE is the first snapshot technique to account for traceroute phenomena caused by layer 3 virtual private networks (L3VPNs). I validated these claims through the design, implementation, and evaluation of three experimental systems – MAP-IT, bdrmapIT, and vrfinder – that together form HONE. All the components advance the state-of-the-art toward accurate interface and router-level snapshots of the Internet’s graph. The first component, MAP-IT, proposes the iterative constraint satisfaction framework at the core of HONE that allows it to use constraints drawn from the traceroute. The second component, bdrmapIT, extends the MAP-IT framework by incorporating methodologies from an independently designed system. bdrmapIT adapts heuristics designed for a narrow instance of the Internet snapshot problem and generalizes them for global Internet traceroutes. The final component, vrfinder, addresses the problem that L3VPNs cause routers to report the forwarding address in response to traceroute probes, violating general traceroute semantics. vrfinder is the first technique to identify forwarding address in traceroute, and extends bdrmapIT with additional heuristics designed for L3VPN forwarding addresses, further improving HONE’s accuracy. HONE achieves the best-known accuracy for this problem on traditional IPv4 and IPv6 networks (92.5% – 100.0%), as well as for L3VPNs (88.7% – 95.7%)