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.
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:
- ISP: Traffic from a major European ISP (2006) featuring "triple-play" services.
- Campus: A 2008 trace from the University of Brescia representing LAN/Internet egress.
- 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.
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