An improved algorithm for multicast topology discovery from end-to-end measurements

Hui Tian, Hong Shen

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


We present a new multicast topology inference algorithm called binary loss tree classification with hop count (HBLT). HBLT improves the previous algorithm of binary loss tree classification (BLT) not only in time complexity but also in misclassification probability and inference accuracy. The time complexity of HBLT is O(l2) instead of O(l3) required by BLT in the worst case, and O(l ·log l) instead of O(l3) by BLT in the expected case, where l is the number of receivers in the multicast network. The misclassification probability of HBLT decreases more quickly than that of BLT as the number of probe packets increases. For correct classification, the inference accuracy of HBLT is always 1, i.e. the inferred tree is identical to the physical tree, whereas that of BLT is dependent on the shape of the physical tree and inversely proportional to the number of internal nodes with single child. We also show through simulation that HBLT requires fewer probe packets to infer the correct topology and hence has a lower misclassification probability and higher inference accuracy than BLT.

Original languageEnglish
Pages (from-to)935-953
Number of pages19
JournalInternational Journal of Communication Systems
Issue number8
Publication statusPublished - Oct 2006
Externally publishedYes


  • Hop count
  • Inference accuracy
  • Misclassification probability
  • Multicast network
  • Topology inference


Dive into the research topics of 'An improved algorithm for multicast topology discovery from end-to-end measurements'. Together they form a unique fingerprint.

Cite this