Jianwei An

Topic

Bandwidth Tomography

Department of Computer Science

Date & location

• Thursday, May 15, 2025

• 10:00 A.M.

• Virtual Defence

Reviewers

Supervisory Committee

• Dr. Kui Wu, Department of Computer Science, University of Victoria (Supervisor)

• Dr. Jianping Pan, Department of Computer Science, UVic (Member)

• Dr. Xiaodai Dong, Department of Electrical and Computer Engineering, UVic (Outside Member) 

External Examiner

• Dr. Yuanzhu (Peter) Chen, School of Computing, Queen’s University 

Chair of Oral Examination

• Dr. Yu-Ting Chen, Department of Mathematics and Statistics, UVic

   

Abstract

Bandwidth tomography—inferring the bandwidth of internal network links from end-to-end path bandwidth measurements—is a long-standing open problem in network tomography. The core challenge arises from the fact that no existing mathematical framework directly addresses the inverse problem formulated as a set of min-equations.

To systematically tackle this challenge, we design a polynomial-time algorithm that accurately determines the bandwidth of all identifiable links and derives the tightest possible error bounds for unidentifiable links based on a given set of measurement paths. Furthermore, when additional information on link correlations is available, we leverage the extra information to refine our error bounds. Specifically, we explore two key types of link correlations: fairness constraints and total capacity constraints among a node’s adjacent links. We provide theoretical guarantees on how these correlations enhance the precision of bandwidth tomography and develop algorithms to address two fundamental challenges in refining these bounds: (i) the impact of synchronous vs. asynchronous updates and (ii) the cascading effects during bound updates.

Having developed algorithms to derive the tightest possible performance bounds for a given set of measurement paths, we then tackle the next major challenge: constructing optimal measurement paths that minimize the global error bounds for unidentifiable links. We prove the hardness of this problem and, in response, propose a reinforcement learning (RL) approach for measurement path construction. Our solution leverages domain-specific knowledge in bandwidth tomography and integrates both offline training and online prediction to build suitable measurement paths.

We evaluate our proposed methods using real-world ISP topologies and simulated networks. Experimental results show that compared to existing path construction methods—Random and Diversity Preferred—our RL-based approach significantly re duces the average error bound of inferred link bandwidths. In addition, our performance bound computation algorithms improve the state-of-the-art techniques by substantially tightening the performance bounds in bandwidth tomography.