An Online Mechanism for BGP Instability Detection and Route Quarantine

The importance of Border Gateway Protocol (BGP) as the primary inter-Autonomous System (AS) routing protocol imposes the requirement of stability on the route selection process of BGP. The normal operation of the current BGP implementation causes inflation in update messages in response to even minor changes in the routing tables. This intrinsic nature of BGP aggravates the instability of the network during failure events. In this work we propose an instability detection architecture that can be implemented by individual routers. We use statistical pattern recognition techniques for instability detection and the algorithm is evaluated using real Internet trace data. We show that instabilities due to misconfiguration, node failures and several worm attacks can be detected with an average detection delay of 63 mins. In response to the instability detection we propose a few route quarantine mechanisms to limit the propagation of the instability. We evaluate these measures using trace driven simulations and show that they reduce the inflation of update messages without adversely affecting network stability.