Seminar: Optimal probing for unicast network delay tomography

Speaker: Dr. Yu Gu

Faculty Host: Professor Kang Xi

Abstract

Network tomography has been proposed to ascertain internal network performances from end-to-end measurements. In this work, we present priority probing, an optimal probing scheme for unicast network delay tomography that is proven to provide the most accurate estimation. We first demonstrate that the Fisher information matrix in unicast network delay tomography can be decomposed into an additive form where information accumulates as each probing is performed. This establishes the space over which we can design the optimal probing scheme. Then, we formulate the optimal probing problem into a semi-definite programming (SDP) problem. High computation complexity constrains the SDP solution to only small scale scenarios. In response, we propose a greedy algorithm that approximates the optimal solution. Evaluations through simulation demonstrate that priority probing effectively increases estimation accuracy under a fixed number of probes.

Bio

Yu Gu is a research staff member in NEC Laboratory, America. He graduated with a Ph.D degree from UMass, Amherst in August, 2008. His research interests include network modeling and measurement, traffic anomaly detection and congestion control.