Estimating internal link loss rates using active network tomography.

Abstract

Estimating quality of service parameters associated with computer and communication networks, such as link loss rates and delay distributions, is a problem of considerable importance to network administrators and service providers. This thesis considers active network tomography and studies the problem of estimating internal link loss rates from end-to-end measurements based on active probing. The statistical inference involves an inverse problem. The thesis proposes a new class of active probing schemes and studies its properties. Necessary and sufficient conditions for identifiability with single-source topologies and a sufficient condition for multi-source topologies are established. Based on the necessary and sufficient identifiability condition, a class of minimal experiments is proposed for single-source topologies. Two types of estimation methods are studied for statistical inference: (1) Maximum likelihood estimators (MLE); (2) Least squares (LS) based estimators. The MLE is computed using the EM algorithm, which could be computationally intensive depending on the topology and the associated loss rates, but nonetheless useful because it always returns estimates within the [0,1] range. The LS based estimators are fast, easy to implement and provide an explicit variance-covariance matrix for the parameters of interest. A distributed version of the LS estimators is also introduced to address the scalability issue. The large-sample properties of the estimators are studied. It is shown that the MLE is consistent and asymptotically efficient, all the LS based estimators are consistent and asymptotically normal, and in addition the GLS and IRWLS estimators are asymptotically equivalent to the MLE. Several design issues are also investigated, including how to allocate the probes among the schemes for a given probing experiment and how to choose an optimal experiment for a given topology. Finally, the results are illustrated using the NS network simulator package.