On the bias of traceroute sampling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs

Full text

Pdf (210 KB)

Source

Journal of the ACM (JACM) archive
Volume 56 , Issue 4 (June 2009) table of contents

Article No. 21

Year of Publication: 2009

ISSN:0004-5411

Authors

Dimitris Achlioptas	University of California, Santa Cruz, CA
Aaron Clauset	University of New Mexico, Albuquerque, and the Santa Fe Institute, New Mexico
David Kempe	University of Southern California, Los Angeles, CA
Cristopher Moore	University of New Mexico, Albuquerque, and the Santa Fe Institute, New Mexico

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 26, Downloads (12 Months): 185, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1538902.1538905 What is a DOI?

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 like traceroute to 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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	David Alderson , Lun Li , Walter Willinger , John C. Doyle, Understanding internet topology: principles, models, and validation, IEEE/ACM Transactions on Networking (TON), v.13 n.6, p.1205-1218, December 2005 [doi>10.1109/TNET.2005.861250]
	2	Amini, L., Shaikh, A., and Schulzrinne, H. 2002. Issues with inferring Internet topological attributes. In SPIE IT-Com.
	3	Paul Barford , Azer Bestavros , John Byers , Mark Crovella, On the marginal utility of network topology measurements, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505204]
	4	Blondel, V., Guillaume, J.-L., Hendrickx, J., and Jungers, R. 2007. Distance distribution in random graphs and application to network exploration. Phys. Rev. E 76, 066101.
	5	Bollobás, B. 2001. Random Graphs, 2nd ed. Cambridge University Press, Cambridge.
	6	B. Bollobás , F. R. K. Chung, The diameter of a cycle plus a random matching, SIAM Journal on Discrete Mathematics, v.1 n.3, p.328-333, Aug. 1988 [doi>10.1137/0401033]
	7	Chen, Q., Chang, H., Govindan, R., Jamin, S., Shenker, S., and Willinger, W. 2002. The origin of power laws in Internet topologies revisited. In Proceedings of the 21st ACM SIGCOMM Conference. ACM, New York.
	8	Clauset, A., and Moore, C. 2005. Accuracy and scaling phenomena in Internet mapping. Phys. Rev. Lett. 94, 018701.
	9	Cohen, R., Gonen, M., and Wool, A. 2007. Bounding the bias of tree-like sampling in ip topologies. In Proceedings of the European Conference on Complex Systems (ECCS).
	10	Dall'Asta, L. 2007. Dynamic exploration of networks: From general principles to the traceroute process. Europ. Phys. J. B 60, 123--133.
	11	Luca Dall'Asta , Ignacio Alvarez-Hamelin , Alain Barrat , Alexei Vázquez , Alessandro Vespignani, Exploring networks with traceroute-like probes: theory and simulations, Theoretical Computer Science, v.355 n.1, p.6-24, 6 April 2006 [doi>10.1016/j.tcs.2005.12.009]
	12	Erdős, P., and Rényi, A. 1960. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5, 17--61.
	13	Alex Fabrikant , Elias Koutsoupias , Christos H. Papadimitriou, Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.110-122, July 08-13, 2002
	14	Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
	15	Flaxman, A., and Vera, J. 2007. Bias reduction in traceroute sampling: Towards a more accurate map of the internet. In Proceedings of the 5th Workshop on Algorithms and Models for the Web-Graph (WAW2007).
	16	Govindan, R., and Tangmunarunkit, H. 2000. Heuristics for Internet map discovery. In Proceedings of the 19th ACM SIGCOMM Conference. ACM, New York.
	17	Jean-Loup Guillaume , Matthieu Latapy , Damien Magoni, Relevance of massively distributed explorations of the internet topology: qualitative results, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.16, p.3197-3224, 14 November 2006 [doi>10.1016/j.comnet.2005.12.010]
	18	Hoeffding, W. 1963. Probability inequalities for sums of bounded random variables. J. ASA 58, 13--30.
	19	Kim, J. H. 2006. Poisson cloning model for random graphs. Preprint.
	20	Kleinberg, J., Kumar, R., Raghavan, P., Rajagopalan, S., and Tomkins, A. 1999. The web as a graph: Measurements, models and methods. In Proceedings of the International Conference on Combinatorics and Computing.
	21	Lakhina, A., Byers, J., Crovella, M., and Xie, P. 2003. Sampling biases in IP topology measurements. In Proceedings of the 22nd IEEE INFOCOM Conference. IEEE Computer Society Press, Los Alamitos.
	22	Jérémie Leguay , Matthieu Latapy , Timur Friedman , Kavé Salamatian, Describing and simulating internet routes, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.8, p.2067-2085, June, 2007 [doi>10.1016/j.comnet.2006.10.008]
	23	McDiarmid, C. 1998. Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics, M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, Eds. Springer-Verlag, Berlin, Germany, 195--247.
	24	Mihail, M., Papadimitriou, C., and Saberi, A. 2003. On certain connectivity properties of the Internet topology. In Proceedings of the 35th ACM Symposium on Theory of Computing. ACM, New York.
	25	Michael Molloy , Bruce Reed, A critical point for random graphs with a given degree sequence, Random Structures & Algorithms, v.6 n.2/3, p.161-179, March-May 1995
	26	Michael Molloy , Bruce Reed, The Size of the Giant Component of a Random Graph with a Given Degree Sequence, Combinatorics, Probability and Computing, v.7 n.3, p.295-305, September 1998 [doi>10.1017/S0963548398003526]
	27	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	28	Jean-Jacques Pansiot , Dominique Grad, On routes and multicast trees in the Internet, ACM SIGCOMM Computer Communication Review, v.28 n.1, p.41-50, Jan. 1998 [doi>10.1145/280549.280555]
	29	Petermann, T., and De Los Rios, P. 2004. Exploration of scale-free networks: Do we measure the real exponents? Euro. Phys. J. B 38, 201--204.
	30	James B. Seaborn, Hypergeometric functions and their applications, Springer-Verlag, London, 1991
	31	Yuval Shavitt , Eran Shir, DIMES: let the internet measure itself, ACM SIGCOMM Computer Communication Review, v.35 n.5, October 2005 [doi>10.1145/1096536.1096546]
	32	Spanier, J., and Oldham, K. 1987. The exponential integral ei(x) and related functions. In An Atlas of Functions. Hemisphere, Chapter 37, 351--360.
	33	Neil Spring , Ratul Mahajan , David Wetherall , Thomas Anderson, Measuring ISP topologies with rocketfuel, IEEE/ACM Transactions on Networking (TON), v.12 n.1, p.2-16, February 2004 [doi>10.1109/TNET.2003.822655]
	34	Tangmunarunkit, H., Govindan, R., Shenker, S., and Estrin, D. 2001. The impact of policy on Internet paths. In Proceedings of the 20th IEEE INFOCOM Conference. IEEE Computer Society Press, Los Alamitos.
	35	Viger, F., Augustin, B., Cuvellier, X., Magnien, C., Latapy, M., Friedman, T., and Teixeira, R. 2006. Detection, understanding, and prevention of traceroute measurement artifacts. In Proceedings of the 6th Internet Measurement Conference (IMC'06).
	36	Herbert S. Wilf, Generating functionology, Academic Press Professional, Inc., San Diego, CA, 1990
	37	Wormald, N. 1999. Models of random regular graphs. In London Math. Soc. Lecture Note Series, J. Lamb and D. Preece, Eds. Vol. 276. Cambridge University Press, Cambridge. 239--298.