A machine learning approach to edge type inference in Internet AS graphs

摘要

The Internet AS topology can be represented by AS graphs where nodes represent ASes and edges represent business relationships between ASes. AS relationship can be broadly classified into two types: provider-to-customer (p2c) and peer-to-peer (p2p). In this paper we present a machine learning approach to edge type inference in AS graphs. Given an AS graph derived from publicly available data source, we use the Gentle AdaBoost machine learning algorithm to train a classifier that classifies the edge types (p2c and p2p) based on a set of node features. We use our method to train classifiers for three AS graphs derived from different data sources-a BGP graph, a traceroute graph, and an IRR graph. The three classifiers achieve 93.97%-97.73% accuracy when validated against ground truth and achieve 81.76%-95.66% accuracy when validated against CAIDA's AS relationship inference dataset. We merge the three individual graphs to obtain a combined graph and propose a method to compute edge types in the combined graph. We analyze the characteristics of the three individual graphs and the combined graph and show that combining the three individual graphs gives us a significantly more complete view of both the p2p and p2c ecosystems in the Internet.