A Theory of Network Tracing

Traceroute is a widely used program for computing the topology of any network in the Internet. Using Traceroute, one starts from a node and chooses any other node in the network. Traceroute obtains the sequence of nodes that occur between these two nodes, as specified by the routing tables in these nodes. Each use of Traceroute in a network produces a trace of nodes that constitute a simple path in this network. In every trace that is produced by Traceroute, each node occurs either by its unique identifier, or by the anonymous identifier“*”. In this paper, we introduce the first theory aimed at answering the following important question. Is there an algorithm to compute the topology of a network

N

from a trace set

T

that is produced by using Traceroute in network

N

, assuming that each edge in

N

occurs in at least one trace in

T

, and that each node in

N

occurs by its unique identifier in at least one trace in

T

? We prove that the answer to this question is “No” if

N

is an even ring or a general network. However, it is ”Yes” if

N

is a tree or an odd ring. The answer is also “No” if

N

is mostly-regular, but “Yes” if

N

is a mostly-regular even ring.