Near-Deterministic Inference of AS Relationships
Authors:
- 1 April 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-2
Abstract
This paper aims to improve on existing methods by providing a near-deterministic inference scheme (ND-ToR ) for solving the ToR problem. The input for ND-ToR is the Internet Core, a sub-graph that consists of the globally top-level providers of the Internet and their interconnecting links with their already inferred relationship types. Theoretically, given an accurately classified core, the algorithm deterministically infers most of the remaining AS relationships using the AS-level paths relative to this core, without incurring additional inference errors. In real-world scenarios, where the core and AS-level paths can contain errors (due to misconfigurations or measurements mistakes), the algorithm introduces minimal inference mistakes. We show that ND-ToR has relaxed requirements from the core, and proves to be robust under changes in its definition, size and density.Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Acyclic Type of Relationships Between Autonomous Systems2007
- DIMESACM SIGCOMM Computer Communication Review, 2005
- Characterizing the Internet hierarchy from multiple vantage points2003
- A simple conceptual model for the Internet topology2002
- On inferring autonomous system relationships in the InternetIEEE/ACM Transactions on Networking, 2001