| 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. |
