Waypoint-based Topology Inference

Yilei Lin, Ting He, Shiqiang Wang, Kevin Chan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


Traditional network topology inference aims at reconstructing the routing trees rooted at each probing source from end-to-end measurements. However, due to emerging technologies such as network function virtualization, software defined networking, and segment routing, many modern networks are capable of supporting generalized forwarding that can create complex routing topologies different from routing trees. In this work, we take a first step towards closing this gap by proposing methods to infer the routing topology (referred to as 1-1-N topology) from a single source to multiple destinations, where routes may be required to traverse a given waypoint. We first thoroughly study the special case of 1-1-2 topologies, showing that even this seemingly simple case is highly nontrivial with 36 possibilities. We then demonstrate how the solution to the special case can be used as building blocks to infer 1-1-N topologies. The inferred topology is proved to be equivalent to the ground truth up to splitting/combining edges in the same category.

Original languageEnglish (US)
Title of host publication2020 IEEE International Conference on Communications, ICC 2020 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728150895
StatePublished - Jun 2020
Event2020 IEEE International Conference on Communications, ICC 2020 - Dublin, Ireland
Duration: Jun 7 2020Jun 11 2020

Publication series

NameIEEE International Conference on Communications
ISSN (Print)1550-3607


Conference2020 IEEE International Conference on Communications, ICC 2020

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Waypoint-based Topology Inference'. Together they form a unique fingerprint.

Cite this