BGP safety with spurious updates

Martin Suchara, Alex Fabrikant, Jennifer L. Rexford

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

We explore BGP safety, the question of whether a BGP system converges to a stable routing, in light of several BGP implementation features that have not been fully included in the previous theoretical analyses. We show that Route Flap Damping, MRAI timers, and other intra-router features can cause a router to briefly send "spurious" announcements of less-preferred routes. We demonstrate that, even in simple configurations, this short-term spurious behavior may cause long-term divergence in global routing. We then present DPVP, a general model that unifies these sources of spurious announcements in order to examine their impact on BGP safety. In this new, more robust model of BGP behavior, we derive a necessary and sufficient condition for safety, which furthermore admits an efficient algorithm for checking BGP safety in most practical circumstances two complementary results that have been elusive in the past decade's worth of classical studies of BGP convergence in more simple models. We also consider the implications of spurious updates for well-known results on dispute wheels and safety under filtering.

Original languageEnglish (US)
Title of host publication2011 Proceedings IEEE INFOCOM
Pages2966-2974
Number of pages9
DOIs
StatePublished - Aug 2 2011
EventIEEE INFOCOM 2011 - Shanghai, China
Duration: Apr 10 2011Apr 15 2011

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Other

OtherIEEE INFOCOM 2011
Country/TerritoryChina
CityShanghai
Period4/10/114/15/11

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'BGP safety with spurious updates'. Together they form a unique fingerprint.

Cite this