An efficient loss rate estimator in multicast tomography and its validity

Network tomography receives a considerable attention in recent years that provides a viable methodology to discover network charateristics, such as the loss rate of a link, the delay distribution of a link, from end-to-end observations. In the loss rate estimation, the previous studies show that to find the maximum likelihood estimate (MLE) of a link/path, we need to solve a polynomial form with a degree that is one less than the number of descendants connected to the link/path. Since there is no analytical solution to a polynomial of 5 degree or higher, the main concern is focused on the methods to obtain MLE without using iterative approximation. An explicit estimator based on the Law of Large Numbers has been proposed. However, the estimate obtained from the estimator is not a MLE. If n <; ∞, the estimator may fail or produce an estimate that is significantly different from the MLE. In this paper, we propose an algorithm that can obtain the estimate analytically. In addition, we will point out the restriction of the previous estimators.