Algorithms for the Inference of the Commercial Relationships between Autonomous Systems: Results Analysis and Model Validation

The Internet has recently been object of several studies concerning its structural properties and the behavior of routing protocols. One of the most interesting challenges is the inference of commercial relationships between Autonomous Systems. This knowledge would provide a deeper insight into the laws governing routing processes, and would constitute a useful guideline for choosing connection strategies and device configurations. Several algorithms have been proposed for inferring the relationships on the basis of the routing data of the Border Gateway Protocol (BGP). This work aims at performing an analysis of the results produced by state-of-the-art algorithms, with the purpose of investigating the meaningfulness of such results. This is achieved by running the algorithms extensively on several BGP data sets and by observing how assigned relationships change. Two kinds of analysis are used for doing this: one considers the relationships assigned by the same algorithm on data sets relative to different time instants; the second takes into account the relationships assigned by different algorithms on the same data set. We a methodology and implement some tools for performing the two kinds of analysis and apply the methodology to two well known algorithms, using publicly available data sets. What comes out is that the number of AS pairs whose relationship is steadily assigned never falls below 94% of the overall pairs, and that the solutions computed by the two algorithms overlap for more than 90% of the pairs. This is an evidence of the fact that the inference is well-founded, i.e., it is not heavily influenced by routing oscillations, and that following different approaches almost yields the same solution, which further validates its trustworthiness. -