Topology Inference of Networks utilizing Rooted Spanning Tree Embeddings

Martin Byrenheid, Stefanie Roos, Thorsten Strufe

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review


Due to its high efficiency, routing based on greedy embeddings of rooted spanning trees is a promising approach for dynamic, large-scale networks with restricted topologies. Friend-to-friend (F2F) overlays, one key application of embedding-based routing, aim to prevent disclosure of their participants to malicious members by restricting exchange of messages to mutually trusted nodes. Since embeddings assign a unique integer vector to each node that encodes its position in a spanning tree of the overlay, attackers can infer network structure from knowledge about assigned vectors. As this information can be used to identify participants, an evaluation of the scale of leakage is needed. In this work, we analyze in detail which information malicious participants can infer from knowledge about assigned vectors. Also, we show that by monitoring packet trajectories, malicious participants cannot unambiguously infer links between nodes of unidentified participants. Using simulation, we find that the vector assignment procedure has a strong impact on the feasibility of inference. In F2F overlay networks, using vectors of randomly chosen numbers for routing decreases the mean number of discovered individuals by one order of magnitude compared to the popular approach of using child enumeration indexes as vector elements.

Original languageEnglish
Title of host publicationICDCN 2022 - Proceedings of the 2022 International Conference on Distributed Computing and Networking
PublisherAssociation for Computing Machinery (ACM)
Number of pages10
ISBN (Electronic)978-1-4503-9560-1
Publication statusPublished - 2022
Event23rd International Conference on Distributed Computing and Networking, ICDCN 2022 - Virtual, Online, India
Duration: 4 Jan 20227 Jan 2022

Publication series

NameACM International Conference Proceeding Series


Conference23rd International Conference on Distributed Computing and Networking, ICDCN 2022
CityVirtual, Online

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.


  • friend-to-friend overlays
  • greedy embeddings
  • topology inference


Dive into the research topics of 'Topology Inference of Networks utilizing Rooted Spanning Tree Embeddings'. Together they form a unique fingerprint.

Cite this