The Strategic Justification for BGP

Levin, Hagay and Schapira, Michael and Zohar, Aviv (2006): The Strategic Justification for BGP.

Abstract

The Internet consists of many administrative domains, or \emph{Autonomous Systems} (ASes), each owned by an economic entity (Microsoft, AT\&T, The Hebrew University, etc.). The task of ensuring interconnectivity between ASes, known as \emph{interdomain routing}, is currently handled by the \emph{Border Gateway Protocol} (BGP).

ASes are self-interested and might be willing to manipulate BGP for their benefit. In this paper we present the strategic justification for using BGP for interdomain routing in today's Internet: We show that, in the realistic Gao-Rexford setting, BGP is immune to almost all forms of rational manipulation by ASes, and can easily be made immune to all such manipulations. The Gao-Rexford setting is said to accurately depict the current commercial relations between ASes in the Internet. Formally, we prove that a slight modification of BGP is incentive-compatible in \emph{ex-post Nash equilibrium}. Moreover, we show that, if a certain reasonable condition holds, then this slightly modified BGP is also \emph{collusion-proof} in ex-post Nash -- i.e., immune to rational manipulations even by \emph{coalitions} of \emph{any} size.

Unlike previous works on achieving incentive-compatibility in interdomain routing, our results \emph{do not require any monetary transfer between ASes} (as is the case in practice). We also strengthen the Gao-Rexford constraints by proving that one of the three constraints can actually be enforced by the rationality of ASes if the two other constraints hold.

• Item Type: MPRA Paper
• Institution: The Hebrew University of Jerusalem
• Language: English
• Keywords: Networks; Ex post Nash; Routing; rational manipulation; Border Gateway Protocol; Dispute Wheel
• Subjects: D - Microeconomics > D8 - Information, Knowledge, and Uncertainty; D - Microeconomics > D7 - Analysis of Collective Decision-Making; D - Microeconomics > D8 - Information, Knowledge, and Uncertainty > D85 - Network Formation and Analysis: Theory

References

References [1] A.L. Barabasi and R. Albert. Emergence of Scaling in Random Networks. Science, October 1999. [2] Alex Fabrikant, Ankur Luthra, Elitza Maneva, Christos H. Papadimitriou, and Scott Shenker. On a network creation game. In Proceedings of PODC 2003, 2003. [3] Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. On power-law relationships of the inter- net topology. In SIGCOMM 1999: Proceedings of the 1999 conference on Applications, technologies, architectures, and protocols for computer communications. ACM Press, 1999. [4] 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. [5] 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. [6] 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. [7] Joan Feigenbaum, Vijay Ramachandran, and Michael Schapira. Incentive-compatible interdomain rout- ing. In 7th Conference on Electronic Commerce, pages 130{139, New York, 2006. ACM. [8] Joan Feigenbaum, Rahul Sami, and Scott Shenker. Mechanism design for policy routing. Distributed Computing, 18(4):293{305, 2006. [9] Joan Feigenbaum, Michael Schapira, and Scott Shenker. Distributed Algorithmic Mechanism Design: A chapter in the upcoming book \Algorithmic Game Theory". Cambridge University Press. [10] 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 Com- puting and Communications, pages 1{13, New York, 2002. ACM. [11] Lixin Gao, Timothy G. Gri±n, and Jennifer Rexford. Inherently safe backup routing with BGP. In 20th INFOCOM, pages 547{556, Pistacaway, 2001. IEEE. [12] Lixin Gao and Jennifer Rexford. Stable Internet routing without global coordination. IEEE/ACM Transactions on Networking, 9(6):681{692, 2001. [13] 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. [14] 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. [15] Timothy G. Gri±n and Gordon Wilfong. A safe path vector protocol. In Proceedings of IEEE INFOCOM 2000. IEEE Communications Society, IEEE Press, March 2000. [16] Geo® Huston. Interconnection, peering, and settlements. In Internet Global Summit (INET). The Internet Society, 1999. [17] Aaron D. Jaggard and Vijay Ramachandran. Robustness of class-based path-vector systems. In Pro- ceedings of ICNP'04, pages 84{93. IEEE Computer Society, IEEE Press, October 2004. [18] Ahuva Mu'alem and Michael Schapira. Setting lower bounds on truthfulness. In To appear in SODA 2007. [19] Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35(1):166{196, 2001. [20] 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. [21] Jo~ao L. Sobrinho. An algebraic theory of dynamic network routing. IEEE/ACM Transactions on Networking, 13(5):1160{1173, 2005. [22] Alan D. Taylor. The manipulability of voting systems. The American Mathematical Monthly, April 2002. [23] Kannan Varadhan, Ramesh Govindan, and Deborah Estrin. Persistent route oscillations in inter-domain routing. Computer Networks, 32(1):1{16, March 2000.