Mechanisms for generating realistic annotated Internet topologies

Researchers involved in designing network services and protocols rely on results from simulation and emulation environments to evaluate correctness, performance and scalability. To better understand the behavior of these applications and to predict their performance when deployed across the Internet, the generated topologies that serve as input to simulated and emulated environments must closely match real network topologies with respect to a wide range of graph metrics proposed in the literature. Values for a particular graph metric may capture a graph's resilience to failure or its routing efficiency. Unfortunately, there are typically no known algorithms to generate graphs matching one or more proposed metrics and there is little understanding of the relationships among individual metrics or their applicability to different settings. Furthermore, the generated topologies must also be annotated with observed network characteristics that, for instance, include latencies for the edges in a router- level graph, and AS membership for the nodes in the graph. Finally, it should be possible to rescale a given topology to a variety of sizes while still maintaining its essential characteristics. We present a new, systematic approach for analyzing and synthesizing network topologies. We first introduce a unifying series of properties, 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 and, in the limit, describes the graph in its entirety. Using the dK- series, we construct random graphs and demonstrate that these graphs reproduce, with increasing accuracy, all important metrics of measured and modeled Internet topologies. The nature of the dK-series implies that it will also capture any future metric that may be proposed. Further, we scale the generated graphs to a wide range of sizes while still preserving the graph's structure. Finally, we propose techniques to annotate these topologies and specifically describe our scheme to annotate Internet router graphs with AS-membership as well as whether a router is peering or interna