A safe path vector protocol

Abstract

An IP routing protocol is safe if it is guaranteed to converge in the absence of network topology changes. BGP, currently the only interdomain routing protocol employed on the Internet, is not safe in this sense. It may seem that the source of BGP's potential divergence is inherent in the requirements for any interdomain routing protocol-policy-based metrics must be allowed to override distance-based metrics, and each autonomous system must be allowed to independently define its routing policies with little or no global coordination. In this paper we present a simple path vector protocol (SPVP) that captures the underlying semantics of BGP by abstracting away all nonessential details. We then add a dynamically computed attribute to SPVP routing messages, called the route history. Protocol oscillations caused by policy conflicts produce routes whose histories contain cycles. These cycles identify the policy conflicts and the autonomous systems involved. SPVP is made safe by automatically suppressing routes whose histories contain cycles. We discuss how this safe SPVP can be used in the design of a safe BGP.