Title: The Complexity of Restricted Variants of the Stable Paths Problem
Author: Kevin Donnelly, Assaf Kfoury, and Andrei Lapets
Data: March 15, 2010
Abstract:
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 f-SPP. We show that several natural variants of f-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 f-SPP.