License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2022.4
URN: urn:nbn:de:0030-drops-158142
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15814/
Go to the corresponding LIPIcs Volume Portal

Afshar, Ramtin ; Goodrich, Michael T. ; Matias, Pedro ; Osegueda, Martha C.

Mapping Networks via Parallel kth-Hop Traceroute Queries

pdf-format:
LIPIcs-STACS-2022-4.pdf (2 MB)

Abstract

For a source node, v, and target node, w, the traceroute command iteratively issues "kth-hop" queries, for k = 1, 2, … , δ(v,w), which return the name of the kth vertex on a shortest path from v to w, where δ(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, the study of the connectivity of networks, 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. In this paper, we provide efficient network mapping algorithms, that are based on kth-hop traceroute queries. 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 kth-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.

BibTeX - Entry

@InProceedings{afshar_et_al:LIPIcs.STACS.2022.4,
  author =	{Afshar, Ramtin and Goodrich, Michael T. and Matias, Pedro and Osegueda, Martha C.},
  title =	{{Mapping Networks via Parallel kth-Hop Traceroute Queries}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{4:1--4:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15814},
  URN =		{urn:nbn:de:0030-drops-158142},
  doi =		{10.4230/LIPIcs.STACS.2022.4},
  annote =	{Keywords: Network mapping, graph algorithms, parallel algorithms, distributed computing, query complexity, kth-hop queries}
}

Keywords: Network mapping, graph algorithms, parallel algorithms, distributed computing, query complexity, kth-hop queries
Collection: 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Issue Date: 2022
Date of publication: 09.03.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI