Abstract:

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 dlstance-based metrics with policybased metrics when choosing the best routes. Varadhan has shown that it is poss  ible for a group of autonomous systems to independently define BGP policies that together lead to BGP protocol oscillations that never converge on a sta ble 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.

Key words: border gateway protocol, route oscillation, secure multi-party computatiom stable path proble m, routing policy