Loss Tomography from Tree Topologies to General Topologies

Loss tomography has received considerable attention in recent years and a number of estimators based on maximum likelihood (ML) or Bayesian principles have been proposed. Almost all of the estimators are devoted to the tree topology despite the general topology is more common in practice. There has been few likelihood function devoted to the general topology, not to mention the estimator. To overcome this, two sets of sufficient statistics for the tree and general topologies, respectively, are proposed in this paper. Using the statistics, two likelihood functions, one for a topology, are proposed here and subsequently two likelihood equations for the general topology, one is link-based and the other is path-based, are obtained. In addition, a dependence between subtrees in terms of their estimates is identified for the general topology and a divide-and-conquer strategy is proposed to deal with the dependence, which divides a general network into two types of independent trees. Further, two algorithms, one for a type of the independent trees, are proposed to estimate the loss rates of each type.