Improving maximum-likelihood-based topology inference by sequentially inserting leaf nodes

Understanding the topology of a network is very important for network control and management. There have been several methods designed for estimating network topology from end-to-end measurements. Among these methods, the maximum-likelihood-based topology inference method is superior to suboptimal and pair-merging approaches, because it is capable of finding the global optimal topology. However, the existing method which searches the maximum likelihood tree directly is time-consuming, and may not be able to obtain the accurate topology of a larger-scale network. To overcome these issues, this study presents a maximum-likelihood-based leaf nodes inserting topology inference method. The method first builds a binary tree with two leaf nodes, and then inserts the remaining nodes into the tree one by one according to the maximum-likelihood criterion. When compared with the previous methods, the proposed method has the advantages of less computational cost and higher estimate precision. The analytical and simulation results show good performances by the proposed method.