Dynamic routing protocols such as RIP and OSPF essentially implement distributed algorithms for solving the Shortest Paths Problem. Can BGP be viewed as a distributed algorithm for solving some underlying problem? Contrary to popular belief BGP is not, in general, solving a shortest paths problem, since it allows policy-based metrics to override distance-based metrics, and enables autonomous systems to independently define their routing policies with little or no global coordination.

I'll describe the "Stable Paths Problem" and argue that at some level, BGP is a distributed algorithm for solving this problem. The fact that BGP can actually fail to converge to a stable routing, as first observed by Varadhan et al., arises when the corresponding Stable Paths Problem has no solution. I'll give some examples of conflicting BGP policies that lead to BGP divergence, which would result in persistent route oscillations. The likelihood of such scenarios arising in practice is not known.

About the Presenter
Tim Griffin is a member of the technical staff at Bell Labs/Lucent Technologies. He is working with F. Bruce Shepherd and Gordon Wilfong, both of Bell Labs, on algorithms for the analysis of BGP routing policies for use in policy-based network management applications.