A Safe Path Vector Protocol

Most IP routing protocols are safe in the sense that they are guaranteed to converge in the absence of changes in network topology, and to reconverge after topology changes. One exception to this is BGP, currently the only interdomain routing protocol employed on the Internet. The source of BGP's potential divergence is that policy-based metrics can override distance-based metrics, and that policies are defined independently by each autonomous system with little or no global coordination. In this paper, we present a BGP-like protocol, called SPVP, and prove that it is safe. The protocol is independent of the language used to specify routing policies, and it does not assume that such policies are consistent. The safety of SPVP is achieved by adding a dynamically computed attribute to routing messages, called the route history. Protocol oscillations caused by policy conflicts give rise to histories containing cycles that identify these conflicts and the autonomous systems involved. We discuss how SPVP can be used in the design of an extension to BGP to make that product safe.