While robust measurements of network dynamics are essential for the design and management of internetworks, administrative, economic and privacy issues make it impractical to monitor every link in the network. Therefore it becomes necessary to infer network and performance characteristics from end-to-end measurements. One characteristic that is frequently needed to build reliable multicast protocols is the topology of the tree used for multicast communications. Several algorithms have been proposed in the literature for making use of correlations between packets lost at each of the receivers to infer a multicast tree. Most algorithms in the literature are centralized -- they require some node (e.g., the source) to gather data from all receivers in order to compute the tree. Also, most algorithms build the tree up in a bottom-up manner, so that the entire tree must be built even if we require few levels from the top. In this work, we propose efficient top-down algorithms for the multicast tree inference problem. We show that our algorithm can be easily implemented in a distributed fashion, which improves the scalability. We analyze our algorithms and prove upper bounds on the sample complexity or the number of samples required to infer multicast trees with given error bounds and sensitivity. We prove that these bounds are tight by proving matching lower bounds on the sample complexity for some trees. Our results quantify the tradeoff between the number of samples and the probability of computing the tree correctly, and provide lower bounds on the number of samples needed to compute the tree with a given error probability.

Download paper in PDF format.

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.