[ News ]
5/22/2007: We have been developing Cyclops, a topology dynamics visualization tool which we hope to release soon - stay tuned!
Cyclops was presented at NANOG 40 [ pdf ]
|
 |
Internet Topology Collection |
| This page is maintained by Ricardo Oliveira (rveloso at cs.ucla.edu)
|
|
 |
|
|
|
|
Collecting Internet AS-level topology
Typically, an AS-level topology estimate is derived from BGP routing
tables. Each entry in the
routing table lists the path of ASes used to reach a destination prefix,
and thus each entry implicitly lists AS connectivity information.
Estimates of the Internet AS-level topology are commonly obtained by
taking the union of all AS paths found in BGP routing tables available.
The conventional technique
only captures the AS links currently used in some BGP paths and can potentially miss lots of
backup links not currently in routing tables. We found that many of these backup
AS links can be observed from routing updates over time.
Our goal is to capture the AS-level topology to the furthest
extent using existing resources.
Data sources
We update daily the topology map using the following data sources.
NOTE:
At this time we do not use data collected through traceroute for AS-level topology discovery, due to the inability to accurately converting router paths to AS paths.
We plan to incorporate traceroute data once this problem is solved.
For more information about this problem, please read these papers:
- H. Chang, S. Jamin, and W. Willinger, "Inferring AS-level Internet topology from router-level path traces," in Proceeding of SPIE ITCom 2001, Denver, CO, August 2001
(ps).
- Towards an Accurate AS-Level Traceroute Tool by Z. Morley Mao, Jennifer Rexford, Jia Wang, and Randy Katz, ACM SIGCOMM 2003 (pdf).
- "On Third-party Addresses in Traceroute Paths" authored by Young Hyun, Andre Broido, and kc claffy. Presented at the Passive and Active Measurement Workshop in 2003
(pdf).
File format
For each day, we mantain a file with the AS nodes and AS links observed so far. Each node/link is annotated with the time it was first observed and the time it was last observed.
Furthermore, we also include information about the location of each link in the ASPATH.
Link file format:
AS0 AS1 time_first_seen time_last_seen link_position
Times are in the UNIX timestamp format (seconds since midnight
January 1, 1970 GMT/UTC).
Link position:
0: if it was seen at the beginning of an ASPATH
1: if it was seen at the end of an ASPATH
2: if it was seen at the middle of an ASPATH
3: cannot determine position of link, e.g. links extracted from looking glasses
Example: in ASPATH [7018 3356 11537 52], 7018-3356 is type 0, 3356-11537 is type 2, and 11537-52 is type 1. In ASPATH [701 29], link 701-29 is type 1.
Node file format
AS time_first_seen time_last_seen node_position
Node position:
0: if it was seen at the beginning of an ASPATH
1: if it was seen at the end of an ASPATH
2: if it was seen at the middle of an ASPATH
3: cannot determine position of node
Note: A node with entries of type 1 and no entries of type 2 is considered a stub node, i.e. does not provide transit servide to other nodes.
Download data
Publications
- Ricardo Oliveira, Beichuan Zhang, Lixia Zhang, "Observing the Evolution of Internet AS Topology", to appear in ACM SIGCOMM, Kyoto, Japan, August 2007. (pdf)
- Ricardo Oliveira, Ying-Ju Chi, Ioannis Pefkianakis, Mohit Lad, Lixia Zhang, "Visualizing Internet Topology Dynamics with Cyclops", to appear in ACM SIGCOMM (poster session), Kyoto, Japan, August 2007. (NANOG slides)
- Beichuan Zhang, Raymond Liu, Daniel Massey, Lixia Zhang, "Collecting the
Internet AS-level Topology," ACM SIGCOMM Computer Communication Review
(CCR), special issue on Internet Vital Statistics, January, 2005.
(pdf)
Contact
Please send any comments/questions/bug reports to Ricardo Oliveira (rveloso at cs.ucla.edu) or Beichuan Zhang (bzhang at cs.arizona.edu).
|
|
|
|
|
|
