Fast Parameter Estimation in Loss Tomography for Networks of General Topology

Ke Deng, Yang Li, Weiping Zhu, Jun S. Liu

Abstract: Loss tomography is a vital technique for investigating link-level loss rates with low operational cost. While various methods exist for tree and general topologies, they often suffer from high computational costs. This paper introduces novel statistics and alternative parameter systems, revealing that the likelihood function for both tree and general topologies shares the same mathematical formulation. By re-parameterizing the likelihood function into the standard exponential family, the authors develop new algorithms—LE-$\xi$ and PCEM—that achieve the Maximum Likelihood Estimate (MLE) with significantly improved computational efficiency, reaching speedups of up to 2,000x over traditional methods.

Introduction

Network loss tomography allows administrators to infer internal link performance by analyzing end-to-end probe data. This is essential when internal routers are inaccessible or belong to different administrative domains. While inference on simple tree structures is well-established, real-world "general" topologies—characterized by multiple sources and complex, overlapping paths—present a much harder computational problem.

The Challenge of Network Tomography

The primary goal of loss tomography is to estimate the loss rate of individual links based on whether probes sent from sources reach their intended receivers. In a tree topology, the path from a source to any receiver is unique. However, in general topologies, paths can intersect in complex ways, making the likelihood function difficult to solve.

A typical tree topology used in network loss tomography, where $\theta_i$ represents the success probability of link $i$.

Historically, methods for general topologies were either "expensive" (slow to converge) or "wasteful" (ignoring useful data). The breakthrough presented here lies in recognizing that the underlying mathematical structure of these complex networks is identical to that of simple trees.

Methodology and Mathematical Innovations

The authors propose three key innovations to achieve fast and accurate parameter estimation:

  1. Internal View Statistics: They defined a set of "complete and minimal sufficient statistics" ($n_i(1), n_i(0)$). These statistics capture all necessary information regarding probe success and failure at each link, eliminating redundant data processing.
  2. Exponential Family Re-parametrization: By transforming the link loss rate ($\theta$) into alternative systems ($\xi$ and $\psi$), the researchers proved that the likelihood function belongs to the standard exponential family. This ensures the function is convex and has a unique global maximum, guaranteeing that algorithms will find the true MLE.
  3. Novel Algorithms:
    • LE-$\xi$ (Likelihood-Equation-based): This algorithm solves likelihood equations locally at each node, allowing for parallel computation.
  4. PCEM (Pattern-Collapsed EM): A highly optimized Expectation-Maximization algorithm. While naive EM complexity grows exponentially with network size ($O(n2^m)$), PCEM reduces this to linear complexity ($O(m)$).

Performance Evaluation

The algorithms were tested using synthetic datasets sampled from Beta distributions and realistic traffic simulations in ns-2 (Network Simulator 2), which included complex TCP/UDP cross-traffic.

The results demonstrate a massive leap in efficiency. In a 5-layer network test, the "Naive" EM algorithm (NEM) took over 90,000 milliseconds. The proposed PCEM and LE-$\xi$ algorithms completed the same task in just 25 and 28 milliseconds, respectively—a ~2,000x speedup. Furthermore, these methods maintained perfect accuracy, matching the MLE and outperforming heuristic approaches like the Minimum Variance Weighted Average (MVWA).

Conclusion

This work reveals that the mathematical nature of loss tomography is invariant across different network topologies. By leveraging the properties of the exponential family, the authors have developed algorithms that are both theoretically sound and practically efficient. These methods scale linearly, making them suitable for the massive, complex networks of the modern internet. Future research may extend these techniques to other performance metrics like delay and jitter.

Summary updated

Abstract

As a technique to investigate link-level loss rates of a computer network with low operational cost, loss tomography has received considerable attentions in recent years. A number of parameter estimation methods have been proposed for loss tomography of networks with a tree structure as well as a general topological structure. However, these methods suffer from either high computational cost or insufficient use of information in the data. In this paper, we provide both theoretical results and practical algorithms for parameter estimation in loss tomography. By introducing a group of novel statistics and alternative parameter systems, we find that the likelihood function of the observed data from loss tomography keeps exactly the same mathematical formulation for tree and general topologies, revealing that networks with different topologies share the same mathematical nature for loss tomography. More importantly, we discover that a re-parametrization of the likelihood function belongs to the standard exponential family, which is convex and has a unique mode under regularity conditions. Based on these theoretical results, novel algorithms to find the MLE are developed. Compared to existing methods in the literature, the proposed methods enjoy great computational advantages.
BibTeX
@article{deng2016fast,
  author = {Ke Deng and Yang Li and Weiping Zhu and Jun S. Liu},
  title = {{Fast Parameter Estimation in Loss Tomography for Networks of General Topology}},
  journal = {The Annals of Applied Statistics},
  year = {2016},
  doi = {10.1214/15-aoas883},
}
Figure