Network delay tomography using flexicast experiments

Earl Lawrence, George Michailidis, Vijayan N. Nair

Journal of the Royal Statistical Society: Series B (Statistical Methodology) · 2006 · Volume 68 · Issue 5

DOI: 10.1111/j.1467-9868.2006.00567.x

Abstract

Summary.Estimating and monitoring the quality of service of computer and communications networks is a problem of considerable interest. The paper focuses on estimating link level delay distributions from end-to-end path level data collected by using active probing experiments. This is an interesting large scale statistical inverse (deconvolution) problem. We describe a flexible class of probing experiments (‘flexicast’) for data collection and develop conditions under which the link level delay distributions are identifiable. Maximum likelihood estimation using the EM algorithm is studied. It does not scale well for large trees, so a faster algorithm based on solving for local maximum likehood estimators and combining their information is proposed. The usefulness of the methods is illustrated on real voice over Internet protocol data that were collected from the University of North Carolina campus network.

Keywords

Deconvolution, EM algorithm, Internet, Inverse problem, Tree-structured graphs

Enable JavaScript for citation tools and additional paper interactions.