A Comparative Analysis of Geometric Graph Models For Modelling Backbone Networks

Abstract

Many researchers have studied Internet topology, and the analysis of complex and multilevel Internet structure is nontrivial. The emphasis of these studies has been on logical level topologies, however physical level topologies are necessary to study resilience realistically, given the geography and multilevel nature of the Internet. In this paper, we investigate the representativeness of the synthetic Gabriel, geometric, population-weighted geographical threshold, and location-constrained Waxman graph models to the actual fibre backbone networks of six providers. We quantitatively analyse the structure of the synthetic geographic topologies whose node locations are given by those of actual physical level graphs using well-known graph metrics, graph spectra, and the visualisation tool we have developed. Our results indicate that the synthetic Gabriel graphs capture the grid-like structure of physical level networks best. Furthermore, given that the cost of physical level topologies is an important aspect from a design perspective, we also compare the cost of synthetically generated geographic graphs and find that the synthetic Gabriel graphs achieve the smallest cost among all the graph models that we consider. Finally, based on our findings we propose a graph generation method to model physical level topologies, and show that it captures both grid and star structures ideally.

Department(s)

Electrical and Computer Engineering

Sponsor(s)

National Science Foundation (U.S.)

Keywords and Phrases

Complex Networks; Costs; Geometry; Graphic Methods; Internet; Back-Bone Network; Connectivity; Gabriel Graph; Geometric Graphs; Graph Metrics; Graph Spectra; Network Costs; Physical Level; Resilience; Threshold Graphs; Waxman Graph; Weighted Graph; Graph Theory

International Standard Serial Number (ISSN)

1573-4277

Electronic OCLC #

740974881

Print OCLC #

61878277

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2014 Elsevier, All rights reserved.

Publication Date

01 Jan 2014

Link to Full Text

Share

 
COinS