1999 · 372 citations · 8 references
ComputingAutonomous SystemsComputer ScienceComputer NetworksNetwork SecuritySecurity ProtocolsInternet RoutingNetwork ProtocolsProtocol AnalysisRoutingRouting AlgorithmsRouting ProtocolsBorder Gateway ProtocolDistance MetricsInter-domain RoutingInterdomain RoutingPath-vector RoutingPolicy-based RoutingRouting PoliciesWorst-case Complexity
The Border Gateway Protocol (BGP) is the de facto inter-domain routing protocol used to exchange reachability information between Autonomous Systems in the global Internet. BGP is a path-vector protocol that allows each Autonomous System to override distance-based metrics with policy-based metrics when choosing best routes. Varadhan et al. [18] have shown that it is possible for a group of Autonomous Systems to independently define BGP policies that together lead to BGP protocol oscillations that never converge on a stable routing. One approach to addressing this problem is based on static analysis of routing policies to determine if they are safe. We explore the worst-case complexity for convergence-oriented static analysis of BGP routing policies. We present an abstract model of BGP and use it to define several global sanity conditions on routing policies that are related to BGP convergence/divergence. For each condition we show that the complexity of statically checking it is either NP-complete or NP-hard.
8
The NP-completeness column: An ongoing guide
David S. Johnson · Journal of Algorithms · 1986 · 803 citations
End-to-end routing behavior in the Internet
Vern Paxson · IEEE/ACM Transactions on Networking · 1997 · 699 citations
Craig Labovitz, G. Robert Malan, Farnam Jahanian · 1997 · 363 citations