How traceroute Works

I wrote the following post while I was a co-op at MITRE back in 1995. I was tasked with writing a low-level C library for crafting TCP/IP packets of various types. (The first proof-of-concept application which used the library forged routing redirects.)

I'd read TCP/IP Illustrated Volume 1 by W. Richard Stevens (who is greatly missed) in pretty short order, and was spending a lot of time on the groups in the Newsgroups: line.

This post has become sort of vaguely famous; at least, it's been available on the web for the past ten years. I figured it was time I put it up too, if only to preserve it.

2005-10-20

From: woj@k2.ccs.neu.edu (Matthew Wojcik)
Newsgroups: comp.security.unix,comp.protocols.tcp-ip,alt.security
Subject: Re: Source Routing
Date: 08 Sep 1995 14:05:04 GMT
Organization: College of CS, Northeastern University
Lines: 60
Message-ID: 
References: <810407791snz@hacknet.demon.co.uk> <42o7an$c5f@bubbla.uri.edu>
	<42ostr$dbh@cd4680fs.rrze.uni-erlangen.de>
NNTP-Posting-Host: k2.ccs.neu.edu
In-reply-to: unrza2@rzmail.uni-erlangen.de's message of 8 Sep 1995 07:55:39 GMT
Status: RO

>>>>> "Jochen" == Jochen Kaiser  writes:

Jochen> In <42o7an$c5f@bubbla.uri.edu> medulla@phoenix.org (Mike Edulla)
Jochen> writes:
>> : How does source routing work?

>> The record route option is to record the route a packet is taking, it is
>> used by (i think) the traceroute program, which is probably why traceroute
>> is suid root.

Jochen> No ! The Record Route Option is used by most ping implementations when
Jochen> you supply the "-R" Option. Because the record route option offers
Jochen> only place for 9 IP-Adresses in the IP-Header the traceroute cannot
Jochen> make use of it. Traceroute uses ICMP messages with a varying TTL (time
Jochen> to live) - field.  The traceroute Program works as follows: When you
Jochen> want the route to a host several hops away, the traceroute sends out
Jochen> an ICMP-Message with a TTL of 1 to that host. The first router on the
Jochen> way gets this message and sees the tiny little TTL. It's an internet
Jochen> standard that TTL of 1 must not be forwarded. Thats why the router
Jochen> throws away the packet and sends back an ICMP - time-exceeded message.
Jochen> The traceroute program gets the ICMP-time-exceeded message and sends
Jochen> out a next ICMP - Messages to the host with a TTL of 2 which passes
Jochen> the first router and is decremented by it by one and passsed to the
Jochen> next hop. This hop sees an TTL of 1 and sends back another
Jochen> ICMP-time-exceeded message .... and so on.  The traceroute program
Jochen> collect these messages and gives the user one (!) possibly route to
Jochen> that host.

Mostly right.  Traceroute actually sends out UDP datagrams to find a route,
however, and not ICMP messages.  The destination UDP port is set to an
unlikely value so the final destination host won't process the packet, but
will instead send back an ICMP port unreachable message.  When it gets a port
unreachable, it knows it has reached the destination host.

UDP datagrams are sent out rather than, say, ICMP echo request messages
because an ICMP port unreachable message sends back 8 bytes of the data from
the IP datagram that caused the ICMP error.  In this case, those 8 bytes are
the UDP header.  Van Jacobson uses a hack: the source UDP port in the messages
traceroute sends out is actually used by his code as an identifier, to allow
more than one use to run traceroute at the same time.  Another hack in the
same vein: he increments the destination port with each message to keep track
of what hop he's on.  (These are obviously on the order of "very clever"
rather than "awful" hacks).

traceroute makes some of the cleverest use of various ICMP messages I can
imagine.  Understand what's going on with traceroute, and you'll be a lot
closer to knowing what's really happening when you send information across the
Internet (or on any tcp/ip network), which is doubtless why Rich Stevens
devotes all of chapter 8 of TCP/IP Ill. Vol 1 to it.

Jochen> Ciao Jochen

Jochen> -- Jochen Kaiser Jochen.Kaiser@rrze.uni-erlangen.de Betreuung
Jochen> Terminal-Server dialinadm@rrze.uni-erlangen.de Regionales
Jochen> Rechenzentrum Universitaet Erlangen-Nuernberg

--The Woj                    Matthew Wojcik                   woj@ccs.neu.edu
                        Experimental Systems Group       woj@mbunix.mitre.org
          College of Computer Science, Northeastern University