Revisiting AS-Level Graph Reduction

Erik Rye, Justin Rohrer, and Robert Beverly
Proceedings of the IEEE Network Science for Communication Networks (NetSciCom 2016) Workshop,
San Francisco, CA, April 2016 (to appear).

The topological structure of the Internet -- the interconnection of routers and autonomous systems (ASes) -- is large and complex. Frequently it is necessary to evaluate network protocols and applications on ``Internet-like'' graphs in order understand their security, resilience, and performance properties. A fundamental obstacle to emulation and simulation is creating realistic Internet-like topologies of reduced order. We reexamine existing AS graph reduction algorithms and find that they struggle to capture graph theoretic properties of modern topologies and topologies obtained from different sources. We develop a new AS graph reduction method that performs well across time periods and data sets.

[PDF] [BibTeX]
[Python graph reduction implementations]
[Presentation Slides]

[ Return to publications ]