Systematic Topology Analysis and Generation Using Degree Correlations

Details Systematic Topology Analysis and Generation Using Degree Correlations Systematic Topology Analysis and Generation Using Degree Correlations

2006-05-02

arxiv.org/abs/cs/0605007v2

SIGCOMM 2006 (ACM SIGCOMM Computer Communication Review (CCR), v.36, n.4, p.135-146, 2006)

Computer Science

Networking and Internet Architecture

Final version

Scientific paper

10.1145/1151659.1159930

We present a new, systematic approach for analyzing network topologies. We first introduce the dK-series of probability distributions specifying all degree correlations within d-sized subgraphs of a given graph G. Increasing values of d capture progressively more properties of G at the cost of more complex representation of the probability distribution. Using this series, we can quantitatively measure the distance between two graphs and construct random graphs that accurately reproduce virtually all metrics proposed in the literature. The nature of the dK-series implies that it will also capture any future metrics that may be proposed. Using our approach, we construct graphs for d=0,1,2,3 and demonstrate that these graphs reproduce, with increasing accuracy, important properties of measured and modeled Internet topologies. We find that the d=2 case is sufficient for most practical purposes, while d=3 essentially reconstructs the Internet AS- and router-level topologies exactly. We hope that a systematic method to analyze and synthesize topologies offers a significant improvement to the set of tools available to network topology and protocol researchers.

Affiliated with

Also associated with

No associations

Rating

Systematic Topology Analysis and Generation Using Degree Correlations 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 Systematic Topology Analysis and Generation Using Degree Correlations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systematic Topology Analysis and Generation Using Degree Correlations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-184256