

|
Internet AS-level topology construction & analysis
|
![]() |
![]() |
|||||||||||||
| Type of Project: |
This project is partly sponsored by the European Commission "Information Society Technologies" (IST), 7th Framework through the Trilogy project and receiving substantial support from NEC´s IT Research Division in St. Augustin. All data displayed on this website has been produced using one of their SX-series vector computers. We would like to thank UCLA´s Internet Research Lab, the RouteView´s Project and RIPE´s RIS for providing the data we are using for our computations! |
||||||||||||
|
UPDATE: Due to the current unavailability of the SX Vector Comupter, we were forced to pause this activity. We are working on a solution right now and will resume our activities once an alternative is in place. Motivation and Project GoalsThe Internet is constantly growing. Not only the number of end user devices such as desktop computers, laptops and cell phones is increasing rapidly but also the number of networks connecting to the Net is growing fast. These growth trends not only challenge the scalability of Internet technology but measuring the Internet, modeling it and understanding its evolution is becoming increasingly complex as well. This project is therefore aiming at two things: continuously analyzing the quality of the Internet´s fabric - the AS-level topology - and providing a simplified representation of it for researchers that need to simulate or evaluate a new technology or algorithm on top of the Internet´s AS-level graph. Many fields in Internet research are dependant on available topology data to perform realistic evaluations. The mere availability of topology data it appears is not the biggest problem to solve any more. Projects such as RouteViews [1], RIPE RIS [2] or DIMES [3] to name just three provide extensive sets of topology data. And although these data sets do not provide a complete view of the Internet´s topology, they approximate the Internet´s underlying graph to an increasingly satisfying manner although they will never be able to claim completeness. While data collection is constantly improving, researchers have to put a lot of effort into extracting the relevant data and transforming that data into something they can make use of. This includes e.g. parsing data such as routing tables, constructing graph representations of the AS-level connectivity and performing time consuming computations to analyze the data. The first contribution of this project is therefore to provide an AS-level topology as an easy to use pair of matrices, one approximating the distances between any given AS pair, the other one representing the next hop matrix to reconstruct AS paths. As part of this effort, we analyze the accuracy of the provided model by comparing the paths in those matrices against a large set of routing table data from [1] and [2]. The matrices themselves are based on data provided by the Internet Research Lab. In addition we classify the ASes as tier-1, tier-2 and tier-3 ASes and make these data sets also available. For details on the construction process and the analysis please refer to [5]. We re-compute all of this once a month and make the updated and a number of older data sets available. A description of the data and used formats can be found here. A second contribution of this project is to constantly monitor the "quality" of the current Internet routing system. Based on the data from [4] we construct the best possible routing topology in terms of AS path length, which is the metric for path "goodness" as seen by BGP. Such a topology would be constructed in the absence of routing policy. We compare this idealized topology against a vast amount of routing table data and draw a number of conclusions from it. This policy-free BGP topology is also provided as a pair of matrices. The data can be retrieved here: If you would like to cite the data source in a publication please use [5] as the reference. Statistics for 2008: | 09 | 10 | 11 | 12 | Statistics for 2009: | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | Cumulative statistics
The next two graphs show some statistics about the distances between ASes in the Internet. The distances shown are those taken from the shortest path matrix, i.e. they are not the ones that can be extracted from routing tables but the ones that a policy-free shortest AS path routing protocol would construct. Again, more elaborate per month statistics can be accessed through the links above.
The next two graphs show the distances we observed in the routing tables used for our analysis. One has to bear in mind that the distances in the routing tables are somewhat different in nature than the distances given above. The distances here are from very specific observation points, many closer to the core than to the edge of the AS-level topology. This results into a slightly biased view. Distances observed from the core of the Internet are on average shorter than when observed from the edges. Furthermore, the comparably small amount of tables used (compared to the total number of ASes) strengthens this trend.
Finally, the last set of graphs show the AS path inflation which we calculate by comparing the paths found in the routing tables against the corresponding paths in the shortest path matrix (think of comparing BGP today against a it's policy-free counterpart). The set of graphs below show the maximum path inflation, the average path inflation and the fration of paths with no observable inflation.
Finally, the last set of graphs show the AS path inflation which we calculate by comparing the paths found in the routing tables against the corresponding paths in the shortest path matrix (think of comparing BGP today against a it's policy-free counterpart). The set of graphs below show the maximum path inflation, the average path inflation and the fration of paths with no observable inflation.
|
|||||||||||||
|
Data files and formats: |
|||||||||||||
|
Links to related projects and further information:
[1] RouteViews Project, http://www.routeviews.org |
|||||||||||||
|
|
|||||||||||||
|
|
|||||||||||||
| For more information on the Trilogy project please visit the project website, consult NEC's own project description or use our contact form. | |||||||||||||
|
|
|||||||||||||
|
| Back
to Projects | Top |
|
![]() |
| © Network Laboratories Heidelberg 2004-2009 | ||