  Traceroute is a networking tool that allows one to discover the path that
packets take from a source machine, through the network, to a destination
machine. It is widely used as an engineering tool, and also as a scientific
tool, such as for discovery of the network topology at the IP level. In prior
work, authors on this technical report have shown how to improve the efficiency
of route tracing from multiple cooperating monitors. However, it is not unusual
for a route tracing monitor to operate in isolation. Somewhat different
strategies are required for this case, and this report is the first systematic
study of those requirements. Standard traceroute is inefficient when used
repeatedly towards multiple destinations, as it repeatedly probes the same
interfaces close to the source. Others have recognized this inefficiency and
have proposed tracing backwards from the destinations and stopping probing upon
encounter with a previously-seen interface. One of this technical report's
contributions is to quantify for the first time the efficiency of this
approach. Another contribution is to describe the effect of non-responding
destinations on this efficiency. Since a large portion of destination machines
do not reply to probe packets, backwards probing from the destination is often
infeasible. We propose an algorithm to tackle non-responding destinations, and
we find that our algorithm can strongly decrease probing redundancy at the cost
of a small reduction in node and link discovery.
