Today, we lack a clear understanding of the dynamics of the Border Gateway Protocol (BGP) and this has largely restricted our ability to address BGP's shortcomings. To gain more insight into BGP's dynamics, this paper proposes the design of a BGP health inferencing system that localizes the root causes of routing changes. Specifically, the inference system addresses two questions: What is the cause of a routing change? Where does a routing change originate? The inference system correlates routing updates across multiple vantage points to narrow down the suspect set of AS's that might have triggered routing changes. Our methodology is primarily targeted towards analyzing events affecting relatively stable prefixes (composing roughly 80% of the routing table), which are known to be the most popular destinations of Internet traffic. For 70% of observed updates to these prefixes, our approach can pinpoint the location of origin to a single inter-AS link. We analytically and empirically argue correctness of several key steps of our methodology and additionally show that our technique can correctly pinpoint the source of several well-known/documented routing events.




Download Full History