Analysis on binary loss tree classification with hop count for multicast topology discovery
Date
2004
Authors
Tian, H.
Shen, H.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
CCNC2004 : 2004 1st IEEE Consumer Communications and Networking Conference : Consumer networking : closing the digital divide : proceedings : Caesar's Palace, Las Vegas, Nevada USA, 5-8 January 2004 / [Robert S. Fish, general chair], pp.164-168
Statement of Responsibility
Hui Tian, Hong Shen
Conference Name
IEEE Consumer Communications and Networking Conference (1st : 2004 : Las Vegas, Nevada)
Abstract
The use of multicast inference on end-to-end measurement has recently been proposed as a means of obtaining the underlying multicast topology. We analyze the algorithm of binary loss tree classification with hop count (HBLT). We compare it with the binary loss tree classification algorithm (BLT) and show that the probability of misclassification of HBLT decreases more quickly than that of BLT as the number of probing packets increases. The inference accuracy of HBLT is always 1 (the inferred tree is identical to the physical tree) in the case of correct classification, whereas that of BLT is dependent on the shape of the physical tree and inversely proportional to the number of internal nodes with a single child. Our analytical result shows that HBLT is superior to BLT, not only on time complexity, but also on misclassification probability and inference accuracy.
School/Discipline
Dissertation Note
Provenance
Description
Copyright © 2004 IEEE