Technical Report TR733:
Characterization of Internet Routing Anomalies Through Graph Mining
Pablo Moriano, Srivatsan Iyer, and L. Jean Camp
(May 2017), 15 pages
[This is being posted for sharing with Cisco as a tech report only]
- Abstract:
-
Our goal is to contribute to the understanding and detection of control plane anomalies as perturbations in a graph representation of connected autonomous systems (ASes). We reconstructed the autonomous system (AS) level graph for three large-scale routing incidents and evaluated the topological properties of the graphs before, during, and after these events. The three incidents we examined were the Indosat hijacking event in April of 2014; the Telecom Malaysia leak in June of 2015; and the Bharti Airtel Ltd. hijack in November of 2015. Using observations from the AS graph topology, we illustrate that the incidents are visible as anomalies before they are widely diffused. Topological features in the graph as a whole did not show significant immediate changes over the course of these events. However, significant changes are evident in the average path length and clustering coefficient of the observed graphs when they are decomposed using $k$-shell decomposition analysis. The $k$-shell decomposition distinguishes between core and periphery (also called crust) graphs. In this $k$-shell decomposition the core consists of ASes with of at least connectivity $k$, with the crust consisting of those ASes which have less than $k$ connectivity. While anomalous behavior was not observable in the core graph, the events are immediately apparent on the crust. Specifically when the AS-level graph is examined using $k$-shell decomposition, there are topological changes in the crust in path length, and clustering measurements. Our explanation is that, in graph theoretical terms, these incidents require that the initiators move closer to the core, away from the periphery, and the concentric impacts of the disturbances are visible as these move across the crust. This technique has potential for early detection of large-scale control-plane anomalies possibly enabling quicker mitigation.
- Available as:
-
|
