Statistical estimation of delays in a multicast tree using accelerated EM

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 times are estimated for every node in the tree. The estimation is performed using the 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 non-discretized delays and a full MLE, EM is known to be slow. We hence present a very simple but, in our case, very effective speed-up technique using Principal Component Analysis (PCA). MLE estimations are provided for a few different trees to evaluate our technique.