Title: Robustness of the Internet at the topology and routing level
Authors: Erlebach, Thomas ×
Hall, Alexander
Moonen, Linda
Panconesi, Alessandro
Spieksma, Frits
Vukadinovic, Danica #
Issue Date: 2006
Publisher: Springer
Series Title: Lecture Notes in Computer Science vol:4028 pages:260-274
Conference: 2nd Workshop on Dependable System Software, Computing, Networks location:Lowenberb, GERMANY date:13-14 Oct 2005
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.
Description: Dependable systems: software, computing, networks
ISSN: 0302-9743
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Research Center for Operations Research and Business Statistics (ORSTAT), Leuven
× corresponding author
# (joint) last author

Files in This Item:
File Status SizeFormat
Robustnessoftheinternet.pdf Published 520KbAdobe PDFView/Open Request a copy

These files are only available to some KU Leuven Association staff members


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science