Aggregation of Statistical Data from Passive Probes: Techniques and Best Practices

Silvia Colabrese, Dario Rossi, Marco Mellia

Abstract

Passive network monitoring at high speeds or across distributed locations necessitates the aggregation of statistical data from multiple sources. This paper evaluates techniques for reconstructing aggregate statistics, such as percentiles, from local probe data without transferring raw datasets. We demonstrate that Monotonic Spline Interpolation combined with increased quantile density (20 points instead of 10) significantly reduces reconstruction errors in both multi-core and distributed network environments, achieving median errors as low as 0.1%.

Introduction

In modern network environments, passive probes are essential for monitoring performance and security. However, scaling these probes presents two primary challenges. First, the Multi-Core Challenge: high-speed links (10Gbps+) exceed the processing capacity of a single CPU core, requiring traffic to be distributed across multiple cores, each generating local statistics. Second, the Distributed Challenge: obtaining a network-wide view requires data from multiple geographic vantage points. Transferring raw packet logs to a central collector is bandwidth-prohibitive.

The fundamental problem is consolidation: accurately calculating aggregate statistics (e.g., the 90th percentile of latency for the entire network) from intermediate-grain local statistics. Simple averaging is mathematically invalid and leads to significant inaccuracies.

Methodology

The proposed workflow estimates the aggregate Cumulative Distribution Function (CDF) from discrete quantiles gathered from multiple sources.

Workflow for estimating aggregate quantiles from distributed sources.

The process involves several key steps:

  • Interpolation: To fill gaps between known data points, the authors compare Linear (L) interpolation with Monotonic Spline (S) interpolation using Piecewise Cubic Hermite Interpolating Polynomials. The latter ensures a smooth, monotonically increasing curve, which is a requirement for a valid CDF.
  • Information Density: Two levels of input are tested: Single (S), using 10 points, and Double (D), using 20 points to provide a denser map of the distribution.
  • Consolidation: Reconstructed CDFs are weighted by traffic volume and summed. Final aggregate deciles are then extracted using the bisection method.

Datasets

To validate the approach across diverse traffic patterns, three heterogeneous packet traces were used:

  1. ISP: Traffic from a major European ISP (2006) featuring "triple-play" services.
  2. Campus: A 2008 trace from the University of Brescia representing LAN/Internet egress.
  3. Auckland-VI: A public dataset (2001) from the University of Auckland's egress router.

Results and Insights

The study reveals a stark difference between homogeneous and heterogeneous environments.

Comparison of IP packet length distributions in homogeneous (multi-core) vs. heterogeneous (distributed) environments.

Homogeneous vs. Heterogeneous Scaling

Consolidating data across CPU cores (Homogeneous) is relatively straightforward because each core processes a statistically similar slice of traffic. In contrast, distributed locations (Heterogeneous) exhibit wildly varying traffic patterns, making consolidation significantly more difficult.

Key Performance Metrics

  • Multi-core Accuracy: Using the "Spline Double" (SD) method, the median relative error was approximately 0.1%, with a maximum error of 1%. Error growth was found to be logarithmic relative to the number of cores, suggesting excellent hardware scalability.
  • Distributed Accuracy: In heterogeneous environments, the SD method maintained a median error of roughly 1%. While specific "spiky" metrics could reach higher maximum errors, the method remained vastly superior to naive linear strategies which often exceeded 100% error.
  • Data Density vs. Complexity: Doubling the number of input points (from 10 to 20) provided a more significant accuracy boost than switching to a more complex interpolation algorithm, highlighting that data density is a primary driver of accuracy.

Conclusion

Monotonic Spline Interpolation over a dense set of quantiles provides a robust framework for aggregating network statistics. By achieving median errors as low as 0.1% for multi-core systems and 1% for distributed networks, this approach enables accurate large-scale monitoring without the overhead of raw data transfer. Future work will explore integration with Round Robin Databases (RRD) and spatial sampling techniques to further optimize processing overhead.

Summary updated

Abstract

Passive probes continuously generate statistics on large number of metrics, that are possibly represented as probability mass functions (pmf). The need for consolidation of several pmfs arises in two contexts, namely: (i) whenever a central point collects and aggregates measurement of multiple disjoint vantage points, and (ii) whenever a local measurement processed at a single vantage point needs to be distributed over multiple cores of the same physical probe, in order to cope with growing link capacity.
BibTeX
@inproceedings{colabrese2014aggregation,
  author = {Silvia Colabrese and Dario Rossi and Marco Mellia},
  title = {{Aggregation of Statistical Data from Passive Probes: Techniques and Best Practices}},
  booktitle = {TMA},
  year = {2014},
  doi = {10.1007/978-3-642-54999-1\_4},
}
Figure