Multilevel Resilience Analysis of Transportation and Communication Networks

Abstract

For many years the research community has attempted to model the Internet in order to better understand its behaviour and improve its performance. Since much of the structural complexity of the Internet is due to its multilevel operation, the Internet's multilevel nature is an important and non-trivial feature that researchers must consider when developing appropriate models. In this paper, we compare the normalised Laplacian spectra of physical- and logical-level topologies of four commercial ISPs and two research networks against the US freeway topology, and show analytically that physical level communication networks are structurally similar to the US freeway topology. We also generate synthetic Gabriel graphs of physical topologies and show that while these synthetic topologies capture the grid-like structure of actual topologies, they are more expensive than the actual physical level topologies based on a network cost model. Moreover, we introduce a distinction between geographic graphs that include degree-2 nodes needed to capture the geographic paths along which physical links follow, and structural graphs that eliminate these degree-2 nodes and capture only the interconnection properties of the physical graph and its multilevel relationship to logical graph overlays. Furthermore, we develop a multilevel graph evaluation framework and analyse the resilience of single and multilevel graphs using the flow robustness metric. We then confirm that dynamic routing performed over the lower levels helps to improve the performance of a higher level service, and that adaptive challenges more severely impact the performance of the higher levels than non-adaptive challenges.

Department(s)

Electrical and Computer Engineering

Sponsor(s)

National Science Foundation (U.S.)

Keywords and Phrases

Complex Networks; Critical Infrastructures; Flow Graphs; Graphic Methods; Internet; Internet Service Providers; Algebraic Connectivity; Attack; Dependability; Gabriel Graph; Geographic Graph; Graph Spectra; Multilevel Graph; Network Costs; Network Science; Performability; Resilience; Spectral Radii; Structural Graph; Survivability; Topology

International Standard Serial Number (ISSN)

1018-4864

Electronic OCLC #

43066372

Print OCLC #

27233357

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2015 Springer-Verlag, All rights reserved.

Publication Date

01 Jan 2015

Link to Full Text

Share

 
COinS