Abstract
The Border Gateway Protocol (BGP) is the
current inter-domain routing protocol used to exchange reachability
information between Autonomous Systems (ASes) in the Internet. BGP
supports policy-based routing which allows each AS to independently define
a set of local policies on which routes it accepts and advertises from/to
other networks, as well as on which route it prefers when more than one
route becomes available. However, independently chosen local policies may
cause global conflicts, which result in protocol divergence. In this
study, we propose a new algorithm, called Adaptive Policy Management Scheme
(APMS), to resolve policy conflicts in a distributed manner. Akin to
distributed feedback control systems, each AS independently classifies the
state of the network as either conflict-free or potentially conflicting by
observing its local history only (namely, route flaps). Based on the degree
of measured conflicts, each AS dynamically adjusts its own path
preferences---increasing its preference for observably stable paths over
flapping paths. APMS also includes a mechanism to distinguish route flaps
due to topology changes, so as not to confuse them with those due to policy
conflicts.
The detailed information as well as the correctness and convergence analysis
of APMS based on the sub-stability property of chosen paths can be found in
An Adaptive Management Approach to Resolving Policy Conflicts [PS][PDF].
Selma Yilmaz and Ibrahim Matta.
To appear in Networking 2007, Atlanta, Georgia, May 2007.
The longer version of this paper appears as Technical Report BU-TR 2006-008,
May 2006 [PS][PDF].