An improved algorithm of multicast topology inference from end-to-end measurements

Hui Tian, Hong Shen

研究成果: Chapter同行評審

5 引文 斯高帕斯(Scopus)

摘要

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).

原文English
主出版物標題Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
編輯Alex Veidenbaum, Kazuki Joe, Hideharu Amano, Hideo Aiso
發行者Springer Verlag
頁面376-384
頁數9
ISBN(列印)3540203591, 9783540397076
DOIs
出版狀態Published - 2003
對外發佈

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
2858
ISSN(列印)0302-9743
ISSN(電子)1611-3349

指紋

深入研究「An improved algorithm of multicast topology inference from end-to-end measurements」主題。共同形成了獨特的指紋。

引用此