mrinfo

Thu, 05/06/2010 - 12:57 by Benoit Donnet • Categories:

Internet Topology Discovery Using mrinfo

The Internet Group Management Protocol (IGMP - RFC1112) was initially designed to allow hosts to report their active multicast groups to the multicast router on their LAN. However, IGMP also provides some management tools such as the messages used by mrinfo. In practice, an mrinfo reply provides similar information as a show command on the router's command line interface. Therefore, mrinfo allows us to silently collect useful topological information.

We build a recursive probing scheme in order to scan connected components of networks: mrinfo-rec. Initially, mrinfo-rec is fed with a single IP address corresponding to the first router attached to the mrinfo-rec vantage point. mrinfo-rec probes this router and recursively applies its probing mechanism on all the collected IP addresses. These recursive queries stop at unresponsive routers or when all known routers have been queried.

We developed an intra-domain topology extraction mechanism based on an efficient router-to-AS algorithm. With mrinfo, note that it is possible to distinguish layer-2 switches from point-to-point links.

Compared to traceroute probing, we can also detect physical links that are not used in the normal forwarding plane (such as links with high IGP weight or low local BGP preference).

A new tool, called MERLIN is currently under submission. The source code of MERLIN is available upon request. A description of MERLIN can be found here.

Technical Report

The technical report given here describes in more detail the algorithms and mechanisms we used to perform intra-domain topologies extraction. Take a look at this blog to get an overview of the most recent Internet topology discovery techniques.

Intra-Domain Topologies

Here, we provide a set of intra-domain topologies extracted from the mrinfo-rec using our router-to-AS mapping described in the PAM 2010 paper.

We consider three types of ISPs:

  • Tier-1: Level-3 (AS3356), Sprint (AS1239), Global Crossing (AS3549), Alternet (AS701), NTTC-Gin (AS2914). Those topologies can be downloaded here.
  • Transit: Transit: Telecom Italia (AS3269), IUnet (AS1267), TDC (AS3292), DFN-IPX-Win (AS680), JanetUK (AS785). Those topologies might be downloaded here.
  • Stub: Stub: Wisconsin University (AS59), UNINETT (AS224), CiscoSystemsEU (AS109), GARRItalian (AS137). Those topologies might be downloaded here.

The choice of those ASes has been based on their frequency of apparition in the whole mrinfo dataset, their dimensions (#nodes, #edges), and their number of connex parts. Note that we have not discarded small non
connected components.

For each AS, we provide various formats:
Graphviz :

  • .dot
  • Pajek: .NET
  • NS-2: .tcl
  • Various: .ntf,.Ge,.net,...

Graphviz and Pajek formats can be used for graph vizualization whereas the NS-2 format allows one to perform simulations. Note that our Graphviz data is the most detailed for vizualization. We provide information such as the DNS names, the nature of nodes (core or ASBR routers, switches with their minimal subnet mask) and adjacent ASes. The caption used in the .dot files is the following: Red nodes are ASBR, diamond nodes are switches, green squares are adjacent ASes.

Dataset

mrinfo raw data

The raw mrinfo dataset used for generating intra-domain topologies might be downloaded here.

MERLIN raw data

The first MERLIN dataset is available here. This dataset was collected in July 2010, from several MERLIN vantage points. A deep description of MERLIN and the collected dataset can be found here.

The second MERLIN dataset is available here. It has been collected between November 9th and November 17th 2010. On the contrary to the first dataset, here, we target specific ASes (Tier-1, Transit, and Stub) using a monitor-server architecture. Techniques have been developed to glue together disconnected components.

Software

The code used to extract intra-domain topologies from mrinfo raw data (see the PAM paper for details) is available here . A README file is also included, so that all information for compiling and running the software is provided.

Publications