American Institute of Mathematical Sciences

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

Bounding the bias of tree-like sampling in IP topologies

Reuven Cohen 1, , Mira Gonen 2, and  Avishai Wool 2,

1. 

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

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.
Keywords: Network Computing, Internet Topology Models.
Mathematics Subject Classification: Primary: 90B15, 90B1.
Citation: Reuven Cohen, Mira Gonen, Avishai Wool. Bounding the bias of tree-like sampling in IP topologies. Networks and Heterogeneous Media, 2008, 3 (2) : 323-332. doi: 10.3934/nhm.2008.3.323
[1]

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

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

Tingting Zhu. Emergence of synchronization in Kuramoto model with frustration under general network topology. Networks and Heterogeneous Media, 2022, 17 (2) : 255-291. doi: 10.3934/nhm.2022005
[4]

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

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
[6]

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

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

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

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

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

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

Hari Nandan Nath, Urmila Pyakurel, Tanka Nath Dhamala, Stephan Dempe. Dynamic network flow location models and algorithms for quickest evacuation planning. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2943-2970. doi: 10.3934/jimo.2020102
[13]

Hasan Hosseini-Nasab, Vahid Ettehadi. Development of opened-network data envelopment analysis models under uncertainty. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022027
[14]

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

[15]

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

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

Robert Cardona. The topology of Bott integrable fluids. Discrete and Continuous Dynamical Systems, 2022  doi: 10.3934/dcds.2022054
[18]

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

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

Kuo-Shou Chiu. Periodicity and stability analysis of impulsive neural network models with generalized piecewise constant delays. Discrete and Continuous Dynamical Systems - B, 2022, 27 (2) : 659-689. doi: 10.3934/dcdsb.2021060

2020 Impact Factor: 1.213

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy