Fast bottom up algorithm to infer link delay distributions
一种自底向上的推测链路延迟分布的快速算法*

Network tomography uses end-to-end measurements to estimate the link delay distribution. The existing work based on maximum likelihood estimator (MLE) and expectation maximization (EM) algorithm uses iterative approximation to make the estimation, which consumes a long time for large scale network. To overcome this limitation, this paper proposed a fast algorithm named FBA. The FBA estimated the link delay distributions level by level from bottom to up. The analytical and simulation results show that the FBA greatly reduces the computational complexity. In addition, the estimation accuracy of the FBA is close to that of the EM algorithm with enough probing packets.