An Approach to Seeking BGP Policy Confliction Based on Secure Multi-Party Computation
Xicheng Lu · Computer Engineering and Science · 2006
The Border Gateway Protocol, BGP, is currently the only inter-domain routing protocol employed on the Internet. BGP is a path-vector protocol that allows each autonomous system to override distance-based metrics with policy-based metrics when choosing the best routes. Varadhan has 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. Based on analyzing BGP with the Stable Path Problem (SPP) model, Griffin proposed an efficient algorithm that can find policy conflicts. But this algorithm faces several impediments. In this paper we present a new method which inherits Griffin's merits and eliminates his impediments at the same time. With secure multi-party computation, our algorithm can work well and has a significant practical value.