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

ABSTRACT

Understanding the structure of the Internet graph is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtaining its graph structure is a surprisingly difficult task, as edges cannot be explicitly queried. Instead, empirical studies rely on traceroutes to build what are essentially single-source, all-destinations, shortest-path trees. These trees only sample a fraction of the network's edges, and a recent paper by Lakhina et al. found empirically that the resuting sample is intrinsically biased. For instance, the observed degree distribution under traceroute sampling exhibits a power law even when the underlying degree distribution is Poisson.In this paper, we study the bias of traceroute sampling systematically, and, for a very general class of underlying degree distributions, calculate the likely observed distributions explicitly. To do this, we use a continuous-time realization of the process of exposing the BFS tree of a random graph with a given degree distribution, calculate the expected degree distribution of the tree, and show that it is sharply concentrated. As example applications of our machinery, we show how 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: L. Amini, A. Shaikh, and H. Schulzrinne. Issues with inferring Internet topological attributes. In SPIE IT-Com, 2002.
• 2: 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]
• 3: B. Bollobás. Random graphs. Academic Press, 1985.
• 4: 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]
• 5: Q. Chen, H. Chang, R. Govindan, S. Jamin, S. J. Shenker, and W. Willinger. The origin of power laws in Internet topologies revisited. In Proc. 21st ACM SIGCOMM Conference, 2002.
• 6: A. Clauset and C. Moore. Accuracy and scaling phenomena in Internet mapping. Physical Review Letters, 94:018701, 2005.
• 7: P. Erdős and A. Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci., 5:17--61, 1960.
• 8: 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
• 9: 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
• 10: R. Govindan and H. Tangmunarunkit. Heuristics for Internet map discovery. In Proc. 19th ACM SIGCOMM Conference, 2000.
• 11: W. Hoeffding. Probability inequalities for sums of bounded random variables. J. of the American Statistical Association, 58:13--30, 1963.
• 12: J. H. Kim. Poisson cloning model for random graphs. Preprint, 2004.
• 13: J. Kleinberg, S. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. The web as a graph: Measurements, models and methods. In Intl. Conf. on Combinatorics and Computing, 1999.
• 14: A. Lakhina, J. Byers, M. Crovella, and P. Xie. Sampling biases in IP topology measurements. In Proc. 22nd ACM SIGCOMM Conference, 2003.
• 15: J. Leguay, M. Latapy, T. Friedman, and K. Salamatian. Describing and simulating internet routes. Preprint cs.NI/0411051, 2004.
• 16: C. McDiarmid. Concentration. In M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, editors, Probabilistic Methods for Algorithmic Discrete Mathematics, pages 195--247. Springer, 1998.
• 17: M. Mihail, C. Papadimitriou, and A. Saberi. On certain connectivity properties of the Internet topology. In Proc. 35th ACM Symp. on Theory of Computing, 2003.
• 18: 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
• 19: 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]
• 20: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 21: 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]
• 22: T. Petermann and P. De Los Rios. Exploration of scale-free networks: do we measure the real exponents? Euro. Phys. Journal B, 38:201, 2004.
• 23: James B. Seaborn, Hypergeometric functions and their applications, Springer-Verlag, London, 1991
• 24: J. Spanier and K.B. Oldham. The exponential integral ei(x) and related functions. In An Atlas of Functions, chapter 37, pages 351--360. Hemisphere, 1987.
• 25: Herbert S. Wilf, Generating functionology, Academic Press Professional, Inc., San Diego, CA, 1990
• 26: N.C. Wormald. Models of random regular graphs. In J. Lamb and D. Preece, editors, London Math. Soc. Lecture Note Series, volume 276, pages 239--298. Cambridge University Press, 1999.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Theory

Keywords:
internet mapping, power laws, random graphs