SCIENCE@home

Yarrp'ing the Internet: Randomized High-Speed Active Topology Discovery

Robert Beverly

Published 2016 in ACM/SIGCOMM Internet Measurement Conference

ABSTRACT

Obtaining a "snapshot" of the Internet topology remains an elusive task. Existing active topology discovery techniques and systems require significant probing time -- time during which the underlying network may experience transient dynamics. This work considers how active probing can gather the Internet topology in minutes rather than days. Conventional approaches to active topology mapping face two primary speed and scale impediments: i) per-trace state maintenance; and ii) a low-degree of parallelism. Based on this observation, we develop Yarrp (Yelling at Random Routers Progressively), a new traceroute technique designed for high-rate, Internet-scale probing. Yarrp is stateless, reconstituting all necessary information from ICMP replies as they arrive asynchronously. To avoid overloading routers or links with probe traffic, Yarrp randomly permutes an input IP X TTL space. We run Yarrp at 100Kpps, a rate at which the paths to all IPv4 /24's can be mapped in approximately one hour from a single vantage point. We compare Yarrp against existing systems, and present examples of topological dynamics exposed via the high sampling rates Yarrp enables.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-22 of 22 references · Page 1 of 1

CITED BY

Showing 1-97 of 97 citing papers · Page 1 of 1