Understanding the Internet AS-level structure

The Internet is a vast distributed system consisting of a myriad of independent networks interconnected to each other by business relationships. The border gateway protocol is the glue that keeps this structure connected. Characterizing and modeling the Internet topology is important to our understanding of Internet routing and its interplay with technical, economic and social forces. In this thesis we address several challenges that emerge when studying the Internet connectivity. First, not all the observed changes in connectivity correspond to actual changes in the topology. There are changes that may be caused by transient routing dynamics while others are real topology changes. The problem of distinguishing between these two types of changes is non-trivial, and we call it the liveness problem. We propose a solution to this problem based on a birth/death model of observed links. This solution allows to accurately detect the permanent changes in the Internet topology graph and measure topology dynamics in an accurate way. The second problem in obtaining accurate topology models is the completeness problem , which consists in establishing how much of the real topology is missing from the observed data. We address the completeness problem by defining some bounds on how (in)complete is the graph provided by the current observation. The results using ground truth information obtained from a Tier-1 ISP indicate that the observed Internet graph contains most of the customer-provider links, but may be missing the vast majority of the peer-peer links. Finally, we study how protocol properties such as routing convergence and resilience to prefix hijack attacks depend on the connectivity and relationship between networks. We find that networks at the border of the Internet undergo more severe path exploration because of the higher number of paths available to reach other destinations. On the other hand, we show that Tier-1 networks have the fastest convergence time because of the limited number of alternative routes. In terms of prefix hijack attacks, we surprisingly find that Tier-1 networks at the core of the Internet are vulnerable to hijack attacks from customers because of the business nature of BGP route selection. Based on our observations, we formulate a connectivity recommendation for ISPs to increase their resiliency to these type of attacks.