June  2008, 3(2): 323-332. doi: 10.3934/nhm.2008.3.323

Bounding the bias of tree-like sampling in IP topologies


Department of Mathematics, Bar-Ilan University, Ramat-Gan 52900, Israel


School of Electrical Engineering, Tel Aviv University, Ramat Aviv 69978, Israel, Israel

Received  September 2007 Revised  January 2008 Published  March 2008

It is widely believed that the Internet's AS-graph degree distribution obeys a power-law form. However, it was recently argued that since Internet data is collected in a tree-like fashion, it only produces a sample of the degree distribution, and this sample may be biased. This argument was backed by simulation data and mathematical analysis, which demonstrated that under certain conditions a tree sampling procedure can produce an artificial power-law in the degree distribution. Thus, although the observed degree distribution of the AS-graph follows a power-law, this phenomenon may be an artifact of the sampling process. In this work we provide some evidence to the contrary. We show, by analysis and simulation, that when the underlying graph degree distribution obeys a power-law with an exponent $\gamma>2$, a tree-like sampling process produces a negligible bias in the sampled degree distribution. Furthermore, recent data collected from the DIMES project, which is not based on single source sampling, indicates that the Internet indeed obeys a power-law degree distribution with an exponent $\gamma>2$. Combining this empirical data with our simulation of traceroute experiments on DIMES-measured AS-graph as the underlying graph, and with our analysis, we conclude that the bias in the degree distribution calculated from BGP data is negligible.
Citation: Reuven Cohen, Mira Gonen, Avishai Wool. Bounding the bias of tree-like sampling in IP topologies. Networks & Heterogeneous Media, 2008, 3 (2) : 323-332. doi: 10.3934/nhm.2008.3.323

D. Alderson, H. Chang, M. Roughan, S. Uhlig, W. Willinger. The many facets of internet topology and traffic. Networks & Heterogeneous Media, 2006, 1 (4) : 569-600. doi: 10.3934/nhm.2006.1.569


Shuping Li, Zhen Jin. Impacts of cluster on network topology structure and epidemic spreading. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3749-3770. doi: 10.3934/dcdsb.2017187


T. S. Evans, A. D. K. Plato. Network rewiring models. Networks & Heterogeneous Media, 2008, 3 (2) : 221-238. doi: 10.3934/nhm.2008.3.221


Inom Mirzaev, David M. Bortz. A numerical framework for computing steady states of structured population models and their stability. Mathematical Biosciences & Engineering, 2017, 14 (4) : 933-952. doi: 10.3934/mbe.2017049


Alberto Bressan, Khai T. Nguyen. Conservation law models for traffic flow on a network of roads. Networks & Heterogeneous Media, 2015, 10 (2) : 255-293. doi: 10.3934/nhm.2015.10.255


Gabriel Montes-Rojas, Pedro Elosegui. Network ANOVA random effects models for node attributes. Journal of Dynamics & Games, 2020, 7 (3) : 239-252. doi: 10.3934/jdg.2020017


Simone Göttlich, Stephan Knapp. Semi-Markovian capacities in production network models. Discrete & Continuous Dynamical Systems - B, 2017, 22 (9) : 3235-3258. doi: 10.3934/dcdsb.2017090


Claus Kirchner, Michael Herty, Simone Göttlich, Axel Klar. Optimal control for continuous supply network models. Networks & Heterogeneous Media, 2006, 1 (4) : 675-688. doi: 10.3934/nhm.2006.1.675


Hari Nandan Nath, Urmila Pyakurel, Tanka Nath Dhamala, Stephan Dempe. Dynamic network flow location models and algorithms for quickest evacuation planning. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020102


Tanka Nath Dhamala. A survey on models and algorithms for discrete evacuation planning network problems. Journal of Industrial & Management Optimization, 2015, 11 (1) : 265-289. doi: 10.3934/jimo.2015.11.265


Gunhild A. Reigstad. Numerical network models and entropy principles for isothermal junction flow. Networks & Heterogeneous Media, 2014, 9 (1) : 65-95. doi: 10.3934/nhm.2014.9.65


Bruce Hughes. Geometric topology of stratified spaces. Electronic Research Announcements, 1996, 2: 73-81.


Guizhen Cui, Wenjuan Peng, Lei Tan. On the topology of wandering Julia components. Discrete & Continuous Dynamical Systems, 2011, 29 (3) : 929-952. doi: 10.3934/dcds.2011.29.929


Fengbo Hang, Fanghua Lin. Topology of Sobolev mappings IV. Discrete & Continuous Dynamical Systems, 2005, 13 (5) : 1097-1124. doi: 10.3934/dcds.2005.13.1097


Yu-Jhe Huang, Zhong-Fu Huang, Jonq Juang, Yu-Hao Liang. Flocking of non-identical Cucker-Smale models on general coupling network. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1111-1127. doi: 10.3934/dcdsb.2020155


Kuo-Shou Chiu. Periodicity and stability analysis of impulsive neural network models with generalized piecewise constant delays. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021060


Dengfeng Sun, Issam S. Strub, Alexandre M. Bayen. Comparison of the performance of four Eulerian network flow models for strategic air traffic management. Networks & Heterogeneous Media, 2007, 2 (4) : 569-595. doi: 10.3934/nhm.2007.2.569


James C. Robinson. Computing inertial manifolds. Discrete & Continuous Dynamical Systems, 2002, 8 (4) : 815-833. doi: 10.3934/dcds.2002.8.815


Shunfu Jin, Wuyi Yue, Zhanqiang Huo. Performance evaluation for connection oriented service in the next generation Internet. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 749-761. doi: 10.3934/naco.2011.1.749


Shu Zhang, Jian Xu. Time-varying delayed feedback control for an internet congestion control model. Discrete & Continuous Dynamical Systems - B, 2011, 16 (2) : 653-668. doi: 10.3934/dcdsb.2011.16.653

2019 Impact Factor: 1.053


  • PDF downloads (29)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]