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

Abstract

<jats:title>Abstract</jats:title><jats:p>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 <jats:italic>O</jats:italic>(<jats:italic>l</jats:italic><jats:sup>2</jats:sup>) instead of <jats:italic>O</jats:italic>(<jats:italic>l</jats:italic><jats:sup>3</jats:sup>) required by BLT in the worst case, and <jats:italic>O</jats:italic>(<jats:italic>l</jats:italic> · log <jats:italic>l</jats:italic>) instead of <jats:italic>O</jats:italic>(<jats:italic>l</jats:italic><jats:sup>3</jats:sup>) by BLT in the expected case, where <jats:italic>l</jats:italic> 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. Copyright © 2006 John Wiley &amp; Sons, Ltd.</jats:p>