Interdomain routing and games

Levin, Hagay and Schapira, Michael and Zohar, Aviv (2008): Interdomain routing and games.

Abstract

We present a game-theoretic model that captures many of the intricacies of \emph{interdomain routing} in today's Internet. In this model, the strategic agents are source nodes located on a network, who aim to send traffic to a unique destination node. The interaction between the agents is dynamic and complex -- asynchronous, sequential, and based on partial information. Best-reply dynamics in this model capture crucial aspects of the only interdomain routing protocol de facto, namely the Border Gateway Protocol (BGP).

We study complexity and incentive-related issues in this model. Our main results are showing that in realistic and well-studied settings, BGP is incentive-compatible. I.e., not only does myopic behaviour of all players \emph{converge} to a ``stable'' routing outcome, but no player has motivation to unilaterally deviate from the protocol. Moreover, we show that even \emph{coalitions} of players of \emph{any} size cannot improve their routing outcomes by collaborating. Unlike the vast majority of works in mechanism design, our results do not require any monetary transfers (to or by the agents).

• Item Type: MPRA Paper
• Language: English
• Keywords: Interdomain Routing; Network Games; BGP protocol
• Subjects: D - Microeconomics > D7 - Analysis of Collective Decision-Making; D - Microeconomics > D8 - Information, Knowledge, and Uncertainty; D - Microeconomics > D8 - Information, Knowledge, and Uncertainty > D85 - Network Formation and Analysis: Theory

References

[1] N. Alon, Y. Matias, and M. Szegedy. Jounal of computer and system sciences. The space complexity of approximating the frequency moment, (58(1)):137{137, 1999.

[2] Kevin Butler, Toni Farley, Patrick Mcdaniel, and J. Rexford. A survey of BGP security issues and solutions. Technical report, AT&T Labs - Research, Florham Park, NJ, February 2004.

[3] Ronny R. Dakdouk, Semih Salihoglu, Hao Wang, Haiyong Xie, and Yang Richard Yang. Inter- domain routing as social choice. In Proceedings of Incentive-Based Computing (IBC), Lisboa, Portugal, July 2006.

[4] Alex Fabrikant and Christos Papadimitriou. The complexity of game dynamics: BGP oscilla- tions, sink equlibria, and beyond. In Proceedings of SODA 2008.

[5] Nick Feamster, Ramesh Johari, and Hari Balakrishnan. Implications of autonomy for the expressiveness of policy routing. In SIGCOMM '05: Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, New York, NY, USA, 2005. ACM Press.

[6] Joan Feigenbaum, David R. Karger, Vahab S. Mirrokni, and Rahul Sami. Subjective-cost policy routing. In Xiaotie Deng and Yinyu Ye, editors, First Workshop on Internet and Network Economics, volume 3828 of Lecture Notes in Computer Science, pages 174{183, Berlin, 2005. Springer.

[7] Joan Feigenbaum, Christos H. Papadimitriou, Rahul Sami, and Scott Shenker. A BGP-based mechanism for lowest-cost routing. Distributed Computing, 18(1):61{72, 2005.

[8] Joan Feigenbaum, Christos H. Papadimitriou, and Scott Shenker. Sharing the cost of multicast transmissions. Journal of Computer System Sciences, 63(1):21{41, 2001.

[9] Joan Feigenbaum, Vijay Ramachandran, and Michael Schapira. Incentive-compatible interdo- main routing. In 7th Conference on Electronic Commerce, pages 130{139, New York, 2006. ACM. 14

[10] Joan Feigenbaum, Rahul Sami, and Scott Shenker. Mechanism design for policy routing. Distributed Computing, 18(4):293{305, 2006.

[11] Joan Feigenbaum, Michael Schapira, and Scott Shenker. Distributed Algorithmic Mechanism Design: A chapter in the upcoming book \Algorithmic Game Theory". Cambridge University Press.

[12] Joan Feigenbaum and Scott Shenker. Distributed algorithmic mechanism design: recent results and future directions. In 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pages 1{13, New York, 2002. ACM.

[13] Lixin Gao, Timothy G. Gri±n, and Jennifer Rexford. Inherently safe backup routing with BGP. In 20th INFOCOM, pages 547{556, Pistacaway, 2001. IEEE.

[14] Lixin Gao and Jennifer Rexford. Stable Internet routing without global coordination. IEEE/ACM Transactions on Networking, 9(6):681{692, 2001.

[15] Timothy G. Gri±n, Aaron D. Jaggard, and Vijay Ramachandran. Design principles of policy languages for path vector protocols. In SIGCOMM '03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, pages 61{72, New York, 2003. ACM.

[16] Timothy G. Gri±n, F. Bruce Shepherd, and Gordon Wilfong. Policy disputes in path-vector protocols. In 7th International Conference on Network Protocols, pages 21{30, Los Alamitos, 1999. IEEE Computer Society.

[17] Timothy G. Gri±n and Gordon Wilfong. An analysis of BGP convergence properties. In Proceedings of SIGCOMM 1999.

[18] Alex Hall, Evdokia Nikolova, and Christos Papadimitriou. Incentive-compatible interdomain routing with linear utilities. In Proceedings of WINE 2007.

[19] Sergiu Hart and Yishay Mansour. The communication complexity of uncoupled nash equilib- rium procedures. In Proceedings of STOC 2007.

[20] Johan Hastad. Some optimal inapproximability results. Journal of the ACM, (48):798{859, 201.

[21] Geo® Huston. Interconnection, peering, and settlements. In Internet Global Summit (INET). The Internet Society, 1999.

[22] Hagay Levin, Michael Schapira, and Aviv Zohar. The strategic justi¯cation for BGP. A technical report, Leibniz Institute, The Hebrew University of Jerusalem.

[23] Ahuva Mu'alem and Michael Schapira. Setting lower bounds on truthfulness. In SODA 2007.

[24] Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35(1):166{196, 2001.

[25] David C. Parkes and Je®rey Shneidman. Speci¯cation faithfulness in networks with rational nodes. In 23rd Symposium on Principles of Distributed Computing, pages 88{97, New York.

[26] Jo~ao L. Sobrinho. An algebraic theory of dynamic network routing. IEEE/ACM Transactions on Networking, 13(5):1160{1173, 2005. 15

[27] Kannan Varadhan, Ramesh Govindan, and Deborah Estrin. Persistent route oscillations in inter-domain routing. Computer Networks, 32(1):1{16, March 2000.