Mechanism Design for Policy Routing

TitleMechanism Design for Policy Routing
Publication TypeConference Paper
Year of Publication2004
AuthorsFeigenbaum, J., Sami R., & Shenker S. J.
Published inProceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC 2004)
Other Numbers1717

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 (i.e., 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, the dynamic stability, which may be useful in other problem domains.


This work was partially supported by funding provided to ICSI and its researchers through National Science Foundation grants CCF: 0121555 ("Discrete Models and Algorithms in the Sciences"); CNS: 0207399 ("Incentive-Compatible Designs for Distributed Systems"); and CNS: 0205519 ("Addressing Fundamental Issues for Robust Internet Performance"). 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 National Science Foundation.

Bibliographic Notes

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 conference proceedings