Incentive-Compatible Interdomain Routing
YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
The routing of traffic between Internet domains, or Autonomous Systems ASes, a task known as interdomain routing, is currently handled by the Border Gateway Protocol BGP. Using BGP, autonomous systems can apply semantically rich routing policies to choose interdomain routes in a distributed fashion. This expressiveness in routing-policy choice supports domains autonomy in network operations and in business decisions, but it comes at a price The interaction of locally defined routing policies can lead to unexpected global anomalies, including route oscillations or overall protocol divergence. Networking researchers have addressed this problem by devising constraints on policies that guarantee BGP convergence without unduly limiting expressiveness and autonomy. In addition to taking this engineering or protocol-design approach, researchers have approached interdomain routing from an economic or mechanism-design point of view. It is known that lowest-cost-path LCP routing can be implemented in a truthful, BGP-compatible manner but that several other natural classes of routing policies cannot. In this paper, we present a natural class of interdomain-routing policies that is more realistic than LCP routing and admits incentive-compatible, BGP-compatible implementation. We also present several positive steps toward a general theory of incentive-compatible interdomain routing.
- Computer Systems
- Computer Systems Management and Standards