An analysis of the completeness of the internet AS-level topology discovered by route collectors

In the last decade many studies have exploited the BGP data provided by route collector projects to infer an Internet ASlevel topology to perform several analyses, from discovering its graph properties to assessing its impact on the effectiveness of worm-containment strategies. Nevertheless, the topology that can be extracted from this data is far from being complete, i.e. from this data it is not possible to infer all the AS connections which actually exist among ASes. This thesis analyses the available data and investigates the contribution of route collectors in terms of AS-level connectivity by taking into account economic and geographic characteristics of the Internet AS-level ecosystem. By leveraging on a new metric, named p2c-distance, this analysis shows that the largest amount of ASes currently connected to a route collector belongs to the Internet core, thus the collected data is highly biased and is missing a lot of connections established in the Internet periphery. To address this problem, it should be increased the amount of ASes participating to a route collector project. To this end, this thesis describes how to improve the coverage of route collectors by means of an optimization problem based on the p2c-distance metric, which solution quantifies the minimum number of ASes that should join a route collector in order to obtain an Internet AS-level topology as complete as possible. The results show that route collectors are rarely connected to the selected ASes, highlighting that much effort is needed to devise an ideal route collector infrastructure that would be able to capture a complete view of the Internet. These analyses require the ability to infer the economic relationships which rule the exchange of BGP messages between each pair of connected ASes of the topology. Existing economic tagging algorithms do not take properly into account that BGP data has to be purged from spurious routes, usually caused by router misconfigurations on BGP border routers and which shows up during the BGP path exploration phenomenon. In this thesis an economic tagging algorithm which is able to get rid of these spurious routes is described. This algorithm leverages on robust statistical concepts, rather than on debatable time thresholds and questionable graph metrics. The analyses provided in this thesis are further refined considering the geographical distribution of ASes, which in the global AS-level topology are all considered as a single node. A global analysis could lead to misleading results since an AS connection may hide multiple connections located in different geographic regions, possibly regulated by different economic relationships. From this analysis are indeed highlighted peculiar characteristics of regional topologies previously unrevealed, and it is showed that these considerations also affect the estimated number of feeder ASes needed to improve the completeness of the global AS-level topology.