Cutting Through the Noise to Infer Autonomous System Topology

Kirtus G. Leyba, Joshua J. Daymude, Jean Gabriel Young, M. E.J. Newman, Jennifer Rexford, Stephanie Forrest

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationINFOCOM 2022 - IEEE Conference on Computer Communications
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages10
ISBN (Electronic)9781665458221
StatePublished - 2022
Event41st IEEE Conference on Computer Communications, INFOCOM 2022 - Virtual, Online, United Kingdom
Duration: May 2 2022May 5 2022

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Conference41st IEEE Conference on Computer Communications, INFOCOM 2022
Country/TerritoryUnited Kingdom
CityVirtual, Online

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Cutting Through the Noise to Infer Autonomous System Topology'. Together they form a unique fingerprint.

Cite this