Local Transit Policies and the Complexity of BGP Stability Testing
BGP, the core protocol of the Internet backbone, is renowned to be prone to oscillations. Despite prior work shed some light on BGP stability, many problems remain open. For example, determining how hard it is to check that a BGP network is safe, i.e., it is guaranteed to converge, has been an elusive research goal up to now. In this paper, the authors address several problems related to BGP stability, stating the computational complexity of testing if a given configuration is safe, is robust, or is safe under filtering. Further, they determine the computational complexity of checking popular sufficient conditions for stability.