TL;DR
This paper introduces Flowyager, a system designed to answer complex, unknown network-wide queries in seconds. It achieves this by using a novel, space-efficient data structure called "Flowtrees" to summarize raw network flow data, enabling interactive exploration and drill-down capabilities for network operators.
What Problem Does This Paper Address?
Network operators constantly need to monitor their networks for various reasons, from capacity planning to identifying and mitigating security threats like DDoS attacks. While routers collect flow records, querying this massive, distributed data from hundreds of devices across different sites and time periods is a significant challenge. Existing solutions often require knowing the exact query beforehand, are computationally expensive, or demand specialized hardware, making interactive, ad-hoc exploration of network-wide issues difficult and time-consuming. This paper aims to bridge this gap by providing a system that can answer arbitrary, previously unknown network-wide queries quickly and efficiently.
Methods
Flowyager's core innovation lies in its use of Flowtrees, a novel, self-adjusting data structure that acts as a compressed summary of raw flow data. Flowtrees are built upon hierarchical heavy hitter (HHH) concepts, allowing them to efficiently represent popular network flows while drastically reducing storage and transfer requirements (75-95% reduction compared to raw data). Flowyager also introduces FlowQL, an SQL-inspired query language that enables users to express complex, ad-hoc queries. The system architecture comprises:
- FlowAGG: Ingests raw flow captures and generates Flowtrees.
- FlowDB: Stores and indexes Flowtrees, serving as the backend for query processing.
- FlowQL: The query interface that allows users to interact with FlowDB.
Key Flowtree operators like merge, compress, and diff are crucial for aggregating data across time and space, and for detecting changes.
Datasets
The paper reports on experiments conducted using data from three sources:
- IXP (Internet Exchange Point): IPFIX flow captures from a large European IXP, spanning a week and representing about 10TB of data.
- ISP (Internet Service Provider): NetFlow streams from a tier-1 ISP, covering 30 cities across four European countries and the US, totaling approximately 25TB of data over two days.
- MAWI Dataset: Packet-level captures from a 1 Gbps link, used for reproducibility and testing.
Key Insights and Ideas
- Flowtrees are highly efficient: The novel Flowtree data structure achieves significant space savings (up to 97% compression) by summarizing flow data, making it practical to store and transfer.
- Interactive, ad-hoc querying is crucial: Network operators often don't know the exact problem or query beforehand. Flowyager's ability to answer arbitrary queries in seconds enables true interactive exploration.
- HHH concepts are adaptable: The paper demonstrates how hierarchical heavy hitter principles can be extended and generalized to create a flexible data structure for network flow analysis.
- Trade-offs in granularity: Using higher granularity Flowtrees (e.g., 15-minute bins) leads to faster query response times, highlighting the importance of choosing the right aggregation level.
Key Results
- Query Response Time: Flowyager reduces query response times from hours or minutes to seconds, enabling interactive exploration. For example, some queries are answered in under 5 seconds.
- Space Efficiency: Flowtrees achieve space savings of 89-99.5% compared to raw or compressed flow data.
- Accuracy: Flowyager demonstrates high accuracy for common queries, with median ARE values below 0.0002 and F1 scores well above 0.9 for many feature sets.
- Performance Comparison: Flowyager significantly outperforms big data analytics platforms like Spark and ClickHouse in query response times for network management tasks.
- Deployment Experience: The system was successfully deployed and tested in real-world environments (IXP and ISP), demonstrating its practical applicability.
Limitations and Future Work
- Estimates, not exact values: Flowyager provides estimates, which are accurate but not exact. For absolute precision, combining Flowyager with tools like ClickHouse for focused analysis is suggested.
- Implementation Challenges: Handling unsynchronized router clocks and potential misbinning due to network delay were noted.
- Future Work: The authors suggest exploring more advanced queries, such as detecting "slow" DDoS attacks, and further optimizing the system for even larger-scale deployments. They also plan to make Flowyager publicly available for non-commercial use.
Summary updated