Member： Justin Loye, Romain Fontugne

Category:

Tags: , , ,

BGP Link Stream Analysis

  • Background: BGP induced AS outages are regularly observed and have a societal and economic impact. BGP data is noisy and hard to analyze.
  • Purpose: BGP graphs analysis can make BGP anomaly detection easy and interpretable.
  • Approach: I) Data collection and preprocessing: create high frequency and global-scale Internet topologies from BGP updates message; II) Data analysis: apply a multi-scale frequency-structure decomposition to characterize changes in BGP topology.

QuickRIB: high frequency and global-scale Internet topologies from BGP updates message

We developed our tool to collect topologies’ data: QuickRIB, an open-source Python tool for efficient (re-)construction and analysis of BGP “routing tables”. In short, this project provide the following functionalities:

  • Downloading and caching RIPE RIS and RouteViews MRT archives.
  • Building an agglomerated RIB table from different collectors.
  • Handling the updates in order to have a complete RIB at a higher frequency.
  • Predefined analysis kernels called observers (e.g. topology graphs, AS paths count, …).
  • Observers are easy to implement and cheap to update

Online repository: https://github.com/JustinLoye/quickrib

QuickRIB enables sub real-time analysis of global routing tables thanks to efficient handling of BGP updates. The following figures show how QuickRIB works:

Level 1: Basic RIB analysis
❌ Low resolution ❌ Long compute time
Basic rib analysis

Level 2: Enhanced frequency with RIB reconstruction (BGPview-like)
✅ High resolution ❌ Long compute time
BGPview rib analysis

Level 3: QuickRIB, sub-realtime analysis with efficient observer updates
✅ High resolution ✅ Fast compute time
QuickRIB rib analysis

Apply a multi-scale structure decomposition of BGP graphs to study BGP outages

Apply a multi-scale structural decomposition to BGP graphs

We perform a Haar wavelet decomposition of the graph edge space to characterize the graph structure at several levels of resolution.


Haar wavelet decomposition of a toy backbone graph

Identify BGP graphs anomaly and relate them to BGP outages

Anomaly detection is then applied to the coefficients of the multi-scale decomposition in order to find subgraph anomalies.
Agglomeration all the coefficients anomaly score yield good results.


Anomaly detector result for an outage in Italy


Anomaly detector result for an outage of Telecom Malaysia

We are currently working on the interpretation in terms of BGP subgraphs and BGP topology.

PAGE TOP