Yarrp'ing the Internet: Randomized High-Speed Active Topology Discovery
Loading...
Authors
Beverly, Robert
Subjects
Advisors
Date of Issue
2016-11
Date
Publisher
Language
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.
Type
Article
Presentation
Presentation
Description
The article of record may be found at http://dx.doi.org/10.1145/2987443.2987479
Proceedings of the Sixteenth ACM SIGCOMM Internet Measurement (IMC 2016) Conference, Santa Monica, CA, November 2016
Proceedings of the Sixteenth ACM SIGCOMM Internet Measurement (IMC 2016) Conference, Santa Monica, CA, November 2016
Series/Report No
Department
Computer Science (CS)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
This work supported in part by NSF grant CNS-1213155.
Format
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.