A BGP-Based Mechanism for Lowest-Cost Routing
Title | A BGP-Based Mechanism for Lowest-Cost Routing |
Publication Type | Journal Article |
Year of Publication | 2005 |
Authors | Feigenbaum, J., Papadimitriou C. H., Sami R., & Shenker S. J. |
Published in | Distributed Computing |
Volume | 18 |
Issue | 1 |
Page(s) | 61-72 |
Other Numbers | 3484 |
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). 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. |
Acknowledgment | 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 |