A BGP-based mechanism for lowest-cost routing

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 [14] and Hershberger and Suri [10]. 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 source-destination pairs and payments for transit nodes on all of the routes (rather than computing routes and payments for only one source-destination pair at a time, as is done in [14, 10]); (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 [14, 10]). 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.

REFERENCES

• 1: Aaron Archer , Éva Tardos, Frugal path mechanisms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.991-999, January 06-08, 2002, San Francisco, California
• 2: E. Clarke. Multipart pricing of public goods. Public Choice11 (1971), pages 17-33.
• 3: J. Feigenbaum, A. Krishnamurthy, R. Sami, and S. Shenker. Approximation and Collusion in Multicast Cost Sharing, submitted. Available in preprint form at http://www.cs.yale.edu/homes/jf/FKSS1.ps.
• 4: J. Feigenbaum, A. Krishnamurthy, R. Sami, and S. Shenker. Hardness Results for Multicast Cost Sharing, submitted. Available in preprint form at http://www.cs.yale.edu/homes/jf/FKSS2.ps.
• 5: Joan Feigenbaum , Christos H. Papadimitriou , Scott Shenker, Sharing the cost of multicast transmissions, Journal of Computer and System Sciences, v.63 n.1, p.21-41, August 2001 [doi>10.1006/jcss.2001.1754]
• 6: Amos Fiat , Andrew V. Goldberg , Jason D. Hartline , Anna R. Karlin, Competitive generalized auctions, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509921]
• 7: J. Green and J. Laffont. Incentives in public decision making. In Studies in Public Economics. Volume 1, North Holland, Amsterdam, pages 65-78, 1979.
• 8: Timothy G. Griffin , Gordon Wilfong, An analysis of BGP convergence properties, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.277-288, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 9: T. Groves. Incentives in teams. Econometrica41 (1973), pages 617-663.
• 10: J. Hershberger , S. Suri, Vickrey Prices and Shortest Paths: What is an Edge Worth?, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.252, October 14-17, 2001
• 11: A. Mas-Colell, M. Whinston, and J. Green. Microeconomic Theory, Oxford University Press, New York, 1995.
• 12: J. Mitchell, R. Sami, K. Talwar, and V. Teague. Private communication, December 2001.
• 13: Dov Monderer , Moshe Tennenholtz, Distributed games: from mechanisms to protocols, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.32-37, July 18-22, 1999, Orlando, Florida, United States
• 14: N. Nisan and A. Ronen. Algorithmic mechanism design. Games and Economic Behavior35 (2001), pages 166-196.
• 15: David C. Parkes, iBundle: an efficient ascending price bundle auction, Proceedings of the 1st ACM conference on Electronic commerce, p.148-157, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337032]
• 16: David C. Parkes , Lyle H. Ungar, Iterative Combinatorial Auctions: Theory and Practice, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.74-81, July 30-August 03, 2000
• 17: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 18: Route Views. University of Oregon Route Views Project. http://www.routeviews.org
• 19: Tuomas W. Sandholm, Distributed rational decision making, Multiagent systems: a modern approach to distributed artificial intelligence, MIT Press, Cambridge, MA, 1999
• 20: H. Tangmunarunkit, R. Govindan, and S. Shenker. Internet path inflation due to policy routing. In Proceeding of SPIE ITCom 2001, SPIE Press, Bellingham, pages 19-24, 2001.
• 21: W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance16 (1961), pages 8-37.
• 22: M. Wellman. A market-oriented programming environment and its applications to distributed multicommodity flow problems. Journal of AI Research1 (1993), pages 1-23.
• 23: M. Wellman, W. Walsh, P. Wurman, and J. Mackie-Mason. Auctions for decentralized scheduling. Games and Economic Behavior35 (2001), pages 271-303.