Locating the Root Cause of Large-scale BGP Anomaly with Routing Dependence
Shiqi Zhao, Xiaohong Huang, Pei Zhang · 2024
BGP anomaly has a major impact on the stability, availability, and efficiency of the Internet, thus locating the network element which initiates the anomaly is crucial for network recovery. However, BGP is an information-hiding protocol and BGP anomalies are heterogeneous, which limit the ability to perform root cause localization. This paper proposes an approach to automatically detect large-scale BGP anomaly and locate the root cause in an efficient and generalized fashion. Firstly, time-series analysis and clustering strategy are performed on BGP traffic to ascertain "when" and "where" anomaly happened to start the investigation. Next, based on interdomain routing’s propagation property, a subtopology is constructed which not only reveals the dynamic evolution during anomaly, but also helps narrow down the scale of the Internet for further root cause analysis. Last, by taking deep analysis in the routing characteristics of the root cause from different anomalous scenarios, a routing dependence-based algorithm is developed to realize the localization goal. The proposed method is validated on three different real-world, large-scale BGP anomalies. Results demonstrate its effectiveness and robustness, and in most cases the root causes identified with maximum likelihood are consistent with ground-truths. Further investigations reveal some insights which are helpful for network administrations.