Mechanism Design for Policy Routing
Title | Mechanism Design for Policy Routing |
Publication Type | Journal Article |
Year of Publication | 2006 |
Authors | Feigenbaum, J., Sami R., & Shenker S. J. |
Published in | Distributed Computing |
Volume | 18 |
Page(s) | 11-20 |
Other Numbers | 2232 |
Abstract | The Border Gateway Protocol (BGP) for interdomain routing is designed to allow autonomous systems (ASes) to express policy preferences over alternative routes. We model these preferences as arising from an ASs underlying utility for each route and study the problem of finding a set of routes that maximizes the overall welfare (ie, the sum of all ASes utilities for their selected routes).We show that, if the utility functions are unrestricted, this problem is NP-hard even to approximate closely. We then study a natural class of restricted utilities that we call next-hop preferences. We present a strategyproof, polynomial-time computable mechanism for welfare-maximizing routing over this restricted domain. However, we show that, in contrast to earlier work on lowest-cost routing mechanism design, this mechanism appears to be incompatible with BGP and hence difficult to implement in the context of the current Internet. Our contributions include a new complexity measure for Internet algorithms, dynamic stability, which may be useful in other problem domains. |
Acknowledgment | This work was supported in part through the Office of Naval Research grant N00014-01-1-0795 and through National Science Foundation grants ITR-0219018, ITR-0121555, and ANI-0207399. 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. |
URL | http://www.icsi.berkeley.edu/pubs/networking/mechanismdesign06.pdf |
Bibliographic Notes | Distributed Computing, Vol. 18, Issue. 4, pp. 150-164, special issue of selected papers from the 23rd ACM Symposium on Principles of Distributed Computing (PODC 2004). An earlier version of this paper appeared in the proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC 2004), St. John's, Canada, pp. 11-20 |
Abbreviated Authors | J. Feigenbaum, R. Sami, and S. Shenker |
ICSI Research Group | Networking and Security |
ICSI Publication Type | Article in journal or magazine |