Incentive-compatible interdomain routing.
Saved in:
| Title: | Incentive-compatible interdomain routing. |
|---|---|
| Authors: | Feigenbaum, Joan1 joan.feigenbaum@yale.edu, Ramachandran, Vijay2 vramachandran@colgate.edu, Schapira, Michael3 ms7@cs.princeton.edu |
| Source: | Distributed Computing. Apr2011, Vol. 23 Issue 5/6, p301-319. 19p. 5 Diagrams, 1 Chart. |
| Subjects: | ALGOL (Computer program language), Routing (Computer network management), Computer networks, Computer architecture, Vector analysis |
| 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, Rekhter and Li in RFC 4271 of the Internet Engineering Task Force, ). 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 et al. in Comput Networks 32(1):1-16, ). 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, ; Griffin et al. in Proceedings of 9th ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM'03), pp. 61-72. ACM Press, New York, ). 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 et al. in Distribut. Comput 18(1):61-72, ; Shneidman and Parkes in Proceedings of 23rd ACM Symposium on Principles of Distributed Computing (PODC'04), pp. 88-97. ACM Press, New York, ) but that several other natural classes of policies cannot (Feigenbaum et al. in Theor Comput Sci 378(2):175-189, ; Feigenbaum et al. in Distribut Comput 18(4):293-305, ). 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Distributed Computing is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| 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, Rekhter and Li in RFC 4271 of the Internet Engineering Task Force, ). 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 et al. in Comput Networks 32(1):1-16, ). 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, ; Griffin et al. in Proceedings of 9th ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM'03), pp. 61-72. ACM Press, New York, ). 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 et al. in Distribut. Comput 18(1):61-72, ; Shneidman and Parkes in Proceedings of 23rd ACM Symposium on Principles of Distributed Computing (PODC'04), pp. 88-97. ACM Press, New York, ) but that several other natural classes of policies cannot (Feigenbaum et al. in Theor Comput Sci 378(2):175-189, ; Feigenbaum et al. in Distribut Comput 18(4):293-305, ). 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. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 01782770 |
| DOI: | 10.1007/s00446-011-0126-8 |
