TL;DR
This paper introduces Tiresias, an online anomaly detection system designed for hierarchical operational network data. It efficiently identifies high-impact network issues by leveraging the inherent structure of data like customer call logs, achieving over 94% accuracy and discovering previously unknown anomalies.
What Problem Does This Paper Address?
Large Internet Service Providers (ISPs) collect vast amounts of operational data, such as customer care call logs and equipment system logs. This data is crucial for identifying network problems, but its sheer volume and complexity make manual inspection by human operators a daunting and inefficient task. Existing anomaly detection methods often struggle with operational data due to its volatility (rapidly changing arrival rates), sparseness (infrequent events), and the need for fast, online detection, which is incompatible with offline processing or schemes requiring large, stable datasets to converge. The challenge is to automatically and efficiently pinpoint anomalous events within this complex, hierarchical data.
Methods
Tiresias tackles this problem by proposing an automated, online anomaly detection approach that leverages the hierarchical structure of operational data. The core idea is to identify "heavy hitters" – nodes in the hierarchy that represent high-volume aggregates and are thus suspicious locations for anomalies.
Key components of Tiresias include:
- Hierarchical Heavy Hitters (HHH): The system identifies nodes with significant data counts within the hierarchy. It uses a "succinct" definition (SHHH) to avoid redundant reporting of anomalies at multiple levels.
- Online Time Series Construction: Instead of offline processing, Tiresias maintains and updates time series for heavy hitter nodes in an adaptive, online fashion. This is achieved through a novel algorithm called ADA (Adaptive Scheme), which efficiently updates time series by merging or splitting information from previous time steps, significantly reducing computational cost compared to simpler approaches like STA (Strawman Proposal).
- Time Series Analysis and Forecasting: The system employs time series analysis, including seasonality detection (using FFT and à-trous wavelet transform) and forecasting (using the additive Holt-Winters' model), to characterize "typical" behavior and identify deviations.
- Anomaly Detection: Anomalies are detected when actual observed values significantly deviate from forecasted values, using both relative and absolute thresholds to minimize false positives.
Datasets
The paper evaluates Tiresias on two real-world, large-scale operational datasets from a major US broadband provider:
- Customer Care Call Dataset (CCD): This dataset consists of customer care calls related to performance issues, categorized hierarchically.
- Set-Top Box Crash Dataset (SCD): This dataset comprises logs of set-top box crash events, also associated with a hierarchical network path.
These datasets represent a new benchmark for online anomaly detection in hierarchical operational data.
Key Insights and Ideas
- Hierarchy is Key: The hierarchical structure of operational data is not just descriptive but a powerful tool for anomaly detection. By aggregating data at higher levels, Tiresias can identify significant issues that might be obscured by noise at the leaf nodes.
- Online Adaptation is Crucial: Traditional offline anomaly detection methods are insufficient for the dynamic nature of operational data. Tiresias's adaptive online approach (ADA) is essential for real-time detection and efficient resource utilization.
- Heavy Hitters as Anomaly Indicators: Identifying "heavy hitters" in the hierarchy provides a focused set of suspicious locations, significantly reducing the search space for anomalies.
- Splitting and Merging for Efficiency: The ADA algorithm's ability to adapt heavy hitter positions and time series by splitting and merging information is a clever way to handle the dynamic nature of heavy hitters and reduce computational complexity.
- Reference Time Series for Accuracy: Incorporating reference time series for a small number of top-level nodes significantly improves the accuracy of time series estimation, even with complex split operations.
Key Results
- High Accuracy: Tiresias achieves over 94% accuracy in locating anomalies when compared to a reference set verified by an ISP's operational group.
- Efficiency: The ADA algorithm offers significant performance improvements over a strawman approach (STA), with a 14.2x reduction in running time and a 2x reduction in memory usage.
- Discovery of New Anomalies: Tiresias successfully identified several previously unknown anomalies in the ISP's customer care cases, demonstrating its effectiveness beyond simply replicating known issues.
- Scalability: The system is shown to scale to large operational datasets with low computational resource requirements.
- Time Series Accuracy: The use of reference time series (even for just two levels of the hierarchy) reduces time series error to approximately 1%.
Limitations and Future Work
- Data Dependency: Tiresias's effectiveness is inherently tied to the quality and completeness of the operational data it receives. Misclassified customer calls or missing data can impact detection.
- Additive Hierarchy: The current system is designed for additive hierarchical data. More general data representations like directed acyclic graphs are left for future work.
- Detection of Decreases: Tiresias is primarily designed to detect spikes (increases in data rate). It cannot detect anomalies where the data rate abruptly drops (e.g., link outages).
- Future Work: The authors suggest optimizing system parameters based on feedback from ISP operational teams and exploring more general data representations. They also note that while their system is efficient, further improvements in computational efficiency are always desirable.
Summary updated