Active Network Tomography: A Measurement Design Perspective

Ting He
Associate Professor
Computer Science and Engineering at Pennsylvania State University
SERC 306
Wednesday, October 11, 2017 - 11:00
Timely and accurate knowledge of network internal state (e.g., delay/loss/jitter on links) is essential to efficient network operation and resource allocation. Obtaining such knowledge is, however, a highly nontrivial task in large-scale heterogeneous networks, where the existence of heterogeneous domains due to the difference in communication technology, protocol, ownership, and/or policy makes it difficult for a single monitoring system to receive global support throughout the network. In this talk, I will review a promising approach for monitoring such networks by inferring the internal network state (e.g., link delays) from end-to-end measurements (e.g., path delays) taken between special nodes called monitors, known as "network tomography". The focus will be given to a key challenge in applying network tomography, called "lack of identifiability", i.e., the measurements cannot uniquely determine the network state. In contrast to previous works that resort to best-effort heuristics, I aim at guaranteeing identifiability via carefully designed measurements.
In this talk, I will cover our results on (i) the fundamental condition on the network topology and monitor placement to achieve identifiability, (ii) the optimal monitor placement and path construction algorithms that guarantee identifiability using a minimum number of monitors and a minimum set of measurement paths, and (iii) the optimal way of allocating probes among the measurement paths to minimize the error in estimating link parameters from measurements of random path states. I will then cover several recent advances on extending the measurement design framework to support dynamic and resource-constrained networks, and conclude with an overview of future directions. The above results are selected from publications at ICDCS'13, IMC'13, TON'14, SIGMETRICS'15, INFOCOM'16, TON'17, and Performance'17, including two best paper awards and one nomination.