An Approach to Seeking Policy Disputes Based on Dispute Cycle Avoidance and Configuration Guideline

The Border Gateway Protocol (BGP) is the de facto interdomain routing protocol used to exchange network reachability information between ASes in the global Internet. However, Varadhan et al. [19] has shown that the conflict of BGP routing policies can cause BGP to diverge. This paper presents an approach to seek the set of conflict routing policies based on dispute cycle avoidance. The stable paths problem, a static formalism that captures the semantics of interdomain routing protocol, provides the theoretical foundation for this approach. And this approach draws on the simple path vector protocol to identify the dispute cycles that cause routing oscillation first, and then queries which routing policies lead to these cycles in a distributed manner. Finally, it determines conflict routing policies based on dispute cycle avoidance. Moreover, we present a method to determine the severity level of dispute routing policies based on AS relationships and configuration guidelines of routing policy presented by Gao and Rexford [4]. And this method can help Network administrators determine the top-priority routing policies to be fixed and improve the efficiency of debugging routing policies. In addition, a simulation instance is given in order to explain results of this method.