Mechanism Design for Policy Routing

TitleMechanism Design for Policy Routing
Publication TypeJournal Article
Year of Publication2006
AuthorsFeigenbaum, J., Sami R., & Shenker S.
Published inDistributed Computing
Other Numbers2232

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 AS’s 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.


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.

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