Date Added: Apr 2011
Internet disruptions such as the Northeast Blackout and the Taiwan earthquake highlight the fragility of today's Internet. The authors' 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, they 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. Their main contribution is theoretical and concerns the complexity of the k-fault tolerance decision problem.