On the fitness of geographic graph generators for modelling physical level topologies

Abstract

The Internet topology has been studied extensively for decades. However, the emphasis of Internet topology research has been on logical level topologies. On the other hand, physical level topologies are necessary to study the resilience of networks realistically. In this paper, we analyse the structure of synthetic geographic topologies whose node locations are given by those of actual physical level graphs. Our results indicate that the synthetic Gabriel graphs capture the grid-like structure of physical level networks. Moreover, given that the cost of physical level topologies is an important aspect from a design perspective, we also compare the cost of several synthetically generated geographic graphs and find that the synthetic Gabriel graphs achieve the smallest cost among all of the graph models that we consider.