Analysis on binary loss tree classification with hop count for multicast topology discovery

The use of multicast inference on end-to-end measurement has recently been proposed as a means to obtain underlying multicast topology. In this paper we analyze the algorithm of the binary loss tree classification with hop count (HBLT). We compare it with the algorithm of binary loss tree classification (BLT) and show that the probability of misclassification of HBLT decreases more quickly than 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 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.