To understand how traceroute works, we must understand a detail of the Internet Protocol (IP). Each IP packet header contains a field called Time to Live (TTL). TTL is the maximum number of seconds that a packet should live on the network before being discarded. This is important to keep an IP packet from simply persisting (which is, going in an endless loop) over the network.
TTL time intervals under one second are rounded up. This means that, in practice, each router that handles an IP packet decrements the TTL field by 1. Therefore, TTL is often used as a hop-count. That is to say that the TTL field simply represents the number of hops a packet can still take over the network.
The traceroute utility uses TTL to identify intermediate routers in a network. Traceroute begins by addressing a message (for example, a UDP datagram or an ICMP echo request) to the destination host. However, traceroute sets the TTL field to a value of 1. When the very first router in the connection path receives this message, it decrements TTL to zero. The router then realizes that the message has expired and discards it. A well-behaved router then sends an ICMP Time Exceeded message back to the original sender. Traceroute uses this Time Exceeded message to identify the first router in the connection.
Traceroute repeats this same process with additional messages. The second message is sent using a TTL of 2, and that message identifies the second hop in the network path. The third message is sent using a TTL of 3, and so on. Eventually, the message reaches its final destination and traceroute has mapped the entire network path.
The following diagram illustrates the method used by traceroute:
In the preceding diagram, the first message is sent with a TTL of 1. Router 1 doesn't forward this message, but instead returns an ICMP Time Exceeded message. The second message is sent with a TTL of 2. It makes it to the second router before timing out. The third message makes it to the destination, which replies with an Echo Reply message. (If this traceroute were UDP-based, it would expect to receive an ICMP Port Unreachable message instead.)
Not all routers return an ICMP Time Exceeded message, and some networks filter out these messages. In these cases, traceroute will have no way to know these routers' addresses. Traceroute prints an asterisk instead. Theoretically, if a router exists in the connection path that doesn't decrement the TTL field, then traceroute has no way of knowing that this router exists.
Now that we've covered the way ping and traceroute work, you may be wondering how they could be implemented in C code. Unfortunately, despite their simple algorithms, this is easier said than done. Keep reading to learn more.