Traceroute

How traceroute works ca. September 2009

The Traceroute class is a container for global functions and state.

Each target has a TraceGroup (the "group" is a group of TraceProbes).

Proposed new design

There's no need for a reference trace. It's arbitrary to pick a single host to be the reference host, when it may not even share all that many hops with other hosts.

Nmap's traceroute model

Nmap does not perform a full trace to every host, so necessarily it must make assumptions about the hops that it has not probed. The first and most fundamental of these is that, in tracing a host, we find an intermediate hop that has already been seen in tracing another host, we may assume that it and all it parents' hops are shared between the two hosts.

This suggests a different algorithm and data structure for storing the topology information. We represent the topology as a tree composed of nodes of the form

struct Hop {

	struct sockaddr_storage hop_address;
	struct sockaddr_storage in_trace_for;
	struct Node *parent;

}

You don't traverse the tree downward from the root; you traverse it upward from the leaves; from the targets back to localhost.

A side effect of this change is that it might be necessary to consult the records for more than one host when reading consolidated results. For example, the results for one host might say "hops 1-5 are the same as for host 1.1.1.1" and the results for 1.1.1.1 might say "hops 1-3 are the same as for host 2.2.2.2.

Standard traceroute (2009-09-01) r15389

nmap -sP --traceroute scanme.nmap.org/30 -n

1. Traceroute stats: 21.373 s, 67 probes, 6 retransmissions, 107 if done serially, 57%
2. Traceroute stats: 11.194 s, 66 probes, 5 retransmissions, 107 if done serially, 57%
3. Traceroute stats: 1.098 s, 65 probes, 4 retransmissions, 107 if done serially, 57%
4. Traceroute stats: 10.743 s, 64 probes, 5 retransmissions, 107 if done serially, 55%

Nonparallel routes