On the bias of traceroute sampling
Authors:
Open Access
- 1 June 2009
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 56 (4) , 1-28
Abstract
Understanding the graph structure of the Internet is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtaining this graph structure can be a surprisingly difficult task, as edges cannot be explicitly queried. For instance, empirical studies of the network of Internet Protocol (IP) addresses typically rely on indirect methods liketracerouteto build what are approximately single-source, all-destinations, shortest-path trees. These trees only sample a fraction of the network's edges, and a paper by Lakhina et al. [2003] found empirically that the resulting sample is intrinsically biased. Further, in simulations, they observed that the degree distribution under traceroute sampling exhibits a power law even when the underlying degree distribution is Poisson.In this article, we study the bias of traceroute sampling mathematically and, for a very general class of underlying degree distributions, explicitly calculate the distribution that will be observed. As example applications of our machinery, we prove that traceroute sampling finds power-law degree distributions in both δ-regular and Poisson-distributed random graphs. Thus, our work puts the observations of Lakhina et al. on a rigorous footing, and extends them to nearly arbitrary degree distributions.Keywords
Funding Information
- National Science Foundation (ITR-0324845PHY-0200909CCF-0524613CCR-0220070EIA-0218563ITR-0324845)
- Division of Computing and Communication Foundations (CCF-0546900, ITR-0324845PHY-0200909CCF-0524613CCR-0220070EIA-0218563ITR-0324845)
- European Research Council (210743)
- Division of Physics (ITR-0324845PHY-0200909CCF-0524613CCR-0220070EIA-0218563ITR-0324845)
This publication has 17 references indexed in Scilit:
- Distance distribution in random graphs and application to network explorationPhysical Review E, 2007
- Dynamic exploration of networks: from general principles to the traceroute processThe European Physical Journal B, 2007
- Describing and simulating internet routesComputer Networks, 2007
- Relevance of massively distributed explorations of the Internet topology: Qualitative resultsComputer Networks, 2006
- Exploring networks with traceroute-like probes: Theory and simulationsTheoretical Computer Science, 2006
- DIMESACM SIGCOMM Computer Communication Review, 2005
- Accuracy and Scaling Phenomena in Internet MappingPhysical Review Letters, 2005
- Exploration of scale-free networksThe European Physical Journal B, 2004
- Measuring ISP Topologies With RocketfuelIEEE/ACM Transactions on Networking, 2004
- On routes and multicast trees in the InternetACM SIGCOMM Computer Communication Review, 1998