Near-Deterministic Inference of AS Relationships

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Weinsberg, U., Shavitt, Y., Shir, E.
Format: Conference Proceeding
Language:English
Subjects:
Ear
Europe
Heuristic algorithms
Inference algorithms
Internet
North America
Peer to peer computing
Robustness
Routing
Voting
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
DOI:10.1109/INFCOMW.2009.5072167