Improved BGP Convergence via Ghost Flushing

In [1], [2] it was noticed that sometimes it
takes BGP a substantial amount of time and messages
to converge and stabilize following the failure of some
node in the Internet. In this paper we suggest a minor
modification to BGP that eliminates the problem pointed
out and substantially reduces the convergence time and
communication complexity of BGP. Roughly speaking,
our modification ensures that bad news (the failure of a
node/edge) propagate fast, while good news (the establishment of a new path to a destination) propagate somewhat slower. This is achieved in BGP by allowing withdrawal messages to propagate with no delay as fast as the network forwards them, while announcements propagate as they do in BGP with a delay at each node of one minRouteAdver (except for the first wave of announcements).