Update on AS Path Lengths Over Time

Introduction

The Border Gateway Protocol (BGP) provides a feature called AS path length. It represents the sequence of AS hops that a BGP route follows from a particular AS (the traffic sender) towards the origin AS (the traffic receiver).



One of the common route selection rules in BGP is 'shortest AS path'. That means traffic from AS A will chose the path that leads through the least number of ASes to get to AS B. The more ASes become interconnected, the shorter the AS path tends to become between any two points on the Internet.



Therefore, the average AS path length across the global Internet is one factor that can be used to measure the "interconnectedness" of networks. For more details and a description of the methodology, please refer to Interesting Graph - AS Path Lengths Over Time . Note that the underlying data is taken from the RIPE NCC Routing Information Service (RIS). Other views on the Internet might show slightly different numbers.

Updated Results

The number of ASes connected to the Internet is increasing constantly. One could expect that therefore the length of the AS paths would also increase as the network gets wider. However, this doesn't seem to be the case.

In Figure 1 below, we show the average length of AS paths over time, as seen by the RIS route collectors. You can see the number of AS hops for IPv4 networks is fairly stable at 4.3 hops over the last three years, indicating that the new ASes seem to be contributing to an increased density of the Internet rather than topological expansion.

The number of AS hops for IPv6 networks is lower, but slowly increasing during the last year and a half. This indicates that IPv6 networks might be reaching the same level of interconnectedness as IPv4 networks at some time in the future.

Figure 1: Average AS path lengths (including prepending)

AS prepending (deliberately adding the same AS multiple time in the path) is one factor that can affect the overall average path length, because the same AS would be counted multiple times.

In Figure 2 below, you can see the same graph but this time ignoring AS prepending. That way we counted any AS included sequentially more than once as just one hop. That brings the average number of AS hops for IPv4 networks down to about 3.9. The number of AS hops for IPv6 networks is not decreasing significantly and stays at about 3.5 hops.

Figure 2: Average AS path lengths (excluding prepending)

This graph also shows that, if the artificial layer of prepending is ignored, the average path length over IPv4 would have been decreasing since 2009. This could indicate that, as more IPv4 networks are deployed, the Internet is actually becoming more interconnected. But the increasing usage of AS prepending for traffic engineering purposes counter-balances this factor and prevents it from showing in the statistics.

The green line shows that during the earlier stages of IPv6 deployment (2007-2009), the average path length decreased to the lowest of 3.5 hops, probably indicating that IPv6 was being deployed mostly at the core of the Internet.

The fluctuation in the IPv6 path length values in earlier years can also be explained by the fact that there were much fewer ASes announcing IPv6 prefixes. Therefore single changes in network topology had a higher effect on the overall value for IPv6. As more IPv6 networks were deployed, and the statistical set became more relevant, this effect has decreased.

It is also worth noting that the usage of AS prepending seems to be increasing progressively, even though it is still much rarer in IPv6 than in IPv4, currently contributing to ~12% increase in path length on IPv4, compared to ~5% in IPv6.

Figure 3 shows how this trend developed over the years.

Figure 3: AS path length overhead ratio caused by prepending

The graph shows that both, for IPv4 and IPv6 the amount of the increase in the length of AS paths caused by prepending ASes has been steadily rising. This indicates a general increase in the practice of AS prepending techniques per network.

Conclusions

This update shows that during the last two years, even though the overall number of ASes on the Internet is increasing, the average AS path for IPv4 networks is not getting longer. In fact, it has been decreasing slightly over the last few years. That means the Internet is not becoming wider per se, but more dense, and therefore more interconnected.

For IPv6 networks the paths are generally still shorter than in IPv4 networks by more than .5 hops, but this is increasing slightly. As IPv6 deployment progressively reaches the edges of the Internet it might stabilize and reach the same density level as in IPv4.

The practice of AS prepending seems to be increasing progressively, even though it is still much rarer in IPv6 than in IPv4.

Acknowledgment: This article is entirely based on work done by Vasco Asturiano, software engineer at the RIPE NCC.