Interesting Graph - AS Path Lengths Over Time

Please note the article Update on AS Path Length Over Time (September 2012).

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.

Methodology

The following methodology was used to collect the data:

• The source of data is originated at several of the Routing Information Service (RIS) route collectors, located at various places around the globe: RRC1 (London), RRC3 (Amsterdam), RRC5 (Vienna), RRC6 (Tokyo), RRC10 (Milan), RRC11 (New York) and RRC12 (Frankfurt).
• We then took a snapshot of a RIB (local routing table) dump from each RIS route collector, every first day of the month from January 2005 until now.
• Next we extracted the average length of all the AS paths found and separated the IPv4 from the IPv6 routes.
• The minimum AS path length possible for a route is 1, which includes only the origin AS. This is the case when the origin AS has a BGP session directly with our route collector.

Results

On the graphs below we show the evolution of the average AS path length, as seen from these route collectors in the Routing Information System, from 2005 until today, both for IPv4 and IPv6 routes.

Figure 1: Average AS Path Length Including Prepending

For IPv4, the trend shows stability over time of about 4.3 hops for the average AS path length. That trend indicates that, even though the Internet has been growing progressively since 2005 in terms of active AS numbers, it is not becoming wider per se, but more dense, therefore not generating longer paths between ASes.

For IPv6, we see a generally shorter AS path compared to IPv4, with a tendency to decrease over time, starting from the same length as IPv4 back in 2005 to around 20% less (3.5 hops) currently. This decrease indicates that in 2005 IPv6 networks were more sparse and have become more and more interconnected since then. The shorter path length (compared to IPv4) could be explained by the fact that there is a higher concentration of IPv6 networks at the core of the Internet than at its edges, thus lowering the average AS path length.

The fluctuation in the IPv6 path length values can also be explained by the fact that there are far fewer IPv6 than IPv4 prefixes (currently about 3,500 IPv6 prefixes versus 330,000 IPv4 prefixes). Therefore single changes in network topology have a higher effect on the overall value for IPv6.

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 incorrectly interpreted as an AS hop more than one time. In the graph 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.

Figure 2: Average AS Path Length with AS Prepending removed

We observe that by removing prepended ASes, the average path length was reduced by about 6.7% for IPv4 routes, and 2.3% for IPv6 routes. This seems to indicate that traffic engineering using prepending gets applied to IPv4 much more often or in longer sequences than to IPv6.

Conclusion

To conclude, we can observe that as the Internet grows in terms of number of active AS networks, it becomes more dense and interconnected. Therefore the ratio of global interconnectedness remains stable over time. It is interesting to note that IPv6 networks show a recent tendency to have a shorter AS path length, but as IPv6 gets more deployed at the edges of the Internet, it might converge into the same level of interconnections as IPv4.

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