Logo

Macroscopic Internet Topology Data Kit (ITDK)

Macroscopic Internet Topology Data Kit (ITDK)

ITDK 2021-03

This page describes the historical ITDK release 2021-03, which consists of

  • an IPv4 router-level topology,
  • router-to-AS assignments,
  • geographic location of each router, and
  • DNS lookups of all observed IP addresses.

This ITDK was produced from traceroutes conducted on the Archipelago (Ark) measurement infrastructure. We used a subset of the IPv4 Routed /24 Topology Dataset, which contains traceroutes to randomly-chosen destinations in each routed /24 BGP prefix.

We used traces collected Feb 16 to Mar 2, 2021 on 111 Ark monitors located in 43 countries.

Latest release

Prior Releases

Router-Level Topologies

The IPv4 router-level topology is derived from aliases resolved with MIDAR and iffinder, which yield the highest confidence aliases with very low false positives. The router-level topology is provided in two files, one giving the nodes and another giving the links. There are additional files that assign ASes to each node, provide the geographic location of each node, and provide the DNS name of each observed interface.

Nodes File

The nodes file lists the set of interfaces that were inferred to be on each router.

File format: node <node_id>:   <i1>   <i2>   ...   <in>

Each line indicates that a node node_id has interfaces i1 to in. Interface addresses in 224.0.0.0/3 (IANA reserved space for multicast) are not real addresses. They were artificially generated to identify potentially unique non-responding interfaces in traceroute paths.

NOTE: In ITDK release 2013-04 and earlier, we used addresses in 0.0.0.0/8 instead of 224.0.0.0/3 for these non-real addresses.

Links File

The links file lists the set of routers and router interfaces that were inferred to be sharing each link. Note that these are IP layer links, not physical cables or graph edges. More than two nodes can share the same IP link if the nodes are all connected to the same layer 2 switch (POS, ATM, Ethernet, etc).

File format: link <link_id>:   <N1>:i1   <N2>:i2   [<N3>:[i3]]   ..   [<Nm>:[im]]

Each line indicates that a link link_id connects nodes N1 to Nm. If it is known which router interface is connected to the link, then the interface address is given after the node ID separated by a colon (e.g., "N1:1.2.3.4"); otherwise, only the node ID is given (e.g., "N1").

By joining the node and link data, one can obtain the known and inferred interfaces of each router. Known interfaces actually appeared in some traceroute path. Inferred interfaces arise when we know that some router N1 connects to a known interface i2 of another router N2, but we never saw an actual interface on the former router. The interfaces on an IP link are typically assigned IP addresses from the same prefix, so we assume that router N1 must have an inferred interface from the same prefix as i2.

Node-AS File

The node-AS file assigns an AS to each node found in the nodes file. We use our final bdrmapIT and Hoiho assignment heuristic to infer the owner AS of each node.

