Network performance tomography involves correlating end-to-end performance measures over different network paths to infer the performance characteristics on their intersection. Multicast based inference of link-loss rates is the first paradigm for the approach. Existing algorithms generally require numerical solution of polynomial equations for a maximum-likelihood estimator (MLE), or iteration when applying the expectation maximization (EM) algorithm. The purpose of this note is to demonstrate a new estimator for link-loss rates that is computationally simple, being an explicit function of the measurements, and that has the same asymptotic variance as the MLE, to first order in the link-loss rates.

Network tomography using multicast probes enables inference of loss characteristics of internal network links from reports of end-to-end loss seen at multicast receivers. We develop estimators for internal loss rates when reports are not available on all probes or from all receivers. This problem is motivated by the use of unreliable transport protocols, such as reliable transport protocol, to transmit loss reports to a collector for inference. We use a maximum-likelihood (ML) approach in which we apply the expectation maximization (EM) algorithm to provide an approximating solution to the the ML estimator for the incomplete data problem. We present a concrete realization of the algorithm that can be applied to measured data. For classes of models, we establish identifiability of the probe and report loss parameters, and convergence of the EM sequence to the maximum-likelihood estimator (MLE). Numerical results suggest that these properties hold more generally. We derive convergence rates for the EM iterates, and the estimation error of the MLE. Finally, we evaluate the accuracy and convergence rate through extensive simulations.

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.

Packet delay greatly influences the overall performance of network applications. It is therefore important to identify causes and locations of delay performance degradation within a network. Existing techniques, largely based on end-to-end delay measurements of unicast traffic, are well suited to monitor and characterize the behavior of particular end-to-end paths. Within these approaches, however, it is not clear how to apportion the variable component of end-to-end delay as queueing delay at each link along a path. Moreover, there are issues of scalability for large networks. In this paper, we show how end-to-end measurements of multicast traffic can be used to infer the packet delay distribution and utilization on each link of a logical multicast tree. The idea, recently introduced in Caceres et al. (1999), is to exploit the inherent correlation between multicast observations to infer performance of paths between branch points in a tree spanning a multicast source and its receivers. The method does not depend on cooperation from intervening network elements; because of the bandwidth efficiency of multicast traffic, it is suitable for large-scale measurements of both end-to-end and internal network dynamics. We establish desirable statistical properties of the estimator, namely consistency and asymptotic normality. We evaluate the estimator through simulation and observe that it is robust with respect to moderate violations of the underlying model.

The use of end-to-end multicast traffic measurements has been recently proposed as a means to infer network internal characteristics as packet link loss rate and delay. We propose an algorithm that infers the multicast tree topology based on these end-to-end measurements. It is different from previous approaches which make only partial use of the available information, this algorithm adaptively combines different performance measures to reconstruct the topology. We establish its consistency and evaluate its accuracy through simulation. We show that in general it requires many fewer probes to correctly identify the topology than other methods.

We explore the use of end-to-end multicast traffic as measurement probes to infer network internal characteristics. We have developed in an earlier paper a maximum likelihood estimator for packet loss rates on individual links based on losses observed by multicast receivers. This technique exploits the inherent correlation between such observations to infer the performance of paths between branch points in the multicast tree spanning the probe source and its receivers. We evaluate through analysis and simulation the accuracy of our estimator under a variety of network conditions. In particular, we report on the error between inferred loss rates and actual loss rates as we vary the network topology, propagation delay, packet drop policy, background traffic mix, and probe traffic type. In all but one case, estimated losses and probe losses agree to within 2 percent on average. We feel this accuracy is enough to reliably identify congested links in a wide-area internetwork.

Robust measurements of network dynamics are increasingly important to the design and operation of large internetworks like the Internet. However, administrative diversity makes it impractical to monitor every link on an end-to-end path. At the same time, it is difficult to determine the performance characteristics of individual links from end-to-end measurements of unicast traffic. In this paper, we introduce the use of end-to-end measurements of multicast traffic to infer network-internal characteristics. The bandwidth efficiency of multicast traffic makes it suitable for large-scale measurements of both end-to-end and internal network dynamics. We develop a maximum-likelihood estimator for loss rates on internal links based on losses observed by multicast receivers. It exploits the inherent correlation between such observations to infer the performance of paths between branch points in the tree spanning a multicast source and its receivers. We derive its rate of convergence as the number of measurements increases, and we establish robustness with respect to certain generalizations of the underlying model. We validate these techniques through simulation and discuss possible extensions and applications of this work