Mechanism Design for Policy Routing
Abstract
The Border Gateway Protocol (BGP) for interdomain routing is designed to allow autonomous systems (ASes) to express policy preferences over alternative routes. We model these preferences as arising from an AS's underlying utility for each route and study the problem of finding a set of routes that maximizes the overall welfare (i.e., the sum of all ASes' utilities for their selected routes). We show that, if the utility functions are unrestricted, this problem is NP-hard even to approximate closely. We then study a natural class of restricted utilities, next-hop preferences. We present a strategyproof, polynomial-time computable mechanism for welfare-maximizing routing over this restricted work on lowest-cost routing mechanism design, this mechanism appears to be incompatible with BGP and hence difficult to implement in the context of the current internet. Our contributions include a new complexity measure for Internet algorithms, the dynamic stability, which may be useful in other problem domains.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 2003
- Accession Number
- ADA479188
Entities
People
- Joan Feigenbaum
- Rahul Sami
- Scott Shenker
Organizations
- Yale University