Near-Deterministic Inference of as Relationships

Download Now Free registration required

Executive Summary

The discovery of Autonomous Systems (ASes) interconnections and the inference of their commercial Type of Relationships (ToR) has been motivated by the need to accurately calculate AS-level paths. An inherent problem in current algorithms is their extensive use of heuristics, causing unbounded errors that are spread over all inferred relationships. The authors propose a near-deterministic algorithm for solving the ToR inference problem that uses the Internet's core, a dense sub-graph of top-level ASes. They test several methods for creating such a core and demonstrate the robustness of the algorithm to the core's size and density, the inference period, and errors in the core.

  • Format: PDF
  • Size: 158.36 KB