Bounding the Bias of Tree-Like Sampling in IP Topologies

Details Bounding the Bias of Tree-Like Sampling in IP Topologies Bounding the Bias of Tree-Like Sampling in IP Topologies

2006-11-30

arxiv.org/abs/cs/0611157v1

Computer Science

Networking and Internet Architecture

12 pages, 1 figure

Scientific paper

It is widely believed that the Internet's AS-graph degree distribution obeys a power-law form. Most of the evidence showing the power-law distribution is based on BGP data. However, it was recently argued that since BGP collects data 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 artificail 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 larger than 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 BGP sampling, indicates that the underlying AS-graph indeed obeys a power-law degree distribution with an exponent larger than 2. By combining this empirical data with our analysis, we conclude that the bias in the degree distribution calculated from BGP data is negligible.

Affiliated with

Also associated with

No associations

Rating

Bounding the Bias of Tree-Like Sampling in IP Topologies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bounding the Bias of Tree-Like Sampling in IP Topologies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounding the Bias of Tree-Like Sampling in IP Topologies will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-422695