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

35 Scopus citations


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
Number of pages9
StatePublished - 2011
EventIEEE INFOCOM 2011 - Shanghai, China
Duration: Apr 10 2011Apr 15 2011

Publication series

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



All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Electrical and Electronic Engineering


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