Damping BGP route flaps

BGP route flap damping (RFD) was anecdotally considered to be a key contributor to the stability of the global Internet inter-domain routing system. However, it was recently shown that RFD can incorrectly suppress for substantially long periods of time relatively stable routes, i.e., routes that only fail occasionally. This phenomenon can be attributed to the complex interaction between BGP path exploration and how the RFD algorithm identifies route flaps. In this paper we identify a distinct characteristic of BGP path exploration following a single network event such as a link or router failure. Based on this characteristic, we distinguish BGP route updates during BGP path exploration from route flaps and propose a novel BGP route flap damping algorithm, RFD+. RFD+ has a number of attractive properties in improving Internet routing stability. In particular, it can correctly suppress persistent route flaps without affecting routes that only fail occasionally. In addition to presenting the new algorithm and analyzing its properties, we also perform simulation studies to illustrate the performance of the algorithm.