Show simple item record

dc.contributor.authorLapets, Andreien_US
dc.contributor.authorKfoury, Assafen_US
dc.date.accessioned2012-05-21T18:59:34Z
dc.date.available2012-05-21T18:59:34Z
dc.date.issued2010-03-14
dc.identifier.citationLapets, 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]
dc.identifier.urihttps://hdl.handle.net/2144/3783
dc.description.abstractInterdomain 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.en_US
dc.language.isoen_US
dc.publisherCS Department, Boston Universityen_US
dc.relation.ispartofseriesBUCS Technical Reports;BUCS-TR-2010-004
dc.titleThe NP-completeness of the Restricted Stable Paths Problem with Three Aggregating Functionsen_US
dc.typeTechnical Reporten_US


This item appears in the following Collection(s)

Show simple item record