An Adaptive Policy Management Approach to BGP Convergence - 02/10/2006

Ibrahim Matta

The Border Gateway Protocol (BGP) is used in the Internet by Autonomous Systems (ASes) to exchange routing information. BGP allows each AS to independently apply its own set of policies specifying which routes the AS accepts and advertises from/to other ASes, and which route the AS prefers when more than one route becomes available. This flexibility of independently chosen local policies comes at a price---global conflicts may arise, which result in BGP not converging.

In this talk, I present a new algorithm, we call Adaptive Policy Management (APM), 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. APM also includes a mechanism to distinguish route flaps due to topology changes, so they are not confused with route flaps due to policy conflicts. I present a correctness and convergence analysis of APM based on the sub-stability property of chosen paths. I also present simulation results evaluating APM against other competing solutions in terms of instantaneous measures (throughput, delay, routing load, etc.)

Joint work with Selma Yilmaz.