Multicast topology inference from measured end-to-end loss
Nick G. Duffield, Joseph Horowitz, Francesco Lo Presti, Don Towsley · IEEE Transactions on Information Theory · 2002
Abstract—The use of multicast inference on end-to-end measurement has recently been proposed as a means to infer network internal characteristics such as packet link loss rate and delay. In this paper, we propose three types of algorithm that use loss measurements to infer the underlying multicast topology: i) a grouping estimator that exploits the monotonicity of loss rates with increasing path length; ii) a maximum-likelihood (ML) estimator (MLE); and iii) a Bayesian estimator. We establish their consistency, compare their complexity and accuracy, and analyze the modes of failure and their asymptotic probabilities. Index Terms—Communication networks, end-to-end measurement, maximum-likelihood (ML) estimation, multicast, statistical inference, topology discovery.