Title: On the Stable Paths Problem and a Restricted Variant
Authors: Kevin Donnelly and Assaf Kfoury
Date: January 10, 2008
Abstract:
Interdomain routing on the Internet is performed using route
preference policies specified independently, and arbitrarily by each
Autonomous System in the network. These policies are used in the
border gateway protocol (BGP) by each AS when selecting next-hop
choices for routes to each destination. Con- flicts between policies
used by different ASs can lead to routing instabilities that,
potentially, cannot be resolved no matter how long BGP is run. The
Stable Paths Problem (SPP) is an abstract graph theoretic model of the
problem of selecting nexthop routes for a destination. A stable
solution to the problem is a set of next-hop choices, one for each AS,
that is compatible with the policies of each AS. In a stable solution
each AS has selected its best next-hop given that the next-hop choices
of all neighbors are fixed. BGP can be viewed as a distributed
algorithm for solving SPP. In this report we consider the stable
paths problem, as well as a family of restricted variants of the
stable paths problem, which we call F stable paths problems. We show
that two very simple variants of the stable paths problem are also
NP-complete. In addition we show that for networks with a DAG
topology, there is an efficient centralized algorithm to solve the
stable paths problem, and that BGP always efficiently converges to a
stable solution on such networks.