Cutting Through the Noise to Infer Autonomous System Topology

Abstract

The Border Gateway Protocol (BGP) is a distributed protocol that manages interdomain routing without requiring a centralized record of which autonomous systems (ASes) connect to which others. Many methods have been devised to infer the AS topology from publicly available BGP data, but none provide a general way to handle the fact that the data are notoriously incomplete and subject to error. This paper describes a method for reliably inferring AS-level connectivity in the presence of measurement error using Bayesian statistical inference acting on BGP routing tables from multiple vantage points. We employ a novel approach for counting AS adjacency observations in the AS-PATH attribute data from public route collectors, along with a Bayesian algorithm to generate a statistical estimate of the AS-level network. Our approach also gives us a way to evaluate the accuracy of existing reconstruction methods and to identify advantageous locations for new route collectors or vantage points.

Publication
IEEE Conference on Computer Communications 2022
Kirtus G. Leyba
Kirtus G. Leyba
PhD Student, Computer Science
Joshua J. Daymude
Joshua J. Daymude
Assistant Professor, Computer Science

I am a Christian and assistant professor in computer science studying collective emergent behavior and programmable matter through the lens of distributed computing, stochastic processes, and bio-inspired algorithms. I also love gaming and playing music.

Jean-Gabriel Young
Jean-Gabriel Young
Assistant Professor of Mathematics and Statistics
M. E. J. Newman
M. E. J. Newman
Professor of Physics
Jennifer Rexford
Jennifer Rexford
Professor of Computer Science
Stephanie Forrest
Stephanie Forrest
Professor of Computer Science