DOC PREVIEW
UW-Madison CS 740 - Systematic Topology Analysis and Generation Using Degree Correlations

This preview shows page 1-2-3-4 out of 12 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Systematic Topology Analysis and GenerationUsing Degree CorrelationsPriya MahadevanUC San DiegoDmitri KrioukovCAIDAKevin FallIntel ResearchAmin VahdatUC San Diego{pmahadevan,vahdat}@cs.ucsd.edu, [email protected], [email protected] have proposed a variety of metrics to measureimpor tant graph properties, for instance, in social, biologi-cal, and computer networks. Values for a particular graphmetric may capture a graph’s resilience to failure or its rout-ing efficiency. Knowledge of appropriate metric values mayinfluence the engineering of future topologies, repair strate-gies in the face of failure, and understanding of fundamen-tal properties of existing networks. Unfortunately, there aretypically no algorithms to generate graphs matching one ormore proposed metrics and there is little understanding ofthe relationships among individual metrics or their applica-bility to different settings.We present a new, systematic approach for analyzing net-work topologies. We first introduce the dK-series of proba-bility distributions specifying all degree correlations withind-sized subgraphs of a given graph G. Increasing values ofd capture progressively more properties of G at the costof more complex representation of the probability distribu-tion. Using this series, we can quantitatively measure thedistance between two graphs and construct random graphsthat accurately reproduce virtually all metrics proposed inthe literature. The nature of the dK-series implies that itwill also capture any future metrics that may be proposed.Using our approach, we construct graphs for d = 0, 1, 2, 3and demonstrate that these graphs reproduce, with increas-ing accuracy, important properties of measured and modeledInternet topologies. We find that the d = 2 case is sufficientfor most practical purposes, while d = 3 essentially recon-structs the Internet AS- and router-level topologies exactly.We hope that a systematic method to analyze and synthe-size topologies offers a significant improvement to the set ofto ols available to network topology and protocol researchers.Categories and Subject DescriptorsC.2.1 [Network Architecture and Design]: Networktop ology; G.3 [Probability and Statistics]: Distributionfunctions, multivariate statistics, correlation and regressionPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.SIGCOMM’06, September 11–15, 2006, Pisa, Italy.Copyright 2006 ACM 1-59593-308-5/06/0009 ...$5.00.Measurements, observationsObserved graphsSelection and abstractionGraph metricsto reproduceNetwork evolution modelingSynthetic ‘growing’ graphsSynthetic‘static’ graphsSimulationsComparison with the observed graphs against a set of important graph propertiesTopology ProcessesExtractionConstruction ExecutionFormalizationIf graphs differ, refinements are needed:modify the set ofreproduced graph metrics (on the left)or abstracted evolution rules (on the right)Figure 1: Methodologies of network topology re-search.analysis; G.2.2 [Graph Theory]: Network problemsGeneral TermsMeasurement, Design, TheoryKeywordsNetwork topology, degree corr elations1. INTRODUCTIONKnowledge of network topology is crucial for understand-ing and predicting the performance, robustness, and scala-bility of network protocols and applications. Routing andsearching in networks, robustness to random network fail-ures and targeted attacks, the speed of wor ms spreading,and common strategies for traffic engineering and networkmanagement all depend on the topological characteristics ofa given network.Research involving network topology, particularly Inter-net topology, generally investigates the following questions:1. generation: can we efficiently generate ensembles ofrandom but “realistic” topologies by reproducing a setof simple graph metrics?2. simulations: how does some (new) protocol or appli-cation perform on a set of these “realistic” topologies?3. evolution: what are the forces driving the evolution(growth) of a given network?Figure 1 illustrates the methodologies used to answer thesequestions in its left, bottom, and right parts, respectively.Common to all of the methodologies is a set of pr actically-impor tant graph properties u sed for analyzing and compar-ing sets of graphs at the center box of the figure. Many suchproperties have been defined and explored in the literature.We briefly discuss some of them in Section 2. Unfortunately,there are no known algorithms to construct r andom graphswith given values of most of these properties, since theytypically characterize the global structure of the topology,making it difficult or impossible to algorithmically reproducethem.This paper introduces a finite set of reproducible graphproperties, the dK-series, to describe and constrain randomgraphs in successively finer detail. In the limit, these prop-erties describe any given graph completely. In our model, wemake use of probability distributions, the dK-distributions,on the subgraphs of size d in some given input graph. Wecall d K-graphs the sets of graphs constrained by given val-ues of dK-distributions. Producing a family of 0K-graphsfor a given input graph requires reproducing only the averageno de degree of the original graph, while producing a familyof 1K-graphs requires reproducing the original graph’s nodedegree distribution, the 1K-distribution. 2K-graphs repr o-duce the joint degree distribution, the 2K-distribution, ofthe original graph —the probability that two nodes of de-grees k and k′are connected. 3K-graphs consider intercon-nectivity among triples of nodes, and so forth. Generally,the set of (d + 1)K-graphs is a subset of dK-graphs. Inother words, larger values of d further constrain the num-b er of possible graphs. Overall, larger values of d captureincreasingly complex properties of the original graph. How-ever, generating dK-graphs for large values of d also becomeincreasingly computationally complex.A key contribution of this paper is to define the seriesof dK-graphs and dK-distributions and to employ them forgenerating and analyzing network topologies. Sp ecifically,we develop and implement new algorithms for


View Full Document

UW-Madison CS 740 - Systematic Topology Analysis and Generation Using Degree Correlations

Documents in this Course
Load more
Download Systematic Topology Analysis and Generation Using Degree Correlations
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Systematic Topology Analysis and Generation Using Degree Correlations and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Systematic Topology Analysis and Generation Using Degree Correlations 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?