For a source node, traceroute
command iteratively issues
“traceroute
command is often used for network
mapping applications and it has been studied theoretically with respect
to biases it introduces for network mapping when only a subset of nodes
in the network can be the source of traceroute
queries. We
are not aware of prior theoretical work on efficient network mapping
algorithms, however, that are based on
traceroute
queries; hence, in this paper we
provide such algorithms. Our results include an algorithm that runs in
a constant number of parallel rounds with a subquadratic number of
queries under reasonable assumptions about the sampling coverage of the
nodes that may issue traceroute
queries. In
addition, we introduce a number of new algorithmic techniques, including
a high-probability parametric parallelization of a graph clustering
technique of Thorup and Zwick, which may be of independent interest.