Robustness of the internet at the topology and routing level

T. Erlebach, A.R. Hall, L.S. Moonen, A. Panconesi, F.C.R. Spieksma, D. Vukadinovic

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

4 Citations (Scopus)

Abstract

Classical measures of network robustness are the number of disjoint paths between two nodes and the size of a smallest cut separating them. In the Internet, the paths that traffic can take are constrained by the routing policies of the individual autonomous systems (ASs). These policies mainly depend on the economic relationships between ASs, e.g., customer-provider or peer-to-peer. Paths that are consistent with these policies can be modeled as valley-free paths. We give an overview of existing approaches to the inference of AS relationships, and we survey recent results concerning the problem of computing a maximum number of disjoint valley-free paths between two given nodes, and the problem of computing a smallest set of nodes whose removal disconnects two given nodes with respect to all valley-free paths. For both problems, we discuss NP-hardness and inapproximability results, approximation algorithms, and exact algorithms based on branch-and-bound techniques. We also summarize experimental findings that have been obtained with these algorithms in a comparison of different graph models of the AS-level Internet with respect to robustness properties.
Original languageEnglish
Title of host publicationDependable systems: software, computing, networks
Subtitle of host publicationresearch results of the DICS program
EditorsJ. Kohlas, B. Meyer, A. Schiper
Place of PublicationBerlin
PublisherSpringer
Chapter12
Pages260-274
Number of pages15
ISBN (Electronic)978-3-540-36823-6
ISBN (Print)978-3-540-36821-2
DOIs
Publication statusPublished - 2006
Externally publishedYes

Publication series

NameLecture Notes in Computer Science (LNCS)
Volume4028
ISSN (Print)0302-9743

Cite this

Erlebach, T., Hall, A. R., Moonen, L. S., Panconesi, A., Spieksma, F. C. R., & Vukadinovic, D. (2006). Robustness of the internet at the topology and routing level. In J. Kohlas, B. Meyer, & A. Schiper (Eds.), Dependable systems: software, computing, networks: research results of the DICS program (pp. 260-274). (Lecture Notes in Computer Science (LNCS); Vol. 4028). Berlin: Springer. https://doi.org/10.1007/11808107_12