Since 2000, CAIDA has generated AS Core graphs -- Internet Topology Maps also referred to as AS-level Internet Graphs -- in order to visualize the shifting topology of the Internet over time, as can be seen in the historical view.
Presented below is CAIDA's 2013 visualization of both IPv4 and IPv6 Internet topology at the Autonomous System (AS) level.
This visualization represents a macroscopic snapshot of IPv4 and IPv6 Internet topology samples captured in 2013. The plot illustrates both the extensive geographical scope as well as rich interconnectivity of nodes participating in the global Internet routing system.
For the IPv4 map, CAIDA collected data from 58 monitors in 29 countries on 6 continents. Coordinated by our active measurement infrastructure, Archipelago (Ark), the monitors probed paths toward 214 million /24 networks that cover 93.5% of the routable prefixes seen in the Route Views Border Gateway Protocol (BGP) routing tables on 2 January 2013. For the IPv6 map, CAIDA collected data from 26 IPv6-connected Ark monitors located in 18 countries on 4 continents. This subset of monitors probed paths toward 2 million IPv6 addresses, which represent 82.2% of the globally routed IPv6 prefixes seen in Route Views BGP tables on 2 January 2013.
Figure 2. Coordinates of AS in AS core visualization.
We aggregated this IP-level data to construct IPv4 and IPv6 Internet connectivity graphs at the Autonomous System (AS) level. Each AS approximately corresponds to an Internet Service Provider (ISP). We map each observed IP address to the AS responsible for routing traffic to it, i.e., to the origin (end-of-path) AS for the IP prefix representing the best match for this address in BGP routing tables collected from Route Views.
The position of each AS node is plotted in polar coordinates (radius, angle) calculated as indicated in Figure 2, on the right.
In order to improve our AS Core visualization we have made two major refinements to how we create the graph, including how we rank individual ASes.
- (1) First, we now rank ASes based on their transit degree rather then their outdegree.
- (2) Second, we now infer links across Internet eXchange (IX) point address space, rather than considering the IX itself a node to which various ISPs attach.
(1) Change in Ranking Metric From Outdegree to Transit Degree
To place them on the graph, we originally sorted ASes by outdegree, which is the number of outbound links from an AS as observed in AS paths. In Figure 3, ASes 2, 3, 4, and 5 have an outdegree of 0, since nothing follows them in any path. ASes 6 and 7 have an outdegree of 2, while AS 1 has an outdegree of 3 only due to the monitor it hosts. Using transit degree instead drops AS 1's degree to 0, and differentiates 6, which provides transit for three ASes, from 7, which provides transit for only two.
(2) Inferring links across IX Address Space
Our second substantial methodology change was that we infer links across IXes when the IX's address space appears in the traceroute. IXes provide infrastructure fabrics over which other ASes peer. Although the IX may have their own AS and address space, links that cross an IX's address space are actually peering links directly between the ASes connected to the IX, rather than to the IX itself. But raw traceroute data can include IP addresses used by an IX to facilitate this direct peering across the IX. Sometimes an AS might announce the IX's address space, in which case a simplistic mapping of these raw IP addresses to ASes will introduce false peering links between the AS announcing the IX's address space and ASes peering at the IX, as well as hide actual peering links between pairs of ASes on either side of the IX. To recover the true peering connectivity, we infer links across IX address space that is self-identified by the IX in PeeringDB. This new method does not always result in an increase in the degrees of ASes announcing IX address space. In figure 4, AS 3 already has a direct link to AS 2 at some other location, so inferring peering across the IX results in a loss of the link to the IX's AS, and no additional neighbors, resulting in a drop in degree for AS 3.
Quantifying the effects of these changes on IPv4 AS degree computations
We use box plots (in figures 5, 6, 8, 9, 11, 12, 13, and 14) to show the impact of the two changes in methodology on the resulting data. In each figure, we group ASes into bins of at least 25 with a given outdegree range; each bin is represented by one box-and-whisker plot, which delineates the range of change in degree when moving from an old method to a new method. The top of the box represents the 3rd quartile (75%), the line in the middle of the box is the 2nd quartile (50%), and the bottom of the box is the 1st quartile (25%). The whiskers represent 5% and 95%. We compute the percentages for this distribution as follows:
Figure 5 shows the change in AS degrees when switching from the use of outdegree to transit degree for IPv4 ASes. More then 75% of ASes had a larger transit degree then outdegree, although the relative change decreased as the outdegree increased. For ASes with outdegree larger then 20, an increasing fraction (but never above 25% of ASes in a bin) had transit degrees smaller than their outdegrees.
Figure 6 shows the percentage difference in transit degree when removing links connected to ASes announcing IPv4 IX address space, and adding AS links inferred across IX address space. The effect on transit degrees is subtle; ASes will both potentially lose links to IX address space and potentially gain new links across the IX. In our data, bridging inferences across the IX address space resulted in a loss of 5% of the existing IPv4 links, but yielded an additional 7,000 links (12% of the original), for a net 7% increase in links. Half of the ASes saw less than 10% change in their transit degree. ASes with moderate (between 100 and 360) transit degrees using the old method saw the greatest relative change to their transit degree. Among the top 50 ASes by the old method, 4 had their transit degree drop to less then 10% their old value (these 4 were IXes or announcing IX address space).
Figure 7 focuses on the top ten ASes, ranked by outdegree, transit degree, or transit degree given inferred links in the IPv4 graph. Hurricane Electric (AS 6639) was the only AS whose outdegree was significantly larger then its transit degree, probably due to the two Ark monitors they host. Hurricane Electric (AS 6639) also saw the most new links inferred across the IX address space, which increased its degree from 2,053 to 2,715 (32%). ReTN.net (AS 9002) saw its transit degree increase from 988 to 1,176 (19%). Most of these ASes had transit degrees within 1% of their outdegrees.
Effects on IPv6
Figure 8 shows box plots of the percentage differences between degree and transit degree for ASes in the IPv6 graph. IPv6 sees an effect similar to the IPv4 graph: more then 75% of ASes had a larger transit degree then outdegree, although the relative change decreased as the outdegree increased. Unlike in IPv4, 5% of ASes with outdegrees larger than 5 had their transit degree drop almost to 0, typically in cases where they were hosting an Ark monitor (which increased their observed outdegree but would not affect transit degree). These ASes had a similar drop in the IPv4 graph, but the smaller size of the IPv6 graph increases their visibility.
Figure 9 shows that 75% of ASes had their transit degree increase when links were inferred across IX address space. For the top 50 ASes by the old method, 4 of them (3 IXes and an AS announcing IX address space) saw their degrees drop to almost zero. Half of all ASes had their degree change less than 25%.
Of the top ten ASes by transit degree in the graph where we treated IXes as nodes, Hurricane Electric's transit degree increased by 36% when we inferred links across the IX address space. As expected, the Amsterdam Internet Exchange (AS 1200) and the German Internet Exchange (AS 6695) saw the largest drop in transit degree when we removed links directly to IXes. Although Bharti Airtel (AS 9498) is not an IX, it was announcing an an IX's address space and so its transit degree dropped 88.4%. NORDUnet (AS 2603) and Next Layer Telecommunication (AS 1764) both joined the top 10, with transit degree increases of 155.8% and 269.2%, respectively. The larger role of IXes in the less mature IPv6 topology is reflected in the stronger effect their removal has on the degree-based AS ranking.
Summary of effects of two changes: Switching to Transit Degree and Inferring across IX's Address Space
In both IPv4 and IPv6, the most connected ASes experienced limited effects due to the change from outdegree to transit degree. In most bins, more than 75% of ASes increased their degree. IPv6's top bin (top 25 ASes by outdegree) was the exception, with over half decreasing their degree, due to the many IX ASes represented in this bin. In both IPv4 and IPv6, Hurricane Electric (AS 6939) saw its transit degree increase by over 30% when links were inferred across IX address space. Most other highly connected ASes in IP4 saw little change due to the IX node removal, but the IPv6 AS graph's top 10 saw significant change due to the larger role of IXes in the less mature IPv6 topology.
As in previous years, our IPv6 graph saw greater relative growth then IPv4, with 26% more ASes and 17% more AS links. (In IPv4 the growth was 11% more ASes and 6% links). These growth numbers hide a great deal of churn. Figure 14 shows that for the ~2K IPv6 ASes with degrees less then 4, about the same number of ASes increased as those that decreased their degree. The half of ASes represented by the whiskers outside the boxes increased or decreased their degree by over 30% between 2012 and 2013. Over the last year our IPv6 graph lost 295 (15%) ASes and almost 3K (38%) links, but gained 790 (41%) new ASes and over 4K (55%) new links. Our IPv4 graph was more stable, it lost ~2K (7%) ASes and ~38K (37%) links, but gained ~5K (18%) new ASes and ~43K (42%) new links. The net change in number of ASes was 495 (+26%) in our IPv6 graph and ~3K (+11%) in our IPv4 graph.
In both our IPv4 and IPv6 graphs, small and large (degree less than 5 or greater than 100) ASes split evenly between those that increased and decreased their degrees from 2012 to 2013. Drops in the IPv4 graph tended to be larger than increases; and increases in the IPv6 graph tended to be larger than drops. This reflects the faster growth of the IPv6 topology, especially for larger transit ASes.
Figure 15 plots the top 10 ASes by transit degree in either 2012 or 2013, which includes a set of 11 ASes in IPv6 and 12 ASes in IPv4. Half of these 12 most highly connected ASes in IPv4 increased and half decreased their transit degree from 2012, with a range from +234% for Hurricane Electric (AS 6939) to -92% for WV Fiber (AS 19151). Ten of the 11 top IPv6 ASes increased their degree since 2012. One AS, Init7's (AS 13030), had their transit degree drop from 207 to 91 (56%), but Hurricane Electric (AS 3356) and NTT (AS 2914) grew their transit degree over 30% to 965 and 310 respectively.
Although the set of ASes with the largest transit degrees in both IPv6 and IPv4 are increasingly converging, major differences remain. Hurricane Electric (AS 6939), the AS with the largest transit degree in IPv6, has a degree 192% larger than Level 3 (AS 3356), the second largest IPv6 AS by degree. But despite Hurricane's huge increase in IPv4 transit degree between 2012 and 2013, Level 3 (AS 3356) still has a transit degree 159% larger than Hurricane Electric's (AS 6939), and only 4% larger than Cogent (AS 174), the second largest AS by transit degree in IPv4.
This AS core visualization addresses one of CAIDA's topology mapping project goals is to develop techniques to illustrate structural relationships and depict critical components of the Internet infrastructure. These IPv4 and IPv6 graphs show the relative growth of the two Internet topologies, and in particular the steady continued growth of the IPv6 topology. Although both IPv4 and IPv6 topologies experienced a lot of churn, the net change in number of ASes was 3,290 (10.7%) in our IPv4 graph and 495 (25.7%) in our IPv6 graph.
In order to improve our AS Core visualization over previous years, this year we made two major refinements to our graphing methodology, including how we rank individual ASes. First, we now rank ASes based on their transit degree rather then their outdegree. Second, we now infer links across Internet eXchange (IX) point address space, rather than considering the IX itself a node to which various ISPs attach. For more information about the topology mapping project, see: http://www.caida.org/projects/macroscopic/
For details on a more sophisticated methodology for ranking AS interconnectivity, based on inferring AS relationships from BGP data, see CAIDA's Introduction to Relationship-based AS Ranking at http://www.caida.org/data/as-relationships/.
If you would like to try out a demo of the CAIDA tools used to construct this graph, please see http://www.caida.org/projects/internetatlas/gallery/ascore/demo.xml.
Topology Mapping Analysis Team: Brad Huffaker, kc claffy
Software Development: Young Hyun, Matthew Luckie
Poster Design: Justin Cheng