printlogo
ETH Zuerich - Homepage
Computer Engineering and Networks Laboratory (TIK)
 
ETH Zurich - ITET - TIK - Publications
print
  

Publication Details for Article "k-fault tolerance of the Internet AS graph"

 

 Back

 New Search

 

Authors: Wenping Deng, Merkourios Karaliopoulos, Wolfgang Mühlbauer, Peidong Zhu
Group: Communication Systems
Type: Article
Title: k-fault tolerance of the Internet AS graph
Year: 2011
Pub-Key: Mue11b
Journal: Computer Networks
Volume: 55
Number: 10
Pages: 2492-2503
Abstract: Internet disruptions such as the Northeast Blackout (2003) and the Taiwan earthquake (2006) highlight the fragility of today’s Internet. Our goal in this paper is to investigate the robustness of inter-domain communication at the level of autonomous systems (ASes), taking into account both topological connectivity and compliance to routing policies. To this end, we introduce the concept of k-fault tolerance for Type-of-Relationship (ToR) graphs, which requires that any two nodes (ASes) remain reachable from each other even after removing arbitrary k nodes from the AS graph. Our main contribution is theoretical and concerns the complexity of the k-fault tolerance decision problem. Drawing on strong evidence about the hierarchical structure of the Internet AS graph, we derive sufficient and necessary conditions for determining whether the graph is k-fault tolerant or not in polynomial time. We then apply this theoretical result to study the network-wide resilience properties of AS-level topology instances, as inferred from large-scale experimental data sets. We find that even single-node failures can disconnect up to hundred of ASes and that approximately 1500 ASes do not avail any real redundancy for their global reachability despite having two or more upstream links. Augmenting AS-level graphs for 1-fault tolerance improves overall resilience to failures, but requires a considerable number of AS-level edges (>7000) to be added. Interestingly, such additional upstream links are mainly needed at stub networks rather than at transit ASes, pointing out the need for multi-homing at stub networks.
Resources: [BibTeX] [ External LINK ]

 

 Back

 New Search

top
© 2019 Laboratory TIK, ETH Zurich | Imprint | Last updated on Wed, 16 May, 2018 17:35 | t=0.003s | Valid HTML 4.01