Nicolas Mesa

Posted on Oct 25, 2018 • Originally published at blog.nicolasmesa.co on Sep 17, 2018

How Does Traceroute Work

#commandline #linux #networks #udp

Cross-posted from my personal blog https://blog.nicolasmesa.co.

In this post, we take a look at how the traceroute command works. traceroute is a utility command that prints the route (or hops) that a packet takes to reach another host. We start with an example of traceroute. Then we go through what happened behind the scenes. Finally, we run the traceroute command one more time while sniffing the traffic with tcpdump.

Traceroute example

Let’s look at an example:

nmesa@desktop-nicolas:~$ ping -c 1 google.com
PING google.com (172.217.14.206) 56(84) bytes of data.
64 bytes from sea30s01-in-f14.1e100.net. (172.217.14.206): icmp_seq=1 ttl=56 time=8.02 ms

--- google.com ping statistics ---
1 packets transmitted, 1 received, 0% packet loss, time 0ms
rtt min/avg/max/mdev = 8.028/8.028/8.028/0.000 ms

nmesa@desktop-nicolas:~$ traceroute -q 1 google.com
traceroute to google.com (172.217.14.206), 64 hops max
  1 192.168.0.1 0.247ms
  2 67.218.102.107 11.667ms
  3 174.127.182.56 10.964ms
  4 174.127.141.190 12.403ms
  5 72.14.198.216 11.208ms
  6 74.125.243.177 13.321ms
  7 209.85.254.237 11.483ms
  8 172.217.14.206 12.060m

First, we issue a ping to google.com to find out its IP address (172.217.14.206). Then, we run a traceroute command to google.com (the -q 1 is to have traceroute only send one packet instead of 3). In this example, we see that the packets have to traverse 8 hops to reach google.com’s host.

IP Header

So, how does this work under the hood? To understand this, first, we need to talk about the Internet Protocol (IP). IP is responsible for delivering packets from the source host to the destination. Every IP packet has an IP header, which is used by routers to make routing decisions. The IP header has a lot of information, but we’re going to focus on 3 fields:

Source IP (src): The IP address of the host that sent the packet (we’re going to ignore NATs for this discussion). In our case, it’s 192.168.0.250.
Destination IP (dst): IP address of the target host. In our case, it’s google.com’s IP address: 172.217.14.206.
Time to Live field (TTL): This field doesn’t contain a time, as the name suggests. It has the maximum number of hops that this packet should traverse before reaching its destination. If the maximum number of hops is reached, the packet is dropped, and an error message is sent to the sender. This field helps to prevent routing loops where a packet stays in a loop forever.

When a router receives an IP packet, it subtracts 1 from TTL field to determine if it should forward the packet or not. If the new TTL value is greater than 0, the router forwards the packet with the updated TTL value. If the new TTL is equal to 0, the router discards the packet and sends an ICMP error message to the source to let it know that the packet’s time exceeded in-transit (the TTL wasn’t large enough for the packet to reach the destination).

Traceroute introduction

traceroute takes advantage of the TTL field and the ICMP error message returned to trace the route to the target host. First, it sends a packet (usually UDP if in Linux) with TTL = 1. When this packet reaches our router, the router decrements the TTL and notices that the TTL is equal to 0. Our router drops the packet and sends back an ICMP error message. traceroute uses the source IP address in the ICMP packet as the value of the first hop. traceroute sends another datagram with TTL = 2. Our router gets the packet, decrements the TTL and forwards the packet since the TTL is greater than 0. The second hop receives the packet, decrements the TTL and notices that it is equal to 0. The router drops the packet and sends back an ICMP error message which traceroute uses to get the value for the second hop. traceroute keeps incrementing the TTL by one until it actually reaches the server. The server responds typically with an ICMP error stating that the UDP port is unreachable. At that point, traceroute is done.

Capturing the traceroute traffic

Let’s use tcpdump to capture this exchange. First, we open a new terminal window and execute the following tcpdump command:

nmesa@desktop-nicolas:~$ sudo tcpdump -vv -nn -i eth0 "(udp and ip[8] < 10) or icmp"
tcpdump: listening on eth0, link-type EN10MB (Ethernet), capture size 262144 bytes

Let’s go over the arguments:

