A Randomized Solution to BGP Divergence

S. Yilmaz and I. Matta (USA)


Inter-domain Routing; Border Gateway Protocol (BGP); Convergence Analysis.


The Border Gateway Protocol (BGP) is an interdomain routing protocol that allows each Autonomous System (AS) to define its own routing policies independently and use them to select the best routes. By means of policies, ASes are able to prevent some traffic from accessing their resources, or direct their traffic to a preferred route. How ever, this flexibility comes at the expense of a possibility of divergence behavior because of mutually conflicting poli cies. Since BGP is not guaranteed to converge even in the absence of network topology changes, it is not safe. In this paper, we propose a randomized approach to providing safety in BGP. The proposed algorithm dynamically detects policy conflicts, and tries to eliminate the conflict by chang ing the local preference of the paths involved. Both the detection and elimination of policy conflicts are performed locally, i.e. by using only local information. Randomiza tion is introduced to prevent synchronous updates of the local preferences of the paths involved in the same conflict.

Important Links:

Go Back