A BGP-based Mechanism for Lowest-Cost Routing

A BGP-based Mechanism for Lowest-Cost Routing

(Research Seminar, September 12th, 2002)

Joan Feigenbaum
Yale University

Abstract:

The routing of traffic between Internet domains or "Autonomous Systems" (ASs), a task known as "interdomain routing," is currently handled by the Border Gateway Protocol (BGP). There has been a substantial amount of research on routing in general and on BGP in particular, but until recently all of it took an engineering (or "protocol-design") approach. Recently, Nisan and Ronen (1999) and Hershberger and Suri (2001) have taken an economic (or "mechanism-design") approach to the problem, and that line of research is continued here.

In this paper, we formulate and solve a version of the routing-mechanism design problem that is different from the previously studied version in three ways that make it more accurately reflective of real-world interdomain routing:

(1) we treat the nodes as strategic agents, rather than the links;
(2) our mechanism computes lowest-cost routes for all source-destination pairs and payments for transit nodes on all of the routes, rather than computing routes and payments for only one
source-destination pair at a time;
(3) we show how to compute our mechanism with a *distributed* algorithm that is a straightforward extension to BGP and causes only modest increases in routing-table size and convergence time (in contrast with the centralized algorithms studied by Nisan and Ronen and by Hershberger and Suri).

Our approach of using an existing protocol as a substrate for distributed computation may prove useful for future development of Internet algorithms generally, not only for routing or pricing problems. Our design and
analysis of a strategyproof, BGP-based routing mechanism provides a new, promising direction in "distributed algorithmic mechanism design" (DAMD), which has heretofore been focused mainly on multicast cost sharing.

This is joint work with Christos Papadimitriou, Rahul Sami, and Scott Shenker; it appears in the Proceedings of the 2002 ACM Symposium on Principles of Distributed Computing.

This work was supported by the DoD University Research Initiative (URI) program administered by the Office of Naval Research under Grant N00014-01-1-0795.