-vv: To make the output verbose. We need this to be able to see the packet’s TTL value.
-nn: We don’t want tcpdump to resolve the IP addresses to hostnames or ports to service names.
-i eth0: The interface to listen on.
"(udp and ip[8] < 10) or icmp": Filter to display either UDP packets with a TTL value of less than 10 (adjust this number to meet your needs) or ICMP packets (to see the errors coming back from the routers).
- The ip[8] notation means the 8th byte (starting from 0) of the IP Header.

In another terminal window, we run the traceroute command:

nmesa@desktop-nicolas:~$ traceroute -q 1 google.com
traceroute to google.com (172.217.14.206), 64 hops max
  1 192.168.0.1 0.247ms
  2 67.218.102.107 11.667ms
  3 174.127.182.56 10.964ms
  4 174.127.141.190 12.403ms
  5 72.14.198.216 11.208ms
  6 74.125.243.177 13.321ms
  7 209.85.254.237 11.483ms
  8 172.217.14.206 12.060m

If we go back to the tcpdump window, we see something like this:

nmesa@desktop-nicolas:~$ sudo tcpdump -vv -nn -i eth0 "(udp and ip[8] < 10) or icmp"
tcpdump: listening on eth0, link-type EN10MB (Ethernet), capture size 262144 bytes
21:48:11.140870 IP (tos 0x0, ttl 1, id 34332, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33434: [bad udp cksum 0x7d6c -> 0x0386!] UDP, length 9
21:48:11.141090 IP (tos 0xc0, ttl 64, id 59363, offset 0, flags [none], proto ICMP (1), length 65)
    192.168.0.1 > 192.168.0.250: ICMP time exceeded in-transit, length 45
        IP (tos 0x0, ttl 1, id 34332, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33434: [udp sum ok] UDP, length 9
21:48:11.141236 IP (tos 0x0, ttl 2, id 34333, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33435: [bad udp cksum 0x7d6c -> 0x0385!] UDP, length 9
21:48:11.152912 IP (tos 0x0, ttl 254, id 0, offset 0, flags [none], proto ICMP (1), length 56)
    67.218.102.107 > 192.168.0.250: ICMP time exceeded in-transit, length 36
        IP (tos 0x0, ttl 1, id 34333, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33435: UDP, length 9
21:48:11.152943 IP (tos 0x0, ttl 3, id 34335, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33436: [bad udp cksum 0x7d6c -> 0x0384!] UDP, length 9
21:48:11.163898 IP (tos 0x0, ttl 253, id 26888, offset 0, flags [none], proto ICMP (1), length 96)
    174.127.182.56 > 192.168.0.250: ICMP time exceeded in-transit, length 76
        IP (tos 0x0, ttl 1, id 34335, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33436: [udp sum ok] UDP, length 9
21:48:11.163934 IP (tos 0x0, ttl 4, id 34336, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33437: [bad udp cksum 0x7d6c -> 0x0383!] UDP, length 9
21:48:11.176324 IP (tos 0x0, ttl 252, id 59054, offset 0, flags [none], proto ICMP (1), length 96)
    174.127.141.190 > 192.168.0.250: ICMP time exceeded in-transit, length 76
        IP (tos 0x0, ttl 1, id 34336, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33437: [udp sum ok] UDP, length 9
21:48:11.176368 IP (tos 0x0, ttl 5, id 34339, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33438: [bad udp cksum 0x7d6c -> 0x0382!] UDP, length 9
21:48:11.187557 IP (tos 0x0, ttl 251, id 0, offset 0, flags [none], proto ICMP (1), length 56)
    72.14.198.216 > 192.168.0.250: ICMP time exceeded in-transit, length 36
        IP (tos 0x0, ttl 1, id 34339, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33438: UDP, length 9
21:48:11.187622 IP (tos 0x0, ttl 6, id 34340, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33439: [bad udp cksum 0x7d6c -> 0x0381!] UDP, length 9
21:48:11.200912 IP (tos 0x0, ttl 249, id 45260, offset 0, flags [none], proto ICMP (1), length 96)
    74.125.243.177 > 192.168.0.250: ICMP time exceeded in-transit, length 76
        IP (tos 0x80, ttl 1, id 34340, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33439: [udp sum ok] UDP, length 9
21:48:11.201012 IP (tos 0x0, ttl 7, id 34341, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33440: [bad udp cksum 0x7d6c -> 0x0380!] UDP, length 9
21:48:11.212452 IP (tos 0x0, ttl 248, id 36434, offset 0, flags [none], proto ICMP (1), length 96)
    209.85.254.237 > 192.168.0.250: ICMP time exceeded in-transit, length 76
        IP (tos 0x80, ttl 1, id 34341, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33440: [udp sum ok] UDP, length 9
21:48:11.212596 IP (tos 0x0, ttl 8, id 34342, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33441: [bad udp cksum 0x7d6c -> 0x037f!] UDP, length 9
21:48:11.224616 IP (tos 0x0, ttl 56, id 0, offset 0, flags [none], proto ICMP (1), length 56)
    172.217.14.206 > 192.168.0.250: ICMP 172.217.14.206 udp port 33441 unreachable, length 36
        IP (tos 0x80, ttl 1, id 34342, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33441: UDP, length 9

Traceroute traffic deep dive

Let’s break this down. Line number 3 in the traceroute command shows that the first hop is 192.168.0.1 (my router). Take a look at the following line:

21:48:11.140870 IP (tos 0x0, ttl 1, id 34332, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33434: [bad udp cksum 0x7d6c -> 0x0386!] UDP, length 9
21:48:11.141090 IP (tos 0xc0, ttl 64, id 59363, offset 0, flags [none], proto ICMP (1), length 65)
    192.168.0.1 > 192.168.0.250: ICMP time exceeded in-transit, length 45
        IP (tos 0x0, ttl 1, id 34332, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33434: [udp sum ok] UDP, length 9

Note the ttl 1 value. We can also see the time exceeded in-transit message coming back with source IP 192.168.0.1. That corresponds with the first hop!

The second hop in the traceroute command is 67.218.102.107 (line 4). This also corresponds to the following lines:

21:48:11.141236 IP (tos 0x0, ttl 2, id 34333, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33435: [bad udp cksum 0x7d6c -> 0x0385!] UDP, length 9
21:48:11.152912 IP (tos 0x0, ttl 254, id 0, offset 0, flags [none], proto ICMP (1), length 56)
    67.218.102.107 > 192.168.0.250: ICMP time exceeded in-transit, length 36
        IP (tos 0x0, ttl 1, id 34333, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33435: UDP, length 9

Here we see the ttl 2 value. Note that the source IP (192.168.0.250) and destination IP (172.217.14.206) haven’t changed (the target port increases by 1 every message, but this doesn’t affect our discussion). The ICMP error message has source IP 67.218.102.107 which also aligns with what we see in our traceroute command! Let’s go all the way to the end!

The last hop in the traceroute command is 172.217.14.206, one of the IP addresses of google.com. Let’s examine our tcpdump output for that hop.

21:48:11.212596 IP (tos 0x0, ttl 8, id 34342, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33441: [bad udp cksum 0x7d6c -> 0x037f!] UDP, length 9
21:48:11.224616 IP (tos 0x0, ttl 56, id 0, offset 0, flags [none], proto ICMP (1), length 56)
    172.217.14.206 > 192.168.0.250: ICMP 172.217.14.206 udp port 33441 unreachable, length 36
        IP (tos 0x80, ttl 1, id 34342, offset 0, flags [DF], proto UDP (17), length 37)
    192.168.0.250.50475 > 172.217.14.206.33441: UDP, length 9

We now see a ttl 8 value. Note that there isn’t a time exceeded in-transit ICMP error message. Instead, the server responded with an ICMP message saying udp port 33441 unreachable. This error is coming from the host since it is the only one who knows if that port is open or not. This message tells traceroute that the last packet it sent reached the host and there are no more hops in the way.

Conclusion

We covered how traceroute works under the hood. We saw how this command uses the TTL field to control the number of hops that the packet travels before it is dropped and an error message is sent back to us. We also saw that the source IP address of the ICMP error message is also the IP address of the hop that dropped the packet. Some routers are configured to drop the packet silently and not send an ICMP error message (this shows up as a * entry in the traceroute output).

One thing we didn’t talk about is the IP header checksum. The checksum is used to verify the contents of the IP header (not the IP body). This checksum is validated on every hop and needs to be recalculated after decrementing the TTL value.