Please use this identifier to cite or link to this item:
Scopus Web of ScienceĀ® Altmetric
Type: Conference paper
Title: An improved algorithm of multicast topology inference from end-to-end measurements
Author: Tian, H.
Shen, H.
Citation: High performance computing : 5th International Symposium, ISHPC 2003, Tokio-Odaiba, Japan, October 20-22, 2003 : proceedings / Alex Veidenbaum ... [et al.] (eds.), pp. 376-384
Publisher: Springer
Publisher Place: Berlin
Issue Date: 2003
Series/Report no.: Lecture notes in computer science, 2858
ISBN: 3540203591
ISSN: 0302-9743
Conference Name: International Symposium on High Performance Computing (5th : 2003 : Tokyo, Japan)
Statement of
Hui Tian and Hong Shen
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 (l 2) that is much better than O (l 3) required by the previous algorithm. The expected time complexity of the algorithm is estimated at , while that of the previous algorithm is O (l 3).
Keywords: Multicast
topology inference
end-to-end measurement
hop count
Description: The original publication is available at
DOI: 10.1007/978-3-540-39707-6_32
Published version:
Appears in Collections:Aurora harvest
Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.