The NP-completeness of the Restricted Stable Paths Problem with Three Aggregating Functions
Date
2010-03-14
DOI
Authors
Lapets, Andrei
Kfoury, Assaf
Version
OA Version
Citation
Lapets, Andrei; Kfoury, Assaf. "The NP-completeness of the Restricted Stable Paths Problem with Three Aggregating Functions", Technical Report BUCS-TR-2010-004, Computer Science Department, Boston University, March 14, 2010. [Available from: http://hdl.handle.net/2144/3783]
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 finding a stable solution to an SPP instance. In this report we consider a particular restricted variant of SPP, which we call (f,g,h)-SPP, in which there exist three or more different node policies based on aggregation of edge weights. We show that this variant is NP-complete.