The Internet ASN graph#

Claudio Risso (Universidad de la República, Uruguay), Carlos Martínez (LACNIC)

• Why: A framework for building structural models of the Internet's AS-level graph — relevant to the PM's BGP-internals interest for policy simulation (RPKI/ASPA/ROA scenarios), topology reasoning, and understanding measurement vantage-point bias.
• What: A methodology plus first results: reconstruct the AS-level graph from a full month of MRT data (24 RIPE RIS + 4 RouteViews collectors, April 2025). Raw graph: ~86,400 ASes / ~750,000 edges, 36.8% degree-1 leaves, mean degree 16.6 — Internet transit is only ~0.02% as dense as a full mesh. After reducing to the transit-only graph (84,497 nodes / 389,442 adjacencies) and homeomorphic reduction, the "backbone" is a 2-connected component of ~29,923 nodes, with dense cliques of 31 and 35 ASes (disconnecting one member of the 35-clique requires 34 simultaneous failures). The work also classifies node lifecycles (stable, born, dying, flapping, sporadic, reborn) and explicitly studies the probe-distribution problem: how many and which collectors are needed to reconstruct the topology.
• How: All ASPATHs from MRT full + update dumps parsed with BGPStream; each ASPATH hop becomes an edge; bogons and prepends discarded; then combinatorial-optimization analysis (biconnected components, articulation points, n-connectivity) to identify core structure.
• Where applicable: Routing-policy simulation, topology research, and data-informed peering/deployment decisions. Built from public collector data with the usual vantage-point bias; the probe-placement question is open, which itself matters for anyone consuming collector-derived "Internet views."