Deductive Way of Reasoning about the Internet AS Level Topology

Abstract

Our current understanding about the AS level topology of the Internet is based on measurements and inductive-type models which set up rules describing the behavior (node and edge dynamics) of the individual ASes and generalize the consequences of these individual actions for the complete AS ecosystem using induction. In this paper we suggest a third, deductive approach in which we have premises for the whole AS system and the consequences of these premises are determined through deductive reasoning. We show that such a deductive approach can give complementary insights into the topological properties of the AS graph. While inductive models can mostly reflect high level statistics (e.g. degree distribution, clustering, diameter), deductive reasoning can identify omnipresent subgraphs and peering likelihood. We also propose a model, called YEAS, incorporating our deductive analytical findings that produces topologies contain both traditional and novel metrics for the AS level Internet.

References in corpus (12)

• Emergence of scaling in random networks
• Error and attack tolerance of complex networks
• Power laws, Pareto distributions and Zipf's law
• Hyperbolic Geometry of Complex Networks
• Highly Optimized Tolerance: Robustness and Power Laws in Complex Systems
• Navigability of Complex Networks
• Sustaining the Internet with Hyperbolic Mapping
• Class of correlated random networks with hidden variables
• Pattern Detection in Complex Networks: Correlation Profile of the Internet
• Competing activation mechanisms in epidemics on networks
• Generating hierarchial scale free graphs from fractals
• Modeling the IPv6 Internet AS-level Topology