The statistics provided here document the properties of the AS-level topology we constructed. The data we used to construct that graph was collected the first of the month. The data used includes AS-level connectivity data as provided by the Internet Research Lab [4], and routing tables provided by RouteViews and RIPE RIS. The respective graph representations of the topologies can be downloaded here:

For a detailed description of the modeling process consult "Modeling the Internet Routing Topology with a Known Degree of Accuracy - in less han 24h" [5]. Please also use that publication as a reference.

1. Idealized (policy-free) AS-level Topology
The first set of graphs show two properties of an idealized AS-level topology where idealized refers to the fact that the paths constructed are all shortest paths in terms of AS hops. These graphs represent properties of a topology as created by a "policy-free" BGP. In other words, if BGP routers on the Internet would not implement any type of policy by e.g. setting local preference values or filter routes, BGP should be able to find and use the paths in that idealized topology. Therefore, we use it later to compare it against the actual paths that are used on the Internet today [1][2]. This comparison allows us to judge the impact of routing policy on the routing systems quality in terms of AS path length, also referred to path stretch or path inflation. The topology itself was constructed using the AS-level connectivity data provided by the Internet Research Lab (UCLA) [4].
The first graph shows the AS degree distribution, i.e. it shows the cumulative distribution of the ASes ordered by their degree, i.e. by their level of connectivity with other ASes.

The graph below shows a histogram of the path lengths observed in the policy-free graph between all AS pairs. The graph shows the path length distribution of the best possible path in terms of their length. No routing protocol will be able to find shorter paths on the Internet's AS-level graph. It is followed by a table that highlights some characteristics of the data set used and the shortest path matrix constructed.

2. Routing Table Analysis & BGP Routing Quality
As explained before, the above graphs depict the properties of an AS-level inter-domain routing topology without any policy influence. The underlying model is an all-pair shortest path matrix as constructed based on the data provided by the Internet Research Lab (UCLA)[4]. A second set of data that we are using are a large number of routing tables gathered from the RouteViews Project [1] and from RIPE's RIS [2] (we only use routing tables with more than 50.000 entries). These are analyzed to extract some basic properties of the AS-level paths used and compared against the above idealized topology in order to understand the quality of today's routing system based on the AS path length metric. Note that graphs in this section only show the direct comparison of the paths found in the routing tables against the respective paths found in the topology we constructed. The first graph shows the fraction of origin ASes with different numbers of AS paths that lead to them as summed up over the routing tables used. It therefore shows the Internet's path diversity.

The two graphs below show the outcome of a comparison between the policy-free model and the actual AS-level paths as observed in the BGP routing tables used. More precisely it shows the comparison of the path lengths. The graphs are constructed by going through each unique AS path in the routing tables and subtracting the length of the shortest possible path, i.e. it shows the path length difference between the best possible path and the one used in the Internet. The graphs therefore depict the quality of the paths used on the Internet with the path length used as the quality metric. This can be interpreted as the influence of routing policy on the Internet's routing system's quality.

The graph below shows the link overlap between the paths in the policy-free topology and in the BGP routing tables. Link overlap is expressed as the fraction of AS-level links that are common to both paths, i.e. it is the number of link shared by both paths divided by the number of links of the longer path. As an example consider the three paths [AS1-AS2-AS3], [AS1-AS4-AS3] and [AS1-AS2-AS5-AS3]. The first two AS paths have no link overlap (or a link overlap of 0). The first and third AS paths have a link overlap of 0.33 as the only shared link is the link AS1-AS2 and the longest of the two paths contains three links.

The following graph, illustrates the path length distribution of the AS paths in the topology created by a policy-free BGP, i.e. the shortest paths, and the paths observed in the routing tables.

3. A Model of Today's BGP Routing Topology and an Evaluation of its Accuracy
The analysis in sections 1 and 2 are based on a policy-free AS-level topology, i.e. the shortest possible paths in the Internet. The section 2 results clearly show that today, a large fraction of the AS-level routing paths are inflated. In order to provide a model that more accurately reflects today's routing topology we use the link weight information as provided by the Internet Research Lab [4] as documented in [5]. This section analyzes to what degree the model reflects the topology created by BGP today. The model itself can be downloaded here.
The analysis of the model's accuracy is again done by comparing the AS-level paths found in a large amount of routing tables against the paths the model contains, similar to the analysis of the previous section.
The first graph shows the cumulative distribution function of the path length differences between routing table paths and corresponding paths in the routing tables. Two cases are shown termed "best" and "unique". The "best" case depicts the best match against all paths towards an origin AS. In the routing tables can be multiple as shown in section 1 but our simplified model only represents a single one per source/destination pair. In the "unique" case the all paths in the routing table are compared against the single path in the model. But only unique paths, i.e. paths that appear multiple times in the routing table are only compared once.

The following graph illustrates the AS path link overlap for our two cases. It shows the cumulative distribution of the link overlap. The link overlap metric has been explained in section 2.

The graph below shows the path length distribution of the paths found in the routing tables and their counterparts in the policy-free (shortest paths) and weighted matrix (modeled paths).

Our final graph shows the distribution of the path lengths of paths in the model that match the ones found in the routing tables completely, i.e. the ones that have a link overlap of 1.0. Additionally, the path length distribution of the paths found in the routing tables is depicted for direct comparison.

[1] RouteViews Project, http://www.routeviews.org
[2] RIPE RIS, http://www.ripe.net/ris
[3] The DIMES Project, http://www.netdimes.org
[4] UCLA´s Internet Research Lab, Topology Data, http://irl.cs.ucla.edu/topology/
[5] Rolf Winter, "Modeling the Internet Routing Topology with a Known Degree of Accuracy - in less han 24h", ACM/IEEE/SCS Workshop on Principles of Advanced and Distributed Simulation 2009 (PADS 2009)

Note: These pages are auto-generated, in case they contain errors please contact the NEC Network Labs using the contact form
Note further: The here provided data and analysis can only be used for non-commercial purposes. Individuals and businesses that wish to use our data for any commercial, for-profit activity must have prior written consent from the NEC Network Laboratories. The information provided here comes with absolutely NO WARRANTY. There is no guarantee that the information is accurate to any particular degree, has any value, or is fit for any purpose. In particular, we disclaim responsibility for any consequences arising from use of our data.