k-Dense communities in the Internet AS-level topology graph

In this paper we investigate the structure of the Internet by exploiting an efficient 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-1s. Specifically, 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