View in EDS PDF Full Text

Incentive-compatible interdomain routing.

Saved in:
Bibliographic Details
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
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 59460272
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Incentive-compatible interdomain routing.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Feigenbaum%2C+Joan%22">Feigenbaum, Joan</searchLink><relatesTo>1</relatesTo><i> joan.feigenbaum@yale.edu</i><br /><searchLink fieldCode="AR" term="%22Ramachandran%2C+Vijay%22">Ramachandran, Vijay</searchLink><relatesTo>2</relatesTo><i> vramachandran@colgate.edu</i><br /><searchLink fieldCode="AR" term="%22Schapira%2C+Michael%22">Schapira, Michael</searchLink><relatesTo>3</relatesTo><i> ms7@cs.princeton.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Distributed+Computing%22">Distributed Computing</searchLink>. Apr2011, Vol. 23 Issue 5/6, p301-319. 19p. 5 Diagrams, 1 Chart.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22ALGOL+%28Computer+program+language%29%22">ALGOL (Computer program language)</searchLink><br /><searchLink fieldCode="DE" term="%22Routing+%28Computer+network+management%29%22">Routing (Computer network management)</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+networks%22">Computer networks</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+architecture%22">Computer architecture</searchLink><br /><searchLink fieldCode="DE" term="%22Vector+analysis%22">Vector analysis</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=59460272
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s00446-011-0126-8
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 19
        StartPage: 301
    Subjects:
      – SubjectFull: ALGOL (Computer program language)
        Type: general
      – SubjectFull: Routing (Computer network management)
        Type: general
      – SubjectFull: Computer networks
        Type: general
      – SubjectFull: Computer architecture
        Type: general
      – SubjectFull: Vector analysis
        Type: general
    Titles:
      – TitleFull: Incentive-compatible interdomain routing.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Feigenbaum, Joan
      – PersonEntity:
          Name:
            NameFull: Ramachandran, Vijay
      – PersonEntity:
          Name:
            NameFull: Schapira, Michael
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 04
              Text: Apr2011
              Type: published
              Y: 2011
          Identifiers:
            – Type: issn-print
              Value: 01782770
          Numbering:
            – Type: volume
              Value: 23
            – Type: issue
              Value: 5/6
          Titles:
            – TitleFull: Distributed Computing
              Type: main
ResultId 1