Analyzing and Generating Network Topologies with Orbis

Release

The latest alpha release (version 0.70a) of Orbis be found here. Orbis requires Boost 1.32 or later as well as the Boost program_options library.

Overview

Knowledge of network topology is crucial for understanding and predicting the performance, robustness, and scalability of network protocols and applications. Routing and searching in networks, robustness to random network failures and targeted attacks, the speed of virus spreading, and common strategies for traffic engineering and network management all depend on the topological characteristics of a given network. Research involving network topology, particularly Internet topology, generally investigates the following questions:
The above figure illustrates the relationships between these questions and the use of network topology information. The methodologies from this list correspond to the left, bottom, and right of the figure, respectively. Common to all of the methodologies is a set of practically-important graph properties used for generating or analyzing a set of graphs. Many such properties have been defined and explored in the literature. Unfortunately, there are no known algorithms to construct random graphs with given values for most of these properties. The properties typically characterize the global structure of the topology, making it difficult or impossible to algorithmically reproduce them. We introduce a finite set of enumerable graph properties, the dK-series, to describe and constrain random graphs in successively finer detail. In the limit, these properties describe any graph completely. In our model, we make use of probability distributions on subgraphs of size d in some given input graph. We call dK-graphs the sets of graphs constrained by such distributions. Producing a family of 0K-graphs for a given input graph requires reproducing only the average node degree of the original graph, while producing a family of 1K-graphs requires reproducing the original graph's node degree distribution. 2K-graphs reproduce the joint degree distribution of the original graph as well the probability that a node of degree k1 is connected to a node of degree k2. 3K-graphs consider triples of connected nodes, and so forth. Generally, the set of (d + 1)K-graphs is a subset of dK-graphs. That is, larger values of d further constrain the number of possible graphs. Generating dK-graphs becomes increasingly computationally difficult as d increases. We develop and implement new algorithms for constructing 2K- and 3K-graphs (algorithms to generate 0K- and 1K-graphs are already known). Using a variety of measured and modeled Internet AS and router-level topologies as input, we use our graph generators to show how the space of dK-graphs matching the measured property of the original graph becomes increasingly constrained as we increase d. Further, as we increase d, our randomly generated graphs capture an increasingly larger set of important graph properties proposed in the topology generation and analysis literature. We find that for the class of input graphs we consider, reproducing a graph's 3K distribution is sufficient to accurately reproduce all graph properties we have encountered so far.

Topology Comparisons

We present visualizations of dK-graphs generated using our approach to show the convergence of the dK-series.
The above picture depicts random 0K-, 1K-, 2K- and 3K-graphs matching the corresponding distributions of the HOT graph, a representative router-level topology. This topology is a particularly interesting case, because, to date reproducing router-level topologies using only degree distributions has proven difficult since router-level topologies are more engineered and consequently less random. However, a visual inspection of our generated topologies shows good convergence properties of the dK-series, with the 0K-graph and 1K-graph very far from the original HOT topology, the 2K-graph much closer than the previous ones and the 3K graphs almost identical to the original.

Publications

  • " Orbis: Rescaling Degree Correlations to Generate Annotated Internet Topologies "
    Priya Mahadevan, Calvin Hubble, Dmitri Krioukov, Bradley Huffaker, and Amin Vahdat.
    Proceedings of the ACM SIGCOMM Conference, Kyoto, Japan, August 2007.
  • " Systematic Topology Analysis and Generation Using Degree Coorelations "
    Priya Mahadevan , Dmitri Krioukov, Kevin Fall, and Amin Vahdat.
    Proceedings of the ACM SIGCOMM Conference, Pisa, Italy, September 2006.
  • " Impact of Degree Correlations on Topology Generators",
    Priya Mahadevan, Amin Vahdat, Dmitri Krioukov, Brad Huffaker and kc claffy.
    Poster at ACM SIGCOMM, Philadelphia, August 2005
  • Orbis

    Orbis is a topology generator suite for generating 0K, 1K, 2K and 3K-random graphs as described above.

    The code will be available for download soon !

    Please contact Priya Mahadevan if you have any questions.