caa a22 4500 445355174 CHVBK 20180317142857.0 cr unu---uuuuu 170323e20110401xx s 000 0 eng 10.1007/s00446-011-0126-8 doi (NATIONALLICENCE)springer-10.1007/s00446-011-0126-8 Incentive-compatible interdomain routing [Elektronische Daten] [Joan Feigenbaum, Vijay Ramachandran, Michael Schapira] 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, Rekhter and Li in RFC 4271 of the Internet Engineering Task Force, 2006). Using BGP, ASes 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., Varadhan etal. in Comput Networks 32(1):1-16, 2000). Networking researchers have addressed this problem by devising constraints on policies that guarantee BGP convergence without unduly limiting expressiveness and autonomy (see, e.g., Gao and Rexford in IEEE/ACM Trans Network 9(6):681-692, 2001; Griffin etal. in Proceedings of 9th ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM'03), pp. 61-72. ACM Press, New York, 2003). 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 an incentive-compatible, BGP-compatible manner (Feigenbaum etal. in Distribut. Comput 18(1):61-72, 2005; Shneidman and Parkes in Proceedings of 23rd ACM Symposium on Principles of Distributed Computing (PODC'04), pp. 88-97. ACM Press, New York, 2004) but that several other natural classes of policies cannot (Feigenbaum etal. in Theor Comput Sci 378(2):175-189, 2007; Feigenbaum etal. in Distribut Comput 18(4):293-305, 2006). In this paper, we present the first example of a class of interdomain-routing policies that is more general than LCP routing and for which BGP itself is both incentive-compatible and guaranteed to converge. We also present several steps toward a general theory of incentive-compatible, BGP-compatible interdomain routing. Springer-Verlag, 2011 Inter domain-routing protocols nationallicence BGP nationallicence Algorithmic mechanism design nationallicence Routing policies nationallicence Feigenbaum Joan Yale University, New Haven, CT, USA aut Ramachandran Vijay Colgate University, Hamilton, NY, USA aut Schapira Michael Princeton University, Princeton, NJ, USA aut Distributed Computing Springer-Verlag 23/5-6(2011-04-01), 301-319 0178-2770 23:5-6<301 2011 23 446 https://doi.org/10.1007/s00446-011-0126-8 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00446-011-0126-8 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Feigenbaum Joan Yale University, New Haven, CT, USA aut NATIONALLICENCE 700 1- Ramachandran Vijay Colgate University, Hamilton, NY, USA aut NATIONALLICENCE 700 1- Schapira Michael Princeton University, Princeton, NJ, USA aut NATIONALLICENCE 773 0- Distributed Computing Springer-Verlag 23/5-6(2011-04-01), 301-319 0178-2770 23:5-6<301 2011 23 446 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer