  Traceroute measurements are one of our main instruments to shed light onto
the structure and properties of today's complex networks such as the Internet.
This paper studies the feasibility and infeasibility of inferring the network
topology given traceroute data from a worst-case perspective, i.e., without any
probabilistic assumptions on, e.g., the nodes' degree distribution. We attend
to a scenario where some of the routers are anonymous, and propose two
fundamental axioms that model two basic assumptions on the traceroute data: (1)
each trace corresponds to a real path in the network, and (2) the routing paths
are at most a factor 1/alpha off the shortest paths, for some parameter alpha
in (0,1]. In contrast to existing literature that focuses on the cardinality of
the set of (often only minimal) inferrable topologies, we argue that a large
number of possible topologies alone is often unproblematic, as long as the
networks have a similar structure. We hence seek to characterize the set of
topologies inferred with our axioms. We introduce the notion of star graphs
whose colorings capture the differences among inferred topologies; it also
allows us to construct inferred topologies explicitly. We find that in general,
inferrable topologies can differ significantly in many important aspects, such
as the nodes' distances or the number of triangles. These negative results are
complemented by a discussion of a scenario where the trace set is best
possible, i.e., "complete". It turns out that while some properties such as the
node degrees are still hard to measure, a complete trace set can help to
determine global properties such as the connectivity.
