A BGP-Based Mechanism for Lowest-Cost Routing

TitleA BGP-Based Mechanism for Lowest-Cost Routing
Publication TypeJournal Article
Year of Publication2005
AuthorsFeigenbaum, J., Papadimitriou C. H., Sami R., & Shenker S.
Published inDistributed Computing
Other Numbers3484

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). In this paper, we address the problem of interdomain routing from a mechanism-design point of view. The application of mechanism-design principles to the study of routing is the subject of earlier work by Nisan and Ronen [16] and Hershberger and Suri [12]. 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 sourcedestination pairs and payments for transit nodes on all of the routes (rather than computing routes and payments for only one sourcedestination pair at a time, as is done in [12,16]); (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 used in [12,16]). This approach of using an existing protocol as a substrate for distributed computation may prove useful in 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, which has heretofore been focused mainly on multicast cost sharing.


This work was supported in part through Office of Naval Research grants N00014-01-1-0795 and N00014-01-1-0447, through National Science Foundation grants CCR-0105337, ITR-0081698, ITR-0121555, ITR-0205519, ANI-0207399 ITR-0225660, and ANI-0196514, and by an IBM Faculty Development Award. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors or originators and do not necessarily reflect the views of the funders.

Bibliographic Notes

Distributed Computing, Vol. 18, Issue 1, pp. 61-72, special issue of selected papers from the 21st ACM Symposium on Principles of Distributed Computing (PODC 2002). An earlier version of this paper appeared in the proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC 2002), Monterey, California, pp. 173-182.

Abbreviated Authors

J. Feigenbaum, C.H. Papadimitriou, R. Sami, and S. Shenker

ICSI Research Group

Networking and Security

ICSI Publication Type

Article in journal or magazine