Technical Report Number
The Internet consists of a large number of interconnected autonomous systems (ASes). ASes engage in two types of business relationships to exchange traffic: provider-to-customer (p2c) relationship and peer-to-peer (p2p) relationship. Internet AS-level topology can be represented by AS graphs where nodes represent autonomous systems (ASes) and edges represent connectivity between ASes. While researchers have derived AS graphs using various data sources, inferring the types of edges (p2c or p2p) in AS graphs remains an open problem. In this paper we present a new machine learning approach to edge type inference in AS graphs. Our method uses the AdaBoost machine learning algorithm to train a model that predicts the edge types in a given AS graph using two node attributes - degree and minimum distance to a Tier-1 node. We train a model for a BGP graph and validate the model using ground truth AS relationships and CAIDA's inferred AS relationship dataset. Our results show that the model achieves over 92% accuracy on a number of BGP graphs.