Rationality and traffic attraction: incentives for honest path announcements in bgp

ABSTRACT

We study situations in which autonomous systems (ASes) may have incentives to send BGP announcements differing from the AS-level paths that packets traverse in the data plane. Prior work on this issue assumed that ASes seek only to obtain the best possible outgoing path for their traffic. In reality, other factors can influence a rational AS's behavior. Here we consider a more natural model, in which an AS is also interested in attracting incoming traffic (e.g., because other ASes pay it to carry their traffic). We ask what combinations of BGP enhancements and restrictions on routing policies can ensure that ASes have no incentive to lie about their data-plane paths. We find that protocols like S-BGP alone are insufficient, but that S-BGP does suffice if coupled with additional (quite unrealistic) restrictions on routing policies. Our game-theoretic analysis illustrates the high cost of ensuring that the ASes honestly announce data-plane paths in their BGP path announcements.

REFERENCES

• 1: K. Argyraki, P. Maniatis, O. Irzak, A. Subramanian, and S. Shenker. Loss and Delay Accountability for the Internet. In Proc. IEEE ICNP, pp. 194--205, Oct. 2007.
• 2: Ioannis Avramopoulos , Jennifer Rexford, Stealth probing: efficient data-plane security for IP routing, Proceedings of the annual conference on USENIX '06 Annual Technical Conference, p.25-25, May 30-June 03, 2006, Boston, MA
• 3: Hitesh Ballani , Paul Francis , Xinyang Zhang, A study of prefix hijacking and interception in the internet, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 4: Simon Balon , Guy Leduc, Can Forwarding Loops Appear When Activating iBGP Multipath Load Sharing?, Proceedings of the 3rd Asian conference on Internet Engineering: Sustainable Internet, November 27-29, 2007, Phuket, Thailand [doi>10.1007/978-3-540-76809-8_19]
• 5: K. Butler, T. Farley, P. McDaniel, and J. Rexford. A Survey of BGP Security Issues and Solutions. Technical report, AT&T Labs-Research, 2005.
• 6: Ronny R. Dakdouk , Semih Salihoglu , Hao Wang , Haiyong Xie , Yang Richard Yang, Interdomain Routing as Social Choice, Proceedings of the 26th IEEE International ConferenceWorkshops on Distributed Computing Systems, p.38, July 04-07, 2006 [doi>10.1109/ICDCSW.2006.65]
• 7: Nick Feamster , Ramesh Johari , Hari Balakrishnan, Implications of autonomy for the expressiveness of policy routing, IEEE/ACM Transactions on Networking (TON), v.15 n.6, p.1266-1279, December 2007 [doi>10.1109/TNET.2007.896531]
• 8: Joan Feigenbaum , David R. Karger , Vahab S. Mirrokni , Rahul Sami, Subjective-cost policy routing, Theoretical Computer Science, v.378 n.2, p.175-189, June, 2007 [doi>10.1016/j.tcs.2007.02.020]
• 9: Joan Feigenbaum , Christos Papadimitriou , Rahul Sami , Scott Shenker, A BGP-based mechanism for lowest-cost routing, Distributed Computing, v.18 n.1, p.61-72, July 2005 [doi>10.1007/s00446-005-0122-y]
• 10: Joan Feigenbaum , Vijay Ramachandran , Michael Schapira, Incentive-compatible interdomain routing, Proceedings of the 7th ACM conference on Electronic commerce, p.130-139, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134722]
• 11: Joan Feigenbaum , Rahul Sami , Scott Shenker, Mechanism design for policy routing, Distributed Computing, v.18 n.4, p.293-305, March 2006 [doi>10.1007/s00446-005-0134-7]
• 12: J. Feigenbaum, M. Schapira, and S. Shenker. Distributed Algorithmic Mechanism Design. Chap. 14 (pp. 363--384) in Algorithmic Game Theory, N. Nisan, T. Roughgarden, É. Tardos, and V. Vazirani, eds. Cambridge UP, Sep. 2007.
• 13: L. Gao, T. G. Griffin, and J. Rexford. Inherently Safe Backup Routing with BGP. In Proc. IEEE INFOCOM, vol. 1, pp. 22--26, Apr. 2001.
• 14: Lixin Gao , Jennifer Rexford, Stable internet routing without global coordination, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.681-692, December 2001 [doi>10.1109/90.974523]
• 15: R. Gao, C. Dovrolis, and E. Zegura. Interdomain Ingress Traffic Engineering through Optimized AS-Path Prepending. In Proc. IFIP Networking, May 2005.
• 16: V. Gill , J. Heasley , D. Meyer, The Generalized TTL Security Mechanism (GTSM), RFC Editor, 2004
• 17: S. Goldberg and S. Halevi. Rational ASes and Traffic Attraction: Incentives for Honestly Announcing Paths in BGP. Technical Report TR-813-08, Princeton Univ. Dept. of Comp. Sci., Feb. 2008.
• 18: S. Goldberg, S. Halevi, A. D. Jaggard, V. Ramachandran, and R. N. Wright. Rationality and Traffic Attraction: Incentives for Honest Path Announcements in BGP. Technical Report TR-823-08, Princeton Univ. Dept. of Comp. Sci., Jun. 2008.
• 19: Sharon Goldberg , David Xiao , Eran Tromer , Boaz Barak , Jennifer Rexford, Path-quality monitoring in the presence of adversaries, Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 02-06, 2008, Annapolis, MD, USA
• 20: G. Goodell, W. Aiello, T. Griffin, J. Ioannidis, P. McDaniel, and A. Rubin. Working Around BGP: An Incremental Approach to Improving Security and Accuracy of Interdomain Routing. In Proc. NDSS, Feb. 2003.
• 21: Timothy G. Griffin , F. Bruce Shepherd , Gordon Wilfong, The stable paths problem and interdomain routing, IEEE/ACM Transactions on Networking (TON), v.10 n.2, April 2002
• 22: A. Heffernan, Protection of BGP Sessions via the TCP MD5 Signature Option, RFC Editor, 1998
• 23: K. J. Houle and G. M. Weaver. Trends in Denial of Service Attack Technology. Technical Report, CERT Coordination Center, Oct. 2001.
• 24: G. Huston. Interconnection, Peering, and Settlements. In Proc. Internet Glob. Summit (INET), Jun. 1999.
• 25: A. D. Jaggard, V. Ramachandran, and R. N. Wright. Towards a Realistic Model of Incentives in Interdomain Routing: Decoupling Forwarding from Signaling. Technical Report 2008-02, DIMACS, Rutgers Univ., Apr. 2008.
• 26: S. Kent, C. Lynn, and K. Seo. Secure Border Gateway Protocol (S-BGP). J. Selected Areas in Communications 18(4):582--592, Apr. 2000.
• 27: H. Levin, M. Schapira, and A. Zohar. The Strategic Justification for BGP. Technical Report, Hebrew Univ. of Jerusalem, 2006.
• 28: Hagay Levin , Michael Schapira , Aviv Zohar, Interdomain routing and games, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374388]
• 29: Xin Liu , Xiaowei Yang , David Wetherall , Thomas Anderson, Efficient and secure source authentication with packet passports, Proceedings of the 2nd conference on Steps to Reducing Unwanted Traffic on the Internet, p.2-2, July 07, 2006, San Jose, CA
• 30: Zhuoqing Morley Mao , Jennifer Rexford , Jia Wang , Randy H. Katz, Towards an accurate AS-level traceroute tool, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863996]
• 31: N. Nisan and A. Ronen. Algorithmic Mechanism Design. Games and Economic Behavior 35(1-2):166--196, Apr. 2001.
• 32: V. Padmanabhan and D. Simon. Secure Traceroute to Detect Faulty or Malicious Routing. Proc. HotNets-I, pp. 77--82, Oct. 2002.
• 33: Jeffrey Shneidman , David C. Parkes, Specification faithfulness in networks with rational nodes, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011781]
• 34: Anirudh Ramachandran , Nick Feamster, Understanding the network-level behavior of spammers, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 35: Y. Rekhter, T. Li, and S. Hares. A Border Gateway Protocol 4 (BGP-4). RFC 4271, Jan. 2006.
• 36: Lakshminarayanan Subramanian , Volker Roth , Ion Stoica , Scott Shenker , Randy H. Katz, Listen and whisper: security mechanisms for BGP, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.10-10, March 29-31, 2004, San Francisco, California
• 37: Feng Wang , Lixin Gao, On inferring and characterizing internet routing policies, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948208]
• 38: H. Wang, R. K. Chang, D.-M. Chiu, and J. C. Lui. Characterizing the Performance and Stability Issues of the AS Path Prepending Method. In Proc. ACM SIGCOMM Asia Workshop, Apr. 2005.
• 39: Hao Wang , Haiyong Xie , Yang Richard Yang , Avi Silberschatz , Li Erran Li , Yanbin Liu, On the Stability of Rational, Heterogeneous Interdomain Route Selection, Proceedings of the 13TH IEEE International Conference on Network Protocols, p.40-52, November 06-09, 2005 [doi>10.1109/ICNP.2005.28]
• 40: R. White. Deployment Considerations for Secure Origin BGP (soBGP). Internet Draft (expired), draft-white-sobgp-bgp-deployment-01.txt, Jun. 2003.
• 41: Edmund L. Wong , Praveen Balasubramanian , Lorenzo Alvisi , Mohamed G. Gouda , Vitaly Shmatikov, Truth in advertising: lightweight verification of route integrity, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281123]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Economics, Theory

Keywords:
bgp, incentives