Robert Beverly, Arthur Berger, and Geoffrey G. Xie
Proceedings of the Tenth ACM SIGCOMM/USENIX Internet Measurement Conference (IMC 2010),
Sydney, AU, November 2010.

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.

[Postscript(488KB)] [PDF(192KB)] [BibTeX]

[Presentation]

[ Return to publications ]