Statistical Estimation of Delays in a Multicast Tree using Accelerated EM

Abstract:  Tomography is one of the most promising techniques
today to provide spatially localized information about internal
network performance in a robust and scalable way. The key idea is
to measure performance at the edge of the network, and to
correlate these measurements to infer the internal network
performance. This paper focuses on a specific delay tomographic
problem on a multicast diffusion tree, where end-to-end delays
are observed at every leaf of the tree, and mean sojourn time are
estimated for every node in the tree. The estimation is performed
using Maximum Likelihood Estimator (MLE) and the
Expectation-Maximization (EM) algorithm. Using queuing theory
results, we carefully justify the model we use in the case of
rare probing. We then give an explicit EM implementation in the
case of i.i.d. exponential delays for a general tree. As we work
with a non-discretized delays and a full MLE, EM is known to be
slow. We hence present a yet very simple but, in our case, very
effective speedup technique using Principal Component Analysis
(PCA). MLE estimations are provided for a few different trees to
evaluate our technique.