There's something about MRAI: Timing diversity can exponentially worsen BGP convergence

Alex Fabrikant, Umar Syed, Jennifer L. Rexford

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

28 Scopus citations

Abstract

To better support interactive applications, individual network operators are decreasing the timers that affect BGP convergence, leading to greater diversity in the timer settings across the Internet. While decreasing timers is intended to improve routing convergence, we show that, ironically, the resulting timer heterogeneity can make routing convergence substantially worse. We examine the widely-used Min Route Advertisement Interval (MRAI) timer that rate-limits update messages to reduce router overhead. We show that, while routing systems with homogeneous MRAI timers have linear convergence time, diverse MRAIs can cause exponential increases in both the number of BGP messages and the convergence time (as measured in "activations"). We prove tight upper bounds on these metrics in terms of MRAI timer diversity in general dispute-wheel-free networks and economically sensible (Gao-Rexford) settings. We also demonstrate significant impacts on the data plane: blackholes sometimes last throughout the route-convergence process, and forwarding changes, at best, are only polynomially less frequent than routing changes. We show that these problems vanish in contiguous regions of the Internet with homogeneous MRAIs or with next-hop-based routing policies, suggesting practical strategies for mitigating the problem, especially when all routers are administered by one institution.

Original languageEnglish (US)
Title of host publication2011 Proceedings IEEE INFOCOM
Pages2975-2983
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
CountryChina
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 'There's something about MRAI: Timing diversity can exponentially worsen BGP convergence'. Together they form a unique fingerprint.

  • Cite this

    Fabrikant, A., Syed, U., & Rexford, J. L. (2011). There's something about MRAI: Timing diversity can exponentially worsen BGP convergence. In 2011 Proceedings IEEE INFOCOM (pp. 2975-2983). [5935139] (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFCOM.2011.5935139