Incentive-Compatible Interdomain Routing
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 2006
- Accession Number
- ADA458992
Entities
People
- Joan Feigenbaum
- Michael Schapira
- Vijay Ramachandran
Organizations
- Yale University