A Distance-based Agglomerative Clustering Algorithm for Multicast Network Tomography

In this paper, we address the network tomography problems of inferring the multicast routing tree topology and estimating core link performance characteristics (i.e., loss rate, jitter) based on end-to-end measurements from a source node to a set of destination nodes. We extend the agglomerative hierarchical clustering algorithm that works in a bottom-up manner and iteratively joins siblings (i.e., nodes with the same parent) by incorporating the concepts of reciprocal nearest neighbors and nearest neighbors chains. We employ two alternative ways for calculating the required distance matrix of terminal nodes. One based on additive tree metrics and another utilizing several normalized dissimilarity measures on the binary sequences of received/lost probes maintained at each node. Finally, we evaluate the performance of the proposed algorithm in terms of estimation accuracy and correctness of the inferred logical routing tree over real network topologies constructed in an open testbed of the Fed4FIREP1us federation.