TY - GEN
T1 - BGP safety with spurious updates
AU - Suchara, Martin
AU - Fabrikant, Alex
AU - Rexford, Jennifer
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=79960871042&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79960871042&partnerID=8YFLogxK
U2 - 10.1109/INFCOM.2011.5935137
DO - 10.1109/INFCOM.2011.5935137
M3 - Conference contribution
AN - SCOPUS:79960871042
SN - 9781424499212
T3 - Proceedings - IEEE INFOCOM
SP - 2966
EP - 2974
BT - 2011 Proceedings IEEE INFOCOM
T2 - IEEE INFOCOM 2011
Y2 - 10 April 2011 through 15 April 2011
ER -