IIT Home Page CNR Home Page

k-dense Communities in the Internet AS-Level Topology

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 e_cient networks, and for evaluating the impact of failures. A huge number of community extraction methods have been proposed in the literature, among which the k -core decomposition and the k -clique community extraction methods. The former method is computationally e_cient, but it only discovers coarse-grained and loosely connected communities. On the other hand, k -clique can extract _ne-grained and tightly connected communities, but is NP hard and therefore useless for analyzing the Internet AS -level topology graph. In the paper we investigate the Internet structure by exploiting an e_cient algorithm for extracting k -dense communities, where a k -clique community implies a k -dense community, which in turn implies a k -core community. The paper provides two innovative contributions. The _rst is the application of the k -dense method to the Internet AS-level topology graph - obtained from the CAIDA, DIMES and IRL datasets - to identify well-  connected communities and to analyze how these are connected to the rest of the graph.

The second contribution relates to the study of the most well-connected communities with the support of two additional datasets: a geographical dataset (which lists, for each AS, the countries in which it has at least one geographical location) and the IXP dataset (which maintains, for each IXP, its geographical position and the list of its participants). We found that the k-max - dense community holds a central position in the Internet AS-level topology graph structure since its 101 ASs (less than the 0.3% of Internet ASs) are involved in more than 39% of all Internet connections. We also found that those ASs are connected to at least one IXP and have at least one geographical location in Europe (only 70.3% of them have at least one additional geographical location outside Europe).


2010

External authors: Luciano Lenzini (Dept. of Information Engineering University of Pisa, Italy)
IIT authors:

Chiara Orsini

Foto di Chiara Orsini

Type: TR Technical reports
Field of reference: Information Technology and Communication Systems
IIT TR-021/2010

Activity: Opportunistic Networking and Computing