@inbook{0fb3cd2a42e148b3bdc181081ca804ec,

title = "An improved algorithm of multicast topology inference from end-to-end measurements",

abstract = "Multicast topology inference from end-to-end measurements has been widely used recently. Algorithms of inference on loss distribution show good performance in inference accuracy and time complexity. However, to our knowledge, the existing results produce logical topology structures that are only in the complete binary tree form, which differ in most cases significantly from the actual network topology. To solve this problem, we propose an algorithm that makes use of an additional measure of hop count. The improved algorithm of incorporating hop count in binary tree topology inference is helpful to reduce time complexity and improve inference accuracy. Through comparison and analysis, it is obtained that the time complexity of our algorithm in the worst case is O(l2) that is much better than O(l3) required by the previous algorithm. The expected time complexity of the algorithm is estimated at O(l.log2l), while that of the previous algorithm is O(l3).",

keywords = "End-to-end measurement, Hop count, Multicast, Topology inference",

author = "Hui Tian and Hong Shen",

year = "2003",

doi = "10.1007/978-3-540-39707-6_32",

language = "English",

isbn = "3540203591",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "376--384",

editor = "Alex Veidenbaum and Kazuki Joe and Hideharu Amano and Hideo Aiso",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}