Estimating network loss rates using active tomography

Active network tomography refers to an interesting class of large-scale inverse problems that arise in estimating the quality of service parameters of computer and communications networks. This article focuses on estimation of loss rates of the internal links of a network using end-to-end measurements of nodes located on the periphery. A class of flexible experiments for actively probing the network is introduced, and conditions under which all of the link-level information is estimable are obtained. Maximum likelihood estimation using the EM algorithm, the structure of the algorithm, and the properties of the maximum likelihood estimators are investigated. This includes simulation studies using the ns (network simulator) to obtain realistic network traffic. The optimal design of probing experiments is also studied. Finally, application of the results to network monitoring is briefly illustrated. KEY WORDS: EM algorithm; Inference on graphs; Network modeling; Network monitoring; Network tomography; Probing experiments.