Bounding the bias of tree-like sampling in IP topologies

Previous Article
Graph theory and qualitative analysis of reaction networks
NHM Home
This Issue
Next Article
The simulation of gene knock-out in scale-free random Boolean models of genetic networks

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

Abstract
Related Papers

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 & 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 & 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 & Continuous Dynamical Systems - B, 2017, 22 (10) : 3749-3770. doi: 10.3934/dcdsb.2017187
[3]	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
[4]	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
[5]	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
[6]	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
[7]	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
[8]	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
[9]	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
[10]	Bruce Hughes. Geometric topology of stratified spaces. Electronic Research Announcements, 1996, 2: 73-81.
[11]	Guizhen Cui, Wenjuan Peng, Lei Tan. On the topology of wandering Julia components. Discrete & Continuous Dynamical Systems - A, 2011, 29 (3) : 929-952. doi: 10.3934/dcds.2011.29.929
[12]	Fengbo Hang, Fanghua Lin. Topology of Sobolev mappings IV. Discrete & Continuous Dynamical Systems - A, 2005, 13 (5) : 1097-1124. doi: 10.3934/dcds.2005.13.1097
[13]	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
[14]	James C. Robinson. Computing inertial manifolds. Discrete & Continuous Dynamical Systems - A, 2002, 8 (4) : 815-833. doi: 10.3934/dcds.2002.8.815
[15]	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
[16]	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
[17]	Shuren Liu, Qiying Hu, Yifan Xu. Optimal inventory control with fixed ordering cost for selling by internet auctions. Journal of Industrial & Management Optimization, 2012, 8 (1) : 19-40. doi: 10.3934/jimo.2012.8.19
[18]	Shu Zhang, Yuan Yuan. The Filippov equilibrium and sliding motion in an internet congestion control model. Discrete & Continuous Dynamical Systems - B, 2017, 22 (3) : 1189-1206. doi: 10.3934/dcdsb.2017058
[19]	Flavio Abdenur, Lorenzo J. Díaz. Pseudo-orbit shadowing in the $C^1$ topology. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 223-245. doi: 10.3934/dcds.2007.17.223
[20]	M. Delgado-Téllez, Alberto Ibort. On the geometry and topology of singular optimal control problems and their solutions. Conference Publications, 2003, 2003 (Special) : 223-233. doi: 10.3934/proc.2003.2003.223

2018 Impact Factor: 0.871

American Institute of Mathematical Sciences