Addresses that belong to the address space of an Internet exchange point (as self-identified in PeeringDB: https://www.peeringdb.com/) are excluded from the AS analysis, as we don't consider them to be part of the AS-level topology.

File format: node.AS   <node_id>   <AS>   <method>

Each line indicates that the node node_id is owned/operated by the given AS, as inferred with the given method. There are three inference methods:

refinement
AS inferred based on the ASes of surrounding routers
origins
AS inferred based on the AS announcing the longest matching prefixes for the router interface IP addresses
unknown
routers that bdrmapIT could not infer an AS for
lasthop
bdrmapIT assignment by the ASN of the last hop in the path
as-hints
bdrmapIT assignment using ASN hints in the hostname extracted with Hoiho rules

Hostnames File

The hostnames file contains the hostname for every IP address in the router-level topology for which a successful reverse DNS lookup could be found.

File format: <timestamp>   <IP_address>   <hostname>

Node-Geolocation File

The node-geolocation file contains the geographic location for each node in the nodes file. We use the Hoiho, IXP, and MaxMind's GeoLite City database in that order.

File format: node.geo   <node_id>:   <continent>   <country>   <region>   <city>   <latitude>   <longitude>   <population>   <method>

hoiho
geolocated by Hoiho from DNS names
ix
geolocated from IXP's location of node's IP address
maxmind
geolocated from node's addresses in Maxmind

Future Work

We are in the process of expanding the ITDK with additional data that will combine router and AS-level views of the Internet topology. The AS link dataset will contain the set of AS links as inferred from combining the AS assignment and node datasets. The AS relationship dataset will contain the business relationship associated with each AS link in the AS link dataset. These datasets will be available in the coming months.

Data Availability

  • Data older than one year is available as a public dataset. You can obtain access using this form.
  • The most recent one year of data is available for use by academic researchers and US government agencies. This data is also available for corporate entities (including corporate researchers) who participate in CAIDA's membership program. Please, complete and submit the online form to request access to the most recent data. It usually takes about two to three business days to process your request. Upon approval you will receive an email with instructions on how to download the data you requested. If you have any questions or problems using this form, please contact data-info@caida.org.

Acceptable Use Agreement for the public data

Please read the terms of the CAIDA Acceptable Use Agreement (AUA) for Publicy Accessible Datasets below:

When referencing this data (as required by the AUA), please use:

The CAIDA Macroscopic Internet Topology Data Kit - <release dates >,
https://www.caida.org/catalog/datasets/internet-topology-data-kit

You are required to report your publications using this dataset to CAIDA.

Request Data Access

  • Access the publicly available CAIDA Ark IPv4 Internet Topology Data Kits Dataset (and other topology data)
  • Request Access to the restricted CAIDA Ark IPv4 Internet Topology Data Kits Dataset

Note that two historical ITDK releases made in 2002 and 2003 are also available as public datasets. These datasets should be used with caution, as they were constructed using completely different procedures and using topology data collected on the now decommissioned skitter measurement infrastructure.

Internet Topology Data Kit Process

Below we describe the various steps involved in producing the datasets that are part of the ITDK.

Internet Topology Data Kit Process Alias resolution
 

For alias resolution, we rely on several CAIDA tools: iffinder and MIDAR (recent tech report). MIDAR (Monotonic ID-based Alias Resolution, a tool we hope to release soon) expands on the IP velocity techniques of RadarGun. We use the traceroute dataset as input to MIDAR and iffinder to infer which interfaces belong to the same router, and the set of two or more routers on the same IP link (a construct that represents either a point-to-point link, or LAN or cloud with multiple attached IP addresses). We use iffinder, and MIDAR to construct IPv4 topologies.

DNS hostnames
 

We have an in-house bulk DNS lookup service called HostDB that can look up millions of addresses per day. We look up all intermediate addresses and responding destinations seen in the Topology Dataset. Each ITDK contains a list of the successful lookups for each IP address found in the nodes dataset.

BGP
 

To assign IP addresses to ASes, we used a publicly available BGP dump provided by Routeviews. BGP (Border Gateway Protocol) is the protocol for exchanging interdomain routing information among ASes in the Internet. A single origin AS typically announces ("originates") each routable prefix via BGP. We perform IP-to-AS mapping by assigning an IP address to the origin AS of the longest matching prefix for that IP address in the BGP tables.

AS relationships
 

We used the BGP data to annotate each interdomain link with one of three simplified business relationships -- customer-provider (the customer pays the provider), settlement-free peer (typically no money is exchanged), and sibling (both ASes belong to the same organization) -- using the classification algorithm by Luckie et al., resulting in what we call the AS relationship dataset.

AS assignment
 

bdrmapIT combines the AS inference heuristics found in both bdrmap and MAP-IT. By synthesis of these two techniques, bdrmapIT is designed to accurately identify interdomain links in a traceroute dataset using a graph refinement strategy. Our algorithm proceeds as follows:

  1. The first step (Graph Construction) processes the traceroutes, extracting paths and generating a prioritized graph of the interfaces. This interface graph is used by our heuristics in Step 3 to infer router ownership and interdomain links.
  2. In the second step (Graph Initialization), we use the paths and alias resolution to annotate routers that always appear at the end of a traceroute. We process these first since we are unable to refine these inferences later.
  3. Finally, in the third step (Graph Refinement), we use the graph refinement loop to annotate the remaining routers and interfaces using the prioritized interface graph and the path data. After each iteration of the loop we refine the inferences, enabling additional accuracy.

Hoiho uses inital router to AS assignment inferences from bdrmapIT combined with DNS hostnames to create a set of rules which can extract AS annotations recorded by network operators in hostnames. Those rules are then used to add an additional refinement to bdrmapIT's initial assignment. For further details, please see the papers bdrmap: Inference of Borders Between IP Networks, MAP-IT: Multipass Accurate Passive Inferences from Traceroute, and Learning to Extract and Use ASNs in Hostnames.

Geolocation
 

We use a combination of publicly known Internet eXchange (IX) point information, Hoiho hostname mapping, and MaxMind's free GeoLite City database to provide the geographic location (at city granularity) of routers in the router-level graph.

We generated an internal IX database containing information combined from: BGP Looking glass database, Wikipedia's list of Internet Exchange Points, PeeringDB, and PCH's IX database. The geographic city names are then mapped to Geoname's locations. This data provides a set of geographic locations and prefixes for each IX. A router is mapped to an IX's location if the router contains at least one interface from the IX's address space and the IX is located in a single city.

We then collect the hostnames for interfaces on routers that are not geolocated to an IX. These hostnames are then mapped to geographic locations using Hoiho's heuristics.

All remaining routers are geolocated using MaxMind Lite. Because this database maps individual IP addresses to locations, we take the following steps to find the location of each router (which by definition has multiple interfaces). We first map each interface on a router to a location. If all interfaces map to the same location, then we assign that location to the router; otherwise, we do not assign any location to the router (that is, the router does not appear in the geolocation file).

For further details, please see the papers Learning to Extract Geographic Information from Internet Router Hostnames.

Related Objects

See https://catalog.caida.org/dataset/ark_itdk to explore related objects to this document in the CAIDA Resource Catalog.
Published
Last Modified