Abstract: The link performance inference is crucial to network quality assessment, however usually the present assessment methods can only infer the simple network with definite layer and can’t be applied to the large scale network. This paper proposes a maximum likelihood estimation based on incomplete data to estimate the delay distribution of the inside network. This method divides the tree-like network topology into different two-layer binary subtrees and estimates every chain’s delay of every subtree. And then the link delays are divided into every link through the transplantation algorithm and every subtree is done in this way with this method one by one, thus the link delays of the whole network are obtained. The feasibility and accuracy of the algorithm are verified through NS2 simulation.

Key words: network tomography, delay distribution, Expectation Maximization（EM） algorithm, grafting estimation, delay estimation

摘要： 对于网络质量评估链路性能推测无疑是至关重要的，然而现有的估计方法通常只能推测层次数有限的简单网络，无法应用于大规模网络。提出了一种基于不完整数据极大似然估计算法，估计网络内部链路时延分布，该方法通过不同的发包策略将树状网络拓扑划分成不同的两层三链子树，针对每个子树估计每条“链”的时延，随后通过移植算法将路径时延划分到各链路中，逐一对每个子树使用该方法计算从而得到整个网络链路时延情况。利用NS2仿真实验验证了该算法的可行性和准确性。

关键词: 网络断层扫描, 时延分布, 最大期望（EM）算法, 移植算法, 时延估计