Member： Justin Loye, Romain Fontugne

Category: Exploring

Tags: AS topology, BGP, temporal networks, anomaly detection

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: Detect BGP anomalies and explain their source
• 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. Our detection pipeline have the advantage to be unsupervised, explainable and to work in near-realtime

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

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

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

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. The edge space is ordered by edge activity to capture the postulate: “a graph is anomalous when its the active parts become inactive and vice-versa”. We then perform a statistical test to assess if the current BGP graph Q is consistent to historical graphs H

Identify BGP graphs anomaly and relate them to BGP outages

We test our approach on 10 historical scenarios for both global-level outage and AS-level outage. The later allow our approach to be explainable

Global-level outage

AS-level outages Our method outperforms IODA BGP prefix visibility signal to detect route leaks