## Abstract

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(l^{2}) instead of O(l^{3}) required by BLT in the worst case, and O(l ·log l) instead of O(l^{3}) 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 language | English |
---|---|

Pages (from-to) | 935-953 |

Number of pages | 19 |

Journal | International Journal of Communication Systems |

Volume | 19 |

Issue number | 8 |

DOIs | |

Publication status | Published - Oct 2006 |

Externally published | Yes |

## Keywords

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