CS 269S, Spring 2021: Theory Seminar

May 7, 2021, 1:00 – 1:50:

Mapping Networks via Parallel $k$th-Hop Traceroute Queries

Ramtin Afshar

For a source node, $v$, and target node, $w$, the traceroute command iteratively issues “$k$th-hop” queries, for $k=1,2,\dots ,\delta (v,w)$, which return the name of the $k$th vertex on a shortest path from $v$ to $w$, where $\delta (v,w)$ is the distance between $v$ and $w$, that is, the number of edges in a shortest-path from $v$ to $w$. The 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 $k$th-hop 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 $k$th-hop 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.