Rigorous Measurement of the Internet Degree Distribution
Matthieu Latapy, Elie Rotenberg, Christophe Crespelle, Fabien Tarissan
About
This webpage is supplementary material to our Internet Topology Measurement work. It provides the source of our tools and datasets, and detailed description of how to use them, as well as other useful related information.
Abstract
The degree distribution of the internet, i.e. the fraction of routers with k links for any k, is its most studied property. It has a crucial influence on network robustness, spreading phenomena, and protocol design. In practice, however, this distribution is observed on partial, biased and erroneous maps. This raises serious concerns about the true knowledge we actually have of this key property. Here, we design and run a drastically new measurement approach for the reliable estimation of the degree distribution of the internet, without resorting to any map. It consists in sampling random core routers and precisely estimating their degree with probes sent from many monitors scattered over the internet. Our measurement shows that the true degree distribution significantly differs from classical assumptions: it is heterogeneous but it decreases sharply, in a way incompatible with a heavy-tailed power law.
Authors
| Matthieu Latapy | Sorbonne Universités, UPMC Univ Paris 06, LIP6 UMR 7606, 4 place Jussieu 75005 Paris |
| Elie Rotenberg | Sorbonne Universités, UPMC Univ Paris 06, LIP6 UMR 7606, 4 place Jussieu 75005 Paris |
| Christophe Crespelle | Université Claude Bernard Lyon 1, DANTE/INRIA, LIP UMR CNRRS 5668, ENS de Lyon, Université de Lyon |
| Fabien Tarissan | Sorbonne Universités, UPMC Univ Paris 06, LIP6 UMR 7606, 4 place Jussieu 75005 Paris |
Summary
udpping implements the UDP Ping measurement primitive.
Description
udpping sends an UDP probe towards each IP address read on the standard input (one per line, in dotted-decimal format). This UDP probe consists in a single UDP packet, with TTL 255, adressed to a specified UDP port, carrying a specified message. udpping waits for a set amount of time (60s), during which it waits for responses (ICMP Destination Unreachable packets). Every time a response is received, the target and the interface it used to respond is printed on the standard output. After this set amount of time, all probes without response are considered lost and dismissed.
Input
The targets, one text dotted IPv4 address per line.
Sample input
Output
For each probe that replied, two text-dotted IPv4 adresses that identify the replying interface and the replying target.
Sample output
Parameters
-v |
verbose mode |
-p port |
port: Integer, target port (defaults to random port) |
-d delay |
delay: Integer, delay in milliseconds between two probes (defaults to 1000) |
-m message |
message: String, content of the UDP probes (defaults to UDP Ping). It is strongly advised to include a contact address in the message so that network administrators can opt-out of your measurements and report issues. |
-h |
display help |
Sample usage
./udpping -v -p 44302 -d 100 -m "Matthieu.Latapy@Lip6.fr" < targets.dat > results.dat
Depending on your system, you may need to use sudo or flag the executable with the setuid bit in order to listen to inbound ICMP packets.
Summary
udpexplore implements the UDP Explore measurement primitive.
Description
udpexplore sends an UDP probes towards random valid IP addresses with increasing TTL (starting from 0), until more than one host sends back an ICMP Time Exceeded message, and displays the observed interfaces for each TTL.
Input
udpexplore accepts no input.
Output
For each probe that was sent, two integers that identify the initial TTL and the iteration of the probe, and two text-dotted IPv4 adresses that identify the destination address and the replying interface, or * if the probe had no response.
Sample output
Parameters
-v |
verbose mode |
-p port |
port: Integer, target port (defaults to random(49152, 65535)) |
-n number |
number: Integer, number of probes sent for each TTL (defaults to 100). |
-d delay |
delay: Integer, delay in milliseconds between two probes (defaults to 1000) |
-t timeout |
timeout: Integer, time in milliseconds between the sending of a probe and its assumed loss if no reply is received (defaults to 1000). |
-m message |
message: String, content of the UDP probes (defaults to admin@localhost). It is strongly advised to include a contact address in the message so that network administrators can opt-out of your measurements and report issues. |
-h |
display help |
Sample usage
./udpexplore -v -p 44302 -n 256 -d 100 -t 1500 -m "Matthieu.Latapy@Lip6.fr" > results.dat
Depending on your system, you may need to use sudo or flag the executable with the setuid bit in order to listen to inbound ICMP packets.
Description
Each file contains the aggregated results of running UDP Ping againsts a list of target IPv4 addresses.
Each line in the ASCII-encoded text file has format $monitor $interface $target, where $monitor is a PlanetLab monitor hostname, and $interface and $target are two dotted-decimal IPv4 addresses.
Such a line represents the fact that $monitor has recorded a response to its probe targetted at $target, with origin address $interface.
As explained in the paper, this usually means that the response probe was sent by $target using its interface $interface, therefore allowing us to conclude that $interface belongs to the same IPv4 host than $target.