The Internet is a highly engineered communication infrastructure continuously growing over time. It consists of Autonomous Systems (ASes) each of which can be considered a network, with its own routing policy, administrated by a single authority. ASes peer with each other to exchange traffic and use the Border Gateway Protocol (BGP)  to exchange routing and reachability information in the global routing system of the Internet. Therefore, the Internet can be represented by a graph where ASes are nodes and BPG peering relationships are links.
The structure of the Internet has been studied by many authors and the literature on the subject is vast. One of the most used methods is the statistical analysis of different metrics characterizing the AS graph     . There are not many studies concerning the evolution of the Internet over time    and because the amount of data to analyze tends to grow dramatically, often only a limited number of properties are considered. The purpose of this work is to study the evolution of the Internet considering features related to both its topology and data traffic. To achieve this goal we consider for each year of the period 2008-2017 a snapshot of the undirected AS graph, introduce three classes of metrics related to structure, connectivity, centrality and analyze how they change over time. The paper is organized as follows: in Section 2, we describe the datasets; in Section 3, we define the adopted metrics and for each of them explain its importance; we report the results in Section 4. Finally, in Section 5, we summarize the results and make the final considerations.
2. Data Sets
The ASes graphs have been constructed from the publicly available IPv4 Routed /24 AS Links Dataset provided by CAIDA  . AS links are derived from traceroute-like IP measurements collected by the Archipelago (Ark)   infrastructure and a globally distributed hardware platform of network path probing monitors. The association of an IP address with an AS is based on the RouteViews  BGP data and the probed IP paths are mapped into AS links. We exclude multi-origin ASes and AS sets because they may introduce distortion in the association process due to the fact that the same prefix could be advertised by many different ASes creating an ambiguity in the mapping process between IP addresses and ASes. The sizes of the ASes graphs analyzed in this work are shown in Table 1.
3. Description of Metrics
In this section, we introduce the metrics chosen for this analysis whose summary scheme is shown in Table 2. For each metric, we give a short description and briefly discuss its importance. We use the notation to indicate an AS graph which has N nodes and E edges.
3.1. Degree Distribution
The degree distribution is the probability that a random chosen node
Table 1. Sizes of the ASes undirected graphs.
Table 2. Metrics used to study the evolution of the Internet at the AS level over time.
has degree k. If a graph has nodes with degree k then . Since is a probability distribution it satisfies the normalization condition where and are the minimum and maximum degree, respectively. From we can calculate the average degree . For a random network follows a binomial distribution and in the limit of sparse network , where is the link density, it is well approximated by a Poissonian. The Internet, as many other real networks, can be considered sparse and, moreover, it is scale-free which means that it contains both small and very high degree nodes and this feature cannot be reproduced by a Poissonian. Many studies agree that the degree distribution follows a power law though deviations have been observed    . For each snapshot of the AS graph we calculate the best fit power law parameters and and verify the statistical plausibility of this model.
3.2. K-Core Decomposition
A k-core of a graph is obtained by removing all nodes with degree less than k. Therefore, the k-core is the maximal subgraph in which all nodes have at least degree k. The 0-core is the full graph and coincides with the 1-core if there are no isolated nodes, as in the case of the Internet. The k-core decomposition is a way of peeling the graph by progressively removing the outermost low degree layers up to the innermost high degree core which we call nucleus. We denote by the coreness of the nucleus, and by Ɲn (Ɲk) and ( ) the number of ASes and edges in the nucleus (in the k-core). In the case of the Internet the analysis of the k-core decomposition over time is useful for understanding whether its nucleus, composed of high degree ASes, evolves differently from its periphery.
3.3. Clustering Coefficient
The local clustering coefficient of a node i of degree k is the ratio of the actual number of edges connecting its neighbors to the maximum possible number of edges that could connect them. For an undirected graph . By averaging over all nodes we obtain the global clustering coefficient . For a random network, C is independent of the node’s degree and decreases with the size of the graph as . Scale-free networks exhibit a quite different behavior. For example, the clustering coefficient of a scale-free network obtained from the Barabasi-Albert model.  follows , which for large N is higher than that of a random network. An important quantity is , the average clustering coefficient of degree k nodes. It has been shown  that it is the three-point correlation function which is the probability that a degree k node is connected to two other nodes which in their turn are joined by an edge. can be used to study the hierarchical structure of networks   .
3.4. Shortest Path Length
The shortest path length between two nodes is the minimum number of hops needed to connect them. Of course, for any pair of nodes there may be several shortest paths connecting them. The shortest path length distribution provides, for a given number h of hops, the number of shortest paths of length h. We call S the average shortest path length. The diameter D is the longest shortest path. The importance of the shortest paths is mainly related to routing. Many routing algorithms are based on the shortest path length. Adaptive algorithms allow changing routing decision to optimize traffic load and prevent incidences of congestions. The knowledge of the available shortest paths is then crucial for routing efficiency.
3.5. Closeness Centrality
The closeness centrality of a node i is the inverse of its average shortest path length to all other nodes: where is the shortest path length between i and j. Nodes with high are those closest to all others and can be considered central in the network. On the contrary, nodes with low are, on average, far away from the others and can be considered peripheric.
3.6. Betweenness Centrality
The concept of betweenness centrality applies to both nodes and edges. The betweenness centrality of a node i is defined as where the sum is over all pairs of nodes, is the number of shortest paths and is the number of those passing through i. If then and if , . The betweenness centrality of an edge e is defined in the same way. In this case is the number of shortest paths containing e. Efficient routing policies exploit as much as possible available shortest paths, hence a node (edge) with high betweenness centrality carries large traffic load. In  the betweenness centrality was used to investigate the evolution of networks whose nodes may break down due to overload and in  it was used to define the load of a node for studying the problem of data packet transport in power law scale-free networks.
In this section, we compare the measurements of the metrics concerning the Internet AS graphs obtained for each year of the decade 2008-2017 and report the corresponding results.
4.1. Degree Distribution
Figure 1 shows the node probability degree distributions and their complementary cumulative functions (CCDF). For all data sets the peak of the degree distribution is for , a result already reported in  where it is claimed that it is due to the AS number assignment policies. While the edge density is around during the decade 2008-2017, the general trend is a growth over time for both and as shown in Table 3. This means that the Internet has become more connected preserving its sparse nature. All degree distributions have a similar form. In order to verify the statistical plausibility of the power law model we perform a goodness of fit test based on the Kolmogorov-Smirnov statistic  which provides a p-value. The power law has statistical support if . From Table 3 we see that even if the best-fit exponent is always around the value the power law can be considered a reliable model only for the distributions of the years 2008, 2010 and 2011. Since for the majority of the largest data sets , we could say that at the AS level the evolution of the Internet cannot be explained by models which predict a pure power law degree distribution.
4.2. K-Core Decomposition
The left plot of Figure 2 shows for each year of the decade 2008-2017 the distributions of ASes and edges in each k-core. We observe that in general for each
Figure 1. Node degree probability distributions (left) and their CCDF (right).
Table 3. The table shows: the edge density , the average degree , the maximum degree . The best fit power law cut off and exponent are and . The condition indicates statistical plausibility of the power law model.
Figure 2. Left: number of ASes and edges in each k-core during the decade 2008-2017. Right: for each year of the decade 2008-2017 are shown, as a function of the size of the AS graph: the highest coreness (top); the percentage of ASes (middle) and edges (bottom) in the Internet nucleus.
k-core both the number of ASes and edges increase over time. The evolution of the Internet nucleus is shown in the right plot of Figure 2. The coreness of the nucleus increases over time (in 2016 and 2017 it has the same value). The fraction of ASes in the nucleus is quite stable over time although in absolute value Ɲn increases from 2008 to 2013, decreases in 2014 and 2015 and then increases again until 2017. We observe the same trend also for the number of edges in the nucleus as shown in Table 4.
On average the nucleus contains ~0.4% of all ASes and ~4% of all edges. Carmi et al.  predicted the increase of and Ɲn as a power of N on the base of a numerical simulation assuming a scale-free growing model with the same parameters of the real Internet. Instead, from the analysis of the Internet at the AS level during the period 2001-2006 Guo-Quing Zhang et al.  found no clear evidence of the exponential growth of and observed a stability of its value after 2003. They also found that the size of the nucleus exhibits large fluctuations over time.
We now examine in the left plot of Figure 3 how the fraction of ASes and edges varies in the periphery of the Internet from the 2 to the 10-core. We start from the core of order 2 because in our case there are no isolated ASes.
Figure 3. Left: fraction of ASes and edges in the periphery of the Internet from the 2 to the 10-core. Right: edge density as a function of the size of the AS graph for the k-cores and the Internet nucleus.
Table 4. Left: for each year in the decade 2008-2017 are shown the coreness of the Internet nucleus, and the number of ASes Ɲn and edges it contains. Right: percentage variation in the number of ASes ∆Ɲk and edges in the core of order k obtained comparing 2008 and 2017 data. The last column reports the average edge density calculated over all the years 2008-2017.
Compared to the evolution of the nucleus it is evident that the periphery evolves with a different dynamics. In Table 4 we compare for each k-core the number of ASes and edges it contained in 2008 and 2017 and report the percentage variation. Results clearly show that the nucleus is much more stable than the periphery. The connectivity of each core can be studied by looking at its edge density which is defined as . In the right plot of Figure 3 is shown as a function of N and in Table 4 is reported its average value. The edge density increases with the coreness showing that the inner is the core the more it is connected. It is interesting to note that the edge density of the Internet nucleus is three order of magnitude higher than that of the most external 2-core. From a topological point of view this might imply the existence of an underlying hierarchical organization of the Internet with a small fraction of big ASes tightly connected among them and many regions composed of ASes with low or medium number of links. This structural property is investigated in more detail in the next section.
Tauro et al.  studied the topology of the Internet from the end of 1997 to the middle of 2000. They introduced the concept of importance of a node on the base of its degree and effective eccentricity defined as the minimum number of hops required to reach at least 90% of all other nodes. The most important nodes have high degree and low effective eccentricity. They found that the structure of the Internet is hierarchical with a highly connected core surrounded by layers of nodes of decreasing importance.
4.3. Clustering Coefficient
The clustering coefficient has been used to investigate the hierarchical organization of real networks. The hierarchy could be a consequence of the particular role of the nodes in the network. A stub AS does not carry traffic outside itself and is connected to a transit AS that, on the contrary, is designed for this purpose. The hierarchy of the Internet is rooted in its geographical organization in international, national backbones, regional and local areas. This is the skeleton of the Internet. International and national backbones are connected to regional networks which finally connect local areas to the Internet, implementing in such a way a best and less expensive strategy. It is reasonable to suppose that this hierarchical structure introduces correlations in the connectivity of the ASes. A. Vázquez et al.  showed that the hierarchical structure of the Internet is captured by the scaling and found . Ravasz and Barabasi  proposed a deterministic hierarchical model for which and using a stochastic version of the model showed that the hierarchical topology is again well described by the scaling even if the value of can be tuned by varying other network parameters.
In the left plot of Figure 4 is shown the average clustering coefficient as a function of the size of the AS graph and in the fourth column of Table 5 is reported its value for all the years 2008-2017. Apart from the year 2013, weakly increases over time and the minimum and maximum values are ~0.59 and ~0.68 measured in 2008 and 2017, respectively. For the deterministic hierarchical model studied in  , C is independent of N. The weak dependence of C on N might indicate the presence of a hierarchical organization in the structure of the Internet. To further investigate on this point, we study . The right plot of Figure 4 shows for the AS graph only for the year 2017 because for all other years the plots are almost overlapping. The best fit with the power law provides for all the years values of which differs only by ~0.1% obtaining, on average, . In the same figure is also shown the slope of the function and even if it nicely follows the slope of the experimental points the goodness of fit test does not give any statistical support
Figure 4. Left: average clustering coefficient as a function of the size of the AS graph during the decade 2008-2017. Right: average clustering coefficient as a function of the node’s degree for the AS graph of the year 2017. The solid line shows the slope .
Table 5. For each year of the decade 2008-2017 are shown the average shortest path S, the diameter D and the average clustering coefficient C.
to the scaling . However, data show that decreases with k especially for . Low degree ASes have high neighbourhood connectivity and, on the contrary, neighbours of big hub ASes are slightly connected among them. This is consistent with a hierarchical organization in which big ASes are connected to many regions with high internal cohesiveness and composed of low or medium degree ASes, and these regions are poorly connected among them. Since the plots of the AS graph snapshots overlap, to study the evolution of the clustering coefficient over years we compare the CCDF of in Figure 5. For our convenience we consider in more detail three degree regions: high ( ), medium ( ), low ( ) and also plot them in the same figure. We observe that in the high degree region the CCDF
Figure 5. CCDF of for the years 2008-2017 (top left). The figure shows in more detail the high (top right), medium (bottom left) and low (bottom right) degree regions.
distributions are very intertwined indicating that during the decade 2008-2017 this region was rather static. In the medium degree region a clear separation emerges between the CCDF of the different years and for a given value of the CCDF increases over time. The gap is even more pronounced in the peripheric low degree region. This result suggests that the evolution of the Internet from 2008 to 2017 was not uniform and the most significant changes mainly affected its middle and even more its periphery, and the neighborhood connectivity in these regions increased over time.
4.4. Shortest Path Length
The left plot of Figure 6 shows the shortest path length distributions for all the years 2008-2017 and in Table 5 are reported the average values S and the diameter D. We observe that the overall trend is a slight decrease of S over time with an average of ~3.0. Zhao et al.  analyzed BGP data from the Route-Views Project  in the period 2001-2006 and observed a very weak decreasing of S. They measured a decreasing rate of ~2.5 × 10−4 and found and . They noticed that simple power law and small world models, which predict a growth of S with the size of the Internet, fail to explain the overall slight decrease of S over time and argued that this might be due to the fact that the Internet expands according to many factors not considered by simple models like competitive and cooperative processes (like commercial relationships), policy-driven strategy and other human choices. From the comparison of our result with that of Zhao et al. there are indications the S has been slightly reduced during the period 2001-2017. This reinforces the fact that a pure power law model could not explain the evolution of the Internet because for
Figure 6. Left: shortest path distributions for the AS graphs during the decade 2008-2017. Right: number of shortest paths of different lengths hn as a function of the size of the AS graph. Here hn indicates a shortest path whose length is n hops.
it predicts   . The right plot of Figure 6 shows, for different lengths, the number of shortest paths over time. The 3-hops shortest paths are the most numerous, as expected, and their number increases over time.
4.5 Closeness Centrality
The closeness centrality as a function of the node’s degree k is shown in Figure 7 for the years 2008 and 2017. The plots of the other years have similar slope. Their curves lie in between of those plotted and are not shown in the figure for better readability because they overlap in the region . We observe that increases with the degree which means that big hub ASes are in the center of the Internet while low degree ASes are peripheric. We consider in three regions: , and corresponding respectively to low, medium and high degree and we find that within errors it is almost constant over the period 2008-2017 with average values of 0.392 ± 0.007, 0.434 ± 0.004 and 0.484 ± 0.004.
4.6. Betweenness Centrality
The average node betweenness centrality as a function of the degree k is shown in Figure 8 for the AS graphs of the years 2008 and 2017. As in the case of the closeness centrality, we do not plot the curves of the other years for readability reasons. However, for all the years the average node betweenness centrality increases with the degree which means that the higher is the degree of an AS the more is the number of shortest paths passing through it. There is evidence of an overall slight decrease of during the evolution of the Internet from 2008 to 2017. The overall average values of calculated in 2008 and 2017 are ~7.1 × 10−5 and ~3.6 × 10−5 respectively. In Table 6 are reported the average values of calculated in the degree regions , and . In order to study we represent an edge as a point of the xy plane whose coordinates are the degrees of the nodes it connects. In Figure 9 is
Table 6. Average node betweenness centrality in the degree regions , and .
Figure 7. Average closeness centrality as a function of the degree k for the AS graphs of the years 2008 and 2017.
Figure 8. Average node betweenness centrality as a function of the degree k for the AS graphs of the years 2008 and 2017.
Figure 9. Average edge betweenness centrality for the AS graphs of the years 2008-2017. Left: color mapped 3D plots of . To each edge is associated with a point of the xy plane whose coordinates are the degree of the nodes it connects. Right: colored contour maps of the figures on the left.
shown, for each year of the decade 2008-2017, the colored 3D map of the average . The highest is associated to edges which have at least a high degree ( ) AS as a terminal. Edges connecting low or medium degree ASes have lower . This is what one would expect considering that high degree ASes are the backbone of the Internet and the most part of the shortest routes should cross them. We also observe a slight decrease of over time. The overall average was ~2.2 × 10−5 in 2008 and ~0.7 × 10−5 in 2017, indicating that somehow the Internet has become less congested although it has expanded. By looking at the colored contour maps shown on the right side of Figure 9 we infer that during its evolution the lowering of affected first the part of the Internet containing low and medium degree ASes ( ) and subsequently the backbone. The overall average values of and were measured also in  for three sources of data. Authors found that for the AS graph of the Internet constructed from the CAIDA Skitter  repository with data collected in March 2004 and were ~11.0 × 10−5 and ~5.4 × 10−5. This is a further confirmation that during the evolution of the Internet the traffic load somehow decreases. This may be due to the adoption of more efficient routing policies and to infrastructural upgrades with more advanced network devices.
We studied the evolution of the Internet at the AS level during the decade 2008-2017. For each year of the decade we considered a snapshot of the AS undirected graph and analyzed how a wide range of metrics related to structure, connectivity and centrality varies over time. During the decade 2008-2017 the Internet almost doubled its size and became more connected. The Internet is a scale-free network because it contains both very high and low degree ASes. For all the years 2008-2017 the best fit of the degree distributions with a power law provides values of the exponent very close to each other and around . However, the statistical analysis shows that a pure power law model fails to explain the scale-free properties. The study of the k-core decomposition shows that Internet has a small internal nucleus composed of high degree ASes much more stable and connected than external cores. We investigated the hierarchical organization of the Internet by studying the average clustering coefficient C. We found that there are indications of an overall hierarchical organization of the Internet where a small fraction of big ASes are connected to many regions with high internal cohesiveness containing low and medium degree ASes and these regions are slightly connected among them. The average shortest path length S of the Internet slightly decreased during the decade 2008-2017 form ~3.1 to ~2.9 measured in 2008 and 2016-2017 respectively. Regardless of the analyzed year, the closeness centrality of an AS increases with its degree. Hence, big ASes are in the center of the Internet and low degree ASes are in the periphery. It is reasonable to assume that the traffic load of an AS or carried by an edge is proportional to the number of shortest paths passing through the AS and containing the edge. These measurements can be quantified by the average node and edge betweenness centrality and . There is evidence of an overall slight decrease of both and during the decade 2008-2017, suggesting that during its evolution the Internet became less congested.
The computing resources and the related technical support used for this work have been provided by CRESCO/ENEAGR\-ID High Performance Computing infrastructure and its staff  . CRESCO/ENEAGRID High Performance Computing infrastructure is funded by ENEA, the Italian National Agency for New Technologies, Energy and Sustainable Economic Development and by Italian and European research programmes, see https://www.eneagrid.enea.it for information.
 Mahadevan, P., Krioukov, D., Fomenkov, M., Dimitropoulos, X., Claffy, K.C. and Vahdat, A. (2006) The Internet AS-Level Topology: Three Data Sources and One DefinitiveMetric. ACM SIGCOMM Computer Communication Review, 36, 17-26.
 Dhamdhere, A. and Dovrolis, C. (2008) Ten Years in the Evolution of the Internet Ecosystem. Proceedings of the 8th ACM SIGCOMM Conference on Internet Measurement, Vouliagmeni, 20-22 October 2008, 183-196.
 Zhang, G.-Q., Zhang, G.-Q., Yang, Q.-F., Cheng, S.-Q. and Zhou, T. (2008) Evolution of the Internet and Its Cores. New Journal of Physics, 10, Article ID: 123027.
 CAIDA. Archipelago Measurement Infrastructure.
 Zhao, J. (2008) Does the Average Path Length Grow in the Internet? Information Networking. Towards Ubiquitous Networking and Services. Springer, Berlin Heidelberg.
 Faloutsos, M., Faloutsos, P. and Faloutsos, C. (1999) On Power-Law Relationships of the Internet Topology. ACM SIGCOMM Computer Communication Review, 29, 251-262.
 Chen, Q., Chang, H., Govindan, R., Jamin, S., Shenker, S. and Willinger, W. (2002) The Origin of Power-Laws in Internet Topologies Revisited. 21st Annual Joint Conference of the IEEE Computer and Communications Societies, New York, 23-27 June 2002, 608-617.
 Vázquez, A., Pastor-Satorras, R. and Vespignani, A. (2002) Large-Scale Topological and Dynamical Properties of the Internet. Physical Review E, 65, Article ID: 066130.
 Goh, K.I., Kahng, B. and Kim, D. (2001) Universal Behavior of Load Distribution in Scale-Free Networks. Physical Review Letters, 87, Article ID: 278701.
 Carmi, S., Havlin, S., Kirkpatrick, S., Shavitt, Y. and Shir, E. (2007) A Model of Internet Topology Using k-Shell Decomposition. Proceedings of the National Academy of Sciences, 104, 11150-11154.
 Tauro, S.L., Palmer, C., Siganos, G. and Faloutsos, M. (2001) A Simple Conceptual Model for the Internet Topology. IEEE Global Telecommunications Conference, San Antonio, 25-29 November 2001, Vol. 3, 1667-1671.
 Iannone, F., et al. (2019) CRESCO ENEA HPC Clusters: A Working Example of a Multifabric GPFS Spectrum Scale Layout. Proceedings of the 2019 International Conference on High Performance Computing & Simulation, Dublin, 15-19 July 2019.