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 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.
