关键词: 拓扑估计, 最大似然, 网络层析成像, 三明治包, 马尔科夫链蒙特卡洛算法

Abstract: Maximum likelihood based topology estimation method can obtain globally optimal estimation results, and its performance is better than that of other methods such as general local optimization and node fusion methods. However, when network scale is large, the topology estimation is computationally intensive. To solve this problem, firstly, the authors proved that a network topology estimation likelihood function was a single-peaked function with only one extreme value, namely, the maximum value called peak value. Using the single-peaked property of likelihood function, they improved the current maximum likelihood based topology estimation method. Without returning to a smaller likelihood value state when searching for the maximum likelihood tree, improved method effectively reduces the computational complexity. Finally, the results of Matlab and ns-2 simulations show that improved method cuts computational complexity by 30%-46% without reducing topological estimation accuracy.

Key words: topology estimation, maximum likelihood, network tomography, sandwich packets, Markov Chain Monte Carlo