Locating Routing Instability Based on Path Exploration

Root cause analysis of BGP updates is the key to debug and troubleshoot BGP routing problems. However, accurately inferring what is the cause of routing instability and where it originate is very hard. In this paper, we present a novel approach to locate the origin of routing instability by analyzing the relationship of the closed loops formed by intersecting the all the paths in path exploration and the length variation of the paths received in a single vantage point. Then we demonstrate our approach using BGP data obtained by simulations and show that the method is quite effective. Once there is path exploration when a routing event triggering BGP updates, this approach can precisely identify whether the event is a link failure and pinpoint the right place where the event exactly happens if so. Otherwise the approach can deduce the candidate set of locations to a small size.