Reducing the Complexity of BGP Stability Analysis With Hybrid Combinatorial-Algebraic Models
Routing stability and correctness in the Internet have long been a concern. Despite this, few theoretical frameworks have been proposed to check BGP configurations for convergence and safety. The most popular approach is based on the Stable Paths Problem (SPP) model. Unfortunately, SPP requires enumeration of all possible control-plane paths, which is infeasible in large networks. In this paper, the authors study how to apply algebraic frameworks to the BGP configuration checking problem. They propose an extension of the Stratified Shortest Path Problem (SSPP) model that has a similar expressive power to SPP, but enables more efficient checking of configuration correctness.