From Theory to Practice: Efficiently Checking BGP Configurations for Guaranteed Convergence

Internet Service Providers can enforce a fine-grained control of Interdomain Routing by cleverly configuring the Border Gateway Protocol. However, the price to pay for the flexibility of BGP is the lack of convergence guarantees. The literature on network protocol design introduced several sufficient conditions that routing policies should satisfy to guarantee convergence. However, a methodology to systematically check BGP policies for convergence is still missing. This paper presents two fundamental contributions. First, we describe a heuristic algorithm that statically checks BGP configurations for guaranteed routing convergence. Our algorithm has several highly desirable properties: i) it exceeds state-of-the-art algorithms by correctly reporting more configurations as stable, ii) it can be implemented efficiently enough to analyze Internet-scale configurations, iii) it is free from false positives, namely never reports a potentially oscillating configuration as stable, and iv) it can help spot troublesome points in a detected oscillation. Second, we propose an architecture for a modular tool that exploits our algorithm to process native router configurations and report the presence of potential oscillations. Such a tool can effectively integrate syntactic checkers and assist operators in verifying configurations. We validate our approach using a prototype implementation and show that it scales well enough to enable Internet-scale convergence checks.