Primitives for Active Internet Topology Mapping: Toward High-Frequency Characterization
Abstract
Current large-scale topology mapping systems require multiple days to characterize the Internet due to the large amount of probing traffic they incur. The accuracy of maps from existing systems is unknown, yet empirical evidence suggests that additional fine-grained probing exposes hidden links and temporal dynamics. Through longitudinal analysis of data from the Archipelago and iPlane systems, in conjunction with our own active probing, we examine how to shorten Internet topology mapping cycle time. In particular, this work develops discriminatory primitives that maximize topological fidelity while being efficient.
We propose and evaluate adaptive probing techniques that leverage external knowledge (e.g., common subnetting structures) and data from prior cycle(s) to guide the selection of probed destinations and the assignment of destinations to vantage points. Our \emph{Interface Set Cover} (ISC) algorithm generalizes previous dynamic probing work. Crucially, ISC runs across probing cycles to minimize probing while detecting load balancing and reacting to topological changes. To maximize the information gain of each trace, our \emph{Subnet Centric Probing} technique selects destinations more likely to expose their network's internal structure. Finally, the \emph{Vantage Point Spreading} algorithm uses network knowledge to increase path diversity to destination ingress points.
Description
Proc. ACM Internet Measurement Conference, Melbourne, Australia, November 2010.
The article of record as published may be found at http://dx.doi.org/10.1145/1879141.1879162
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.Collections
Related items
Showing items related by title, author, creator and subject.
-
Server probing for server and agent based active network management
Altinkaya, Mustafa (Monterey, California. Naval Postgraduate School, 2000-03);In Server and Agent Based Active Network Management (SAAM) architecture, a server will make routing and other important decisions on behalf of the routers in its region. In order to make the right decisions and to support ... -
State Estimation of Non-monotonic, Partially Non-deterministic Software with Sparse Probing using an Unscented Kalman Filter combined with Logic Reasoning
Drusinsky, Doron (Monterey, California. Naval Postgraduate School, 2013-01); NPS-CS-13-004This report describes a technique for assessing the state of a general-purpose system using partial probing. The technique utilizes an Unscented Kalman Filter (UKF) combined with in-process and post-process reasoning. While ... -
IPv6 host fingerprint
Nerakis, Eleftherios (Monterey, California. Naval Postgraduate School, 2006-09);This thesis explores ways of using probe packets to identify the type and version of OS that is run by a remote IPv6 host. Such a probing technique can be effective because developers of different OSes often interpret the ...