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:
 Generation: can we efficiently generate ensembles of
random but realistic topologies by reproducing a
set of simple graph metrics?
 Simulations: how does some (new) protocol or application
perform on a set of these realistic topologies?
 Evolution: what are the forces driving the evolution
(growth) of the topology of a given network?
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 practicallyimportant
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 dKseries, 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 dKgraphs the sets of graphs constrained by such distributions.
Producing a family of 0Kgraphs for a given
input graph requires reproducing only the average node
degree of the original graph, while producing a family of
1Kgraphs requires reproducing the original graph's node
degree distribution. 2Kgraphs 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. 3Kgraphs consider triples of connected nodes, and so
forth. Generally, the set of (d + 1)Kgraphs is a subset
of dKgraphs. That is, larger values of d further constrain
the number of possible graphs. Generating dKgraphs becomes increasingly computationally
difficult as d increases.
We develop and implement new algorithms
for constructing 2K and 3Kgraphs (algorithms to generate
0K and 1Kgraphs are already known).
Using a variety of measured and modeled Internet AS and
routerlevel topologies as input, we use our graph
generators to show how the space of dKgraphs 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 dKgraphs generated using our approach to show the convergence
of the dKseries.
The above picture depicts
random 0K, 1K, 2K and 3Kgraphs matching
the corresponding distributions of the HOT graph,
a representative routerlevel topology. This
topology is a particularly interesting case, because, to
date reproducing routerlevel topologies using only degree
distributions has proven difficult since routerlevel
topologies are more engineered and consequently
less random. However, a visual inspection of our generated
topologies shows good convergence properties of
the dKseries, with the 0Kgraph and 1Kgraph very
far from the original HOT topology, the 2Kgraph 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 3Krandom graphs as described above.
The code will be available for download soon !
Please contact Priya Mahadevan if you have any questions.