The Complexity of Restricted Variants of the Stable Paths Problem

Interdomain routing on the Internet is performed using route preference policies specified independently and arbitrarily by each autonomous system (AS) 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. Conflicts between policies used by different ASs can lead to routing instabilities that, potentially, cannot be resolved regardless of how long BGP runs. The stable paths problem (SPP) is an abstract graph theoretic model of the problem of selecting next-hop routes for a destination. A solution to this 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 if the next-hop choices of all neighbors are fixed. BGP can be viewed as a distributed algorithm for solving an SPP instance. In this report we consider a family of restricted variants of SPP, which we call 푓-SPP. We show that several natural variants of 푓-SPP are NP-complete. This includes a variant in which each AS is restricted to one of only two policies, and each of these two policies is based on a monotonic path weight aggregation function. Furthermore, we show that for networks with particular topologies and edge weight distributions, there exist efficient centralized algorithms for solving 푓-SPP.