Eliminating BGP oscillations caused by policy conflicts

The border gateway protocol (BGP) is currently the only inter-domain routing protocol employed on the Internet. It allows each autonomous system to independently define its own routing policies for selecting routes and propagating the routes to its neighbor autonomous systems. However, the collections of routing policies of autonomous systems can conflict in a manner that causes BGP to divergence. In this paper, we propose an approach to dynamically detect policy conflicts and eliminate permanent BGP route oscillations caused by the policy conflicts. The proposed algorithm detects policy conflicts using the relative preference value of selected route compared to the previous selected route. In order to prevent BGP oscillations, a data structure called the local route history is introduced to store routes involving oscillations. The proposed algorithm prevents BGP oscillations by suppressing routes reappear in the local route history.