Queueing Network Topology Inference Using Passive and Active Measurements

Authors:
Publisher website
Google Scholar
Abstract
We revisit a classic problem of inferring the routing tree for a given source in a packet-switched network from end-to-end measurements, with two critical differences from existing solutions: (i) instead of exclusively relying on active measurements obtained by probing, we strive to maximally utilize passive measurements obtained from data packets; (ii) instead of inferring a logical topology that omits degree-2 nodes, we want to recover the physical topology containing all the nodes. Our main idea is to utilize the detailed queueing dynamics inside the network to estimate a certain parameter (residual capacity) of each queue, and then use the estimated parameters as fingerprints to detect the queues shared across paths and thus infer the topology. To this end, we develop a Laplace-transform-based estimator to estimate the parameters of a tandem of queues from end-to-end delays, and efficient algorithms to infer the topology by identifying the parameters associated with the same queue. To improve the accuracy, we further develop a hybrid algorithm that uses the information from active measurements to identify (generalized) siblings and the information from passive measurements to detect shared queues on the paths from the source to each pair of identified siblings. Our inferred topology is guaranteed to converge to the ground-truth topology as the number of measurements increases, up to a permutation of the queues traversed by the same set of paths. Our evaluations in both queueing-theoretic and packet-level simulations show that the proposed solutions, particularly the hybrid algorithm, significantly improve the accuracy over the state of the art.
Funding Information
  • National Science Foundation (CNS-2106294)

This publication has 32 references indexed in Scilit: