Revisiting AS-Level Graph Reduction

摘要

The topological structure of the Internet – theinterconnection of routers and autonomous systems (ASes) –is large and complex. Frequently it is necessary to evaluatenetwork protocols and applications on “Internet-like” graphsin order understand their security, resilience, and performanceproperties. A fundamental obstacle to emulation and simulationis creating realistic Internet-like topologies of reduced order. Wereexamine existing AS graph reduction algorithms and find thatthey struggle to capture graph theoretic properties of moderntopologies and topologies obtained from different sources. Wedevelop a new AS graph reduction method that performs wellacross time periods and data sets.