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

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

• 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.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

General Terms:
Measurement, Reliability, Theory

Keywords:
Internet topology, sampling bias, traceroute