You are here: Home > Publications > RIPE Labs > Mirjam Kühne > Interesting Graph - AS Path Lengths Over Time
Content by this author

Interesting Graph - AS Path Lengths Over Time

Mirjam Kühne — Oct 2010
Contributors: Vasco Asturiano
One way to determine the denseness of the Internet, or its “interconnectedness”, is to look at the path length between Autonomous Systems (ASes). And are there any differences visible when looking at IPv4 or IPv6 networks? See our findings in this article.

 

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.

AS Path Lengths Including Prepening 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.

AS Path Lengths With AS Prepening Removed 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.

6 Comments

Anonymous says:
25 Oct, 2010 11:14 PM
Out of my scientific interest it would perhaps be nice to use Statistical Process Control (SPC) to do analysis on the data.

SPC is a great way to detect changes over time, and see whether a new situation is (and remains) stable.
Anonymous says:
29 Oct, 2010 05:46 PM
Hi Robin,

Thanks for the suggestion, we're always looking for ways to improve the accuracy of our data analysis. SPC looks interesting, and we'll definitely look into how it can benefit future analysis of this data.
Anonymous says:
29 Oct, 2010 04:03 PM
If you use data from a route server, the thought occurs that you are not seeing the effect of increased peering relationships. I announce my peers' ASNs to neither other peers nor to my transit providers. While peering is a common trend, most eveyone has remained pretty much constant with the number of transit providers they have. An ASN could add a very large number of peers but if it remains comparatively constant with the number of transit providers that it uses, analysis like this one will only see the path length constancy reflected in the transit relationships.
Anonymous says:
01 Nov, 2010 05:28 PM
Hi Ian,

You have a valid point. The results are based on the data set collected by RIS, which indeed like all BGP data collection systems has difficulties in seeing every AS adjacency, especially those that exist but are not announced to the global Internet.

Therefore, it is true that trends in these cases might not be accurately reflected in the above results.
Further research in this area could provide additional insight on the subject.
Jared Mauch says:
13 Dec, 2011 02:29 PM
Any updates on this for the impact of 2011 and speculation of changes as a result of Level3/GBLX merger?
Vasco Asturiano says:
16 Dec, 2011 01:55 PM
Hi Jared,

Thanks for your comment. We haven't yet extended this data into 2011 to see how it compares with the trend of the previous years. But if there is reasonable demand to see the recent variations, we will do so, as well as try to put it under the light of recent events that might have had an effect on it, such as the merger you mentioned.
Add comment

You can add a comment by filling out the form below. Only plain text is possible. Web and email addresses will be transformed into clickable links. Comments are moderated so they won't appear immediately.