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.
|