Queuing Network Topology Inference Using Passive Measurements

Yilei Lin, Ting He, Guodong Pang

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

2 Scopus citations


In this work, we revisit a classic problem of inferring a tree topology from end-to-end measurements originated by a single source, with two critical differences: (i) instead of relying on measurements with specific correlation across paths that often require active probing, we do not rely on any correlation and can thus utilize passive measurements; (ii) instead of inferring a logical topology that ignores certain nodes, we want to recover the physical topology. Our key idea is to utilize the detailed queuing dynamics inside the network to estimate the number of queues and a certain parameter (residual capacity) of each queue on each measurement path, and then use the estimated parameters as fingerprints to detect shared queues and infer the topology. To this end, we develop a Laplace-transform-based estimator to extract the parameters of a tandem of queues from end-to-end delays, and efficient algorithms to identify the parameters associated with the same queue and infer the topology accordingly. The inferred topology is guaranteed to converge to the ground truth, up to a permutation of queues traversed by the same paths, as the number of measurements increases. Our evaluations validate the proposed solutions against benchmarks and identify potential directions for further improvements.

Original languageEnglish (US)
Title of host publication2021 IFIP Networking Conference, IFIP Networking 2021
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9783903176393
StatePublished - Jun 21 2021
Event20th Annual IFIP Networking Conference, IFIP Networking 2021 - Virtual, Espoo, Finland
Duration: Jun 21 2021Jun 24 2021

Publication series

Name2021 IFIP Networking Conference, IFIP Networking 2021


Conference20th Annual IFIP Networking Conference, IFIP Networking 2021
CityVirtual, Espoo

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Computer Science Applications
  • Information Systems and Management
  • Hardware and Architecture


Dive into the research topics of 'Queuing Network Topology Inference Using Passive Measurements'. Together they form a unique fingerprint.

Cite this