The structure and evolution of the AS-level Internet - Amogh Dhamdhere

The global Internet is a "network of networks", consisting of thousands of independently operated and managed networks, called Autonomous Systems (ASes). ASes are of different business types such as regional or international transit providers, content providers, enterprise and academic networks, access providers and content distribution networks -- all of which interconnect to provide end-to-end reachability. There has been much research in recent times on measuring the AS-level topology, characterizing its structural properties, measuring and modeling its evolution, and inferring business relationships between networks. This tutorial will give an overview of research in each of the previously mentioned areas, focusing primarily on the AS-level Internet topology (as opposed to the router-level topology). We will start with available measurements of the Internet topology, highlighting several pitfalls and caveats in interpreting the results of such measurements. The focus will be on what we can and cannot measure reliably with the datasets available to researchers. We will give a brief overview of recent findings on the structural properties of the Internet topology, e.g., degree distribution, diameter, hierarchical structure, etc. We will discuss business relationships between networks, how they affect interdomain traffic flow, and how they can be inferred from available measurements. We will then describe measurement results about the evolution of the AS-level Internet topology, focusing on a recent trend towards a "flattening" Internet hierarchy. We will conclude with an overview of the rich literature on modeling the evolution of the Internet's AS-level structure.