News

Colloquia

Incentive-Compatible Interdomain Routing

Vijay Ramachandran
Stevens Institute of Technology

Tuesday, February 27, 2007

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, ASes use semantically rich routing policies to choose interdomain routes in a distributed fashion. However, the interaction of these locally defined policies can lead to unexpected global anomalies. 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: Lowest-cost-path (LCP) routing can be implemented in a truthful, BGP-compatible manner, but several other natural classes of routing policies cannot. This work combines both approaches. In this talk, I will first review the concepts surrounding distributed algorithmic mechanism design and policy-based interdomain routing. I will discuss several positive results toward a general theory of incentive-compatible interdomain routing. I will then present a natural, realistic class of policies more expressive than LCP that does admit efficient and truthful implementation.

Hosted by: Chuck Stewart (x6731)
Administrative support: Jacky Carley (x8291)