A Comparative Analysis of Geometric Graph Models For Modelling Backbone Networks
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.
E. K. Çetinkaya et al., "A Comparative Analysis of Geometric Graph Models For Modelling Backbone Networks," Optical Switching and Networking, no. PART 2, pp. 95-106, Elsevier, Jan 2014.
The definitive version is available at http://dx.doi.org/10.1016/j.osn.2014.05.001
Electrical and Computer Engineering
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)
Electronic OCLC #
Print OCLC #
Article - Journal
© 2014 Elsevier, All rights reserved.