Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Local transit policies and the complexity of BGP Stability Testing
Roma Tre University, Italy.ORCID iD: 0000-0002-9675-9729
2011 (English)In: INFOCOM, 2011 Proceedings IEEE, Institute of Electrical and Electronics Engineers (IEEE), 2011, p. 2957-2965, article id 5935136Conference paper, Published paper (Refereed)
Abstract [en]

BGP, the core protocol of the Internet backbone, is renowned to be prone to oscillations. Despite prior work shed some light on BGP stability, many problems remain open. For example, determining how hard it is to check that a BGP network is safe, i.e., it is guaranteed to converge, has been an elusive research goal up to now. In this paper, we address several problems related to BGP stability, stating the computational complexity of testing if a given configuration is safe, is robust, or is safe under filtering. Further, we determine the computational complexity of checking popular sufficient conditions for stability. We adopt a model that captures Local Transit policies, i.e., policies that are functions only of the ingress and the egress points. The focus on Local Transit policies is motivated by the fact that they represent a configuration paradigm commonly used by network operators. We also address the same BGP stability problems in the widely adopted SPP model. Unfortunately, we find that the most interesting problems are computationally hard even if policies are restricted to be as expressive as Local Transit policies. Our findings suggest that the computational intractability of BGP stability be an intrinsic property of policy-based path vector routing protocols that allow policies to be specified in complete autonomy.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2011. p. 2957-2965, article id 5935136
Series
Proceedings - IEEE INFOCOM, ISSN 0743-166X
National Category
Communication Systems Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-222338DOI: 10.1109/INFCOM.2011.5935136ISI: 000297374703035Scopus ID: 2-s2.0-79960860037ISBN: 9781424499212 (print)OAI: oai:DiVA.org:kth-222338DiVA, id: diva2:1180751
Conference
IEEE INFOCOM 2011, Shanghai, China, 10 April 2011 through 15 April 2011
Note

QC 20180207

Available from: 2018-02-06 Created: 2018-02-06 Last updated: 2018-02-07Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Chiesa, Marco
Communication SystemsComputer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 12 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf