Download Network Troubleshooting from End-Hosts

6
the right, we see the topology that would be inferred from the routers’ responses.
TTL = 6
TTL = 7
Possible traceroute outcome:
Hop #6
Hop #7
0
S
0
L
1
2
0
Hop #6
A
B
1
1
Hop #7
Hop #8
0
C
0 D
Hop #9
1
0
1 E
2
A0
1
Hop #8
E1
L0
D0
Hop #9
TTL = 8
TTL = 9
Figure 2.1: Missing nodes and links, and false links.
Missing nodes and links. Because routers B and C send no responses, nodes B0
and C0 are not discovered, and links such as (L0 , B0 ) and (B0 , D0 ) are not identified.
False links. L directs the probe with initial TTL 7 to A and the one with initial TTL
8 to B, leading to the mistaken identification of a link between A0 and D0 .
These errors occur even under per-flow load balancing, because traceroute systematically varies the flow identifier of its probes. Traceroute needs a probe identifier, or a way to
match routers’ responses with the probes that elicited them. A router that sends an ICMP
Time Exceeded response encapsulates only the IP header of the packet that it discarded,
plus the first eight octets of data [31, p.5], which, in the case of UDP or ICMP Echo probes,
is equivalent to the transport-layer header. Hence, for UDP, traceroute identifies probes
by varying the destination port; and for ICMP probes, the Sequence Number field (which
in turn varies the Checksum field, which is in the first four octets). Our experiments show
that varying any field in the first four octets of the transport-layer header amounts to
changing the flow identifier for each probe [32]. Thus, traceroute reports false links both
under per-flow and per-packet load balancing.
We provide a publicly-available traceroute tool, called Paris traceroute 1 , which resolves
both problems identified above. First, we discuss how Paris traceroute controls packet
header contents to correctly probe a single route. Measurements comparing Paris traceroute
with classic traceroute show that Internet topologies measured with classic traceroute may
contain “loops”, “cycles”, and “diamonds” that are pure artifacts of traceroute’s behavior
under load balancing. Then, we extend Paris traceroute with the Multipath Detection
Algorithm (MDA), a stochastic probing algorithm that adapts the number of probes to
send on a hop-by-hop basis in order to enumerate all reachable interfaces at each hop. We
use the MDA to measure load balancing in hundreds of thousands of Internet paths. Paris
traceroute is the thesis of Brice Augustin, who I co-advise with Timur Friedman.
1
Paris traceroute is free, open-source software, available from http://www.paris-traceroute.net/.