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.
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:
- 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.
- 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.
- Novel Algorithms:
- LE-$\xi$ (Likelihood-Equation-based): This algorithm solves likelihood equations locally at each node, allowing for parallel computation.
- 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