There's Something About MRAI: Timing Diversity May Exponentially Worsen BGP Convergence
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, the authors show that, ironically, the resulting timer heterogeneity can make routing convergence substantially worse. They examine the widely-used Min Route Advertisement Interval (MRAI) timer that rate-limits update messages to reduce router overhead. They 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").