Paper Info
Title
Subjective-cost policy routing
Abstract
We study a model of interdomain routing in which autonomous systems’ (ASes’) routing policies are based on subjective cost assessments of alternative routes. The routes are constrained by the requirement that all routes to a given destination must be confluent. We show that it is NP-hard to determine whether there is a set of stable routes. We also show that it is NP-hard to find a set of confluent routes that minimizes the total subjective cost; it is hard even to approximate minimum cost closely. These hardness results hold even for very restricted classes of subjective costs. We then consider a model in which the subjective costs are based on the relative importance ASes place on a small number of objective cost measures. We show that a small number of confluent routing trees is sufficient for each AS to have a route that nearly minimizes its subjective cost. We show that this scheme is trivially strategyproof and that it can be computed easily with a distributed algorithm that does not require major changes to the Border Gateway Protocol. Furthermore, we prove a lower bound on the number of trees required to contain a (1 + ε)-approximately optimal route for each node and show that our scheme is nearly optimal in this respect.
Year
DOI
Venue
2007
10.1016/j.tcs.2007.02.020
Theor. Comput. Sci.
Keywords
DocType
Volume
objective cost measure,path-vector routing,confluent route,subjective cost,confluent routing tree,algorithmic mechanism design,policy routing,minimum cost,subjective-cost policy routing,alternative route,small number,total subjective cost,subjective cost assessment,distributed algorithm,mechanism design,lower bound
Journal
378
Issue
ISSN
ISBN
2
Theoretical Computer Science
3-540-30900-4
Citations 
PageRank 
References 
10
0.88
11
Authors
4
Name
Order
Citations
PageRank
Joan Feigenbaum14714711.33
David R. Karger2193672233.64
VAHAB S. MIRROKNI34309287.14
Rahul Sami454154.42