Incentive-compatible interdomain routing

ABSTRACT

The routing of traffic between Internet domains, or Autonomous Systems (ASes), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP) [17]. Using BGP, autonomous systems can apply semantically rich routing policies to choose interdomain routes in a distributed fashion. This expressiveness in routing-policy choice supports domains' autonomy in network operations and in business decisions, but it comes at a price: The interaction of locally defined routing policies can lead to unexpected global anomalies, including route oscillations or overall protocol divergence (see, e.g., [20]). Networking researchers have addressed this problem by devising constraints on policies that guarantee BGP convergence without unduly limiting expressiveness and autonomy (see, e.g., [7, 8]).In addition to taking this engineering or "protocol-design" approach, researchers have approached interdomain routing from an economic or "mechanism-design" point of view. It is known that lowest-cost-path (LCP) routing can be implemented in a truthful, BGP-compatible manner [3] but that several other natural classes of routing policies cannot [2, 5]. In this paper, we present a natural class of interdomain-routing policies that is more realistic than LCP routing and admits incentive-compatible, BGP-compatible implementation. We also present several positive steps toward a general theory of incentive-compatible interdomain routing.

REFERENCES

• 1: M. Caesar and J. Rexford. BGP Policies in ISP Networks. IEEE Network Magazine 19(6):5--11, Nov. 2005.
• 2: J. Feigenbaum, D. Karger, V. Mirrokni, and R. Sami. Subjective-Cost Policy Routing. In Proc. Wshp. Internet and Network Economics (WINE), pp. 174--183, LNCS vol. 3828. Springer-Verlag, Dec. 2005.
• 3: 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]
• 4: J. Feigenbaum, V. Ramachandran, and M. Schapira. Incentive-Compatible Interdomain Routing (full version). Yale Univ. Tech. Report 1342. ftp://ftp.cs.yale.edu/pub/TR/tr1342.pdf.
• 5: Joan Feigenbaum , Rahul Sami , Scott Shenker, Mechanism design for policy routing, 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.1011770]
• 6: L. Gao, T. G. Griffin, and J. Rexford. Inherently Safe Backup Routing with BGP. In Proc. IEEE INFOCOM'01, pp. 547--556. IEEE Computer Society, Apr. 2001.
• 7: 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]
• 8: Timothy G. Griffin , Aaron D. Jaggard , Vijay Ramachandran, Design principles of policy languages for path vector protocols, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863964]
• 9: Timothy G. Griffin , F. Bruce Shepherd , Gordon Wilfong, Policy Disputes in Path-Vector Protocols, Proceedings of the Seventh Annual International Conference on Network Protocols, p.21, October 31-November 03, 1999
• 10: 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
• 11: J. Green and J. Laffont. Incentives in Public Decision Making. In Studies in Public Economics, vol. 1, pp. 65--78. North Holland, Amsterdam, 1979.
• 12: 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
• 13: G. Huston. Interconnection, Peering, and Settlements. In Proc. Internet Global Summit (INET). The Internet Society, Jun. 1999.
• 14: E. Koutsoupias and C. H. Papadimitriou. Worst-case Equilibria. In Proc. 16th Symp. Theoretical Aspects of Computer Science (STACS), pp. 387--396, LNCS vol. 1563 (G. Meinel and S. Tison, eds.). Springer-Verlag, Mar. 1999.
• 15: J. Moy. Open Shortest Pouting First (OSPF) version 2. RFC 2328. Internet Engineering Task Force (IETF), Apr. 1998.
• 16: N. Nisan and A. Ronen. Algorithmic Mechanism Design. Games and Economic Behavior 35(1,2):166--196, 2001.
• 17: Y. Rekhter and T. Li. A Border Gateway Protocol (BGP-4). RFC 1771. Internet Engineering Task Force (IETF), Mar. 1995.
• 18: 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]
• 19: João Luís Sobrinho, An algebraic theory of dynamic network routing, IEEE/ACM Transactions on Networking (TON), v.13 n.5, p.1160-1173, October 2005 [doi>10.1109/TNET.2005.857111]
• 20: K. Varadhan, R. Govindan, and D. Estrin. Persistent Route Oscillations in Interdomain Routing. Computer Networks 32(1):1--16, Jan. 2000.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Economics

Keywords:
border gateway protocol (BGP), distributed algorithmic mechanism design, interdomain routing