BGP convergence delay after multiple simultaneous router failures: Characterization and solutions

Border Gateway Protocol (BGP) is the default routing protocol between various autonomous systems (AS) in the Internet. In the event of a failure, BGP may repeatedly withdraw routes to some destinations and advertise new ones until a stable state is reached. It has been found that the corresponding convergence delay could stretch into hundreds of seconds or more for isolated outages and can lead to high packet drop rates. Previous studies on BGP failures have looked at isolated failures scenarios. In this paper we characterize BGP convergence delay for multiple failure scenarios. We show that the convergence delay depends on a variety of topological and BGP parameters, and can be substantial for large failures. We also observe that the Minimum Route Advertisement Interval (MRAI) and the processing overhead at the routers during the re-convergence have a significant effect on the BGP convergence delay. We propose two new schemes to bring down the processing overload at BGP routers, resulting in reduced convergence delays. We show that these schemes, combined with the tuning of the MRAI value, accelerate the BGP convergence process significantly, and can thus limit the impact of multiple simultaneous failures.