k-dense Communities in the Internet AS-Level Topology Graph

Extracting a set of well connected subgraphs as communities from the Internet AS-level topology graph is crucially important for assessing the performance of protocols and routing algorithms, for designing ecient networks, and for evaluating the impact of failures. In addition, these dense zones of the Internet AS-level topology graph enable to individuate which business classes of ASs are interested in interconnecting with each other. A huge number of community extraction algorithms have been proposed in the literature, including the k- core decomposition and the k-dense community detection algorithms. Both algorithms are computationally ecient, however the k-dense is able to discover more well-connected communities. In this paper we investigate the structure of the Internet by exploiting an ecient algorithm for extracting k-dense communities from the Internet AS-level topology graph.The analyses showed that the most well-connected communities consist of a small number of ASs characterized by a high level of clusterization, although they tend to direct a lot of their connections to ASs outside the community. In addition these communities are mainly composed of ASs that participate at the Internet Exchange Points (IXPs) and have a worldwide geographical scope. Regarding k-max-dense ASs we found that they play a primary role in the Internet connectivity since they are involved in a huge number of Internet connections (42% of Internet connections). We also investigated the properties of three classes of k-max-dense ASs: Content Delivery Networks, Internet Backbone Providers and Tier-1. Specically, we showed that CDNs and IBPs heavily exploit IXPs by participating in many of them and connecting to many IXP participant ASs. On the other hand, we found that a high percentage of connections originated by Tier-1 ASs are likely to involve national ASs which do not participate at IXPs.