Thursday, October 20, 2005
4:15 pm
B17 Upson Hall

Computer Science
Colloquium
Fall 2005


Joan Feigenbaum
Yale University

Incentive-Compatible Interdomain Routing


The Internet is divided into many Autonomous Systems (ASes). Loosely speaking, each AS is a subnetwork that is administered by a single organization. The task of routing between different ASes in the Internet is called "interdomain routing." Currently, the only widely used protocol for interdomain routing is the Border Gateway Protocol (BGP). BGP allows an AS to "advertise" routes it currently uses to neighboring ASes. An AS i with many neighbors may thus receive advertisements of many different routes to a given destination j. It must then select one of these available routes as the route it will use to send its traffic; subsequently, i can advertise this chosen route (prefixed by i itself) to all its neighbors. Proceeding in this manner, every AS in the Internet can eventually discover at least one route to destination j.

In this talk, I will address one of the fundamental problems in interdomain routing, namely incentive compatibility. How can one build into an interdomain-routing scheme incentives for ASes, which are economically and administratively independent entities, to share with each other the potentially sensitive information that could be useful in choosing a set of routes that is best for the network as a whole? I will show that a natural, flexible class of routing policies, first formalized by Gao and Rexford, leads to a routing-tree-optimization problem that is both incentive-compatible and BGP-compatible. Previously studied special cases of these policies include lowest-cost routing and next-hop routing.