FaRNet: fast recognition of high multi-dimensional network traffic patterns

Ignasi Paredes-Oliva, Pere Barlet-Ros, Xenofontas A. DimitropoulosSigmetrics 2013 · DOI

TL;DR

This paper introduces FaRNet, a novel system for efficiently identifying complex patterns in high-dimensional network traffic data. By leveraging generalized frequent item-set mining, FaRNet significantly outperforms existing methods like AutoFocus in speed and scalability, enabling near real-time traffic analysis.

What Problem Does This Paper Address?

Understanding network traffic is crucial for various reasons, including capacity planning, troubleshooting, and identifying emerging threats. A key technique for this is "traffic profiling," which involves identifying "heavy hitters" – the most significant traffic flows based on multiple attributes (dimensions). However, existing methods for finding these multi-dimensional heavy hitters struggle with the sheer volume and complexity of modern network data. They are computationally expensive, don't scale well to a large number of dimensions, and are difficult to extend with new traffic features. This limits their practical application in rapidly evolving network environments.

Methods

FaRNet's core innovation lies in its use of generalized frequent item-set mining (FIM). Unlike traditional FIM, generalized FIM can handle hierarchical attributes, which are common in network data (e.g., IP addresses can be represented by prefixes of varying lengths).

The paper proposes a new algorithm called Progressive Expansion k-by-k (PEK) to efficiently handle these hierarchical attributes. PEK works by expanding attributes in "chunks" (k bits at a time) rather than one bit at a time, significantly reducing redundant computations. It intelligently prunes branches of the hierarchy that are unlikely to yield frequent item-sets, based on the "downward-closure property" of frequent item-sets. This approach allows FaRNet to analyze traffic data with both flat and hierarchical attributes, and it scales well with the number of dimensions.

Datasets

The evaluation uses NetFlow traffic data from the European backbone network of GÉANT from 2011. The specific dataset used for evaluation is 15 minutes long, containing 0.51 million flows, 5.46 million packets, and 5.55 billion bytes. The authors note that for their comparison with AutoFocus, they only used the first 10,000 flows because the available implementation of AutoFocus could not accurately process larger volumes.

Key Insights and Ideas

  • Hierarchical Data is Key: Network traffic attributes like IP addresses are inherently hierarchical. Treating them as flat attributes misses valuable patterns and leads to computational inefficiency.
  • FIM as a Powerful Tool: Generalized FIM provides a robust and scalable framework for extracting complex patterns from multi-dimensional data, especially when combined with hierarchical attributes.
  • The Power of Chunking: The PEK algorithm's approach of expanding attributes in k-bit chunks is a clever optimization that drastically reduces the computational burden compared to bit-by-bit expansion.
  • Scalability Matters: Existing tools like AutoFocus are limited by their exponential computational overhead with increasing dimensions. FaRNet's design directly addresses this limitation, making it suitable for the high-dimensional nature of modern network traffic.

Key Results

FaRNet demonstrates a significant performance improvement over AutoFocus:

  • Speed: FaRNet is up to three orders of magnitude faster than AutoFocus when analyzing the 5-tuple (source IP, destination IP, source port, destination port, protocol).
  • Scalability: While AutoFocus's execution time increases exponentially with the minimum support threshold (s), FaRNet handles it smoothly. For a minimum support of 0.1%, FaRNet is approximately three orders of magnitude faster (0.48s vs. 223s).
  • Memory Usage: FaRNet generally uses less memory than AutoFocus, especially for lower minimum support thresholds. For s = 0.1%, FaRNet consumes 7.79 MB compared to AutoFocus's 88.77 MB. However, for s > 1%, AutoFocus uses less memory.

Limitations and Future Work

  • Memory Trade-off: FaRNet uses more memory than AutoFocus for minimum support thresholds above 1%. The authors note that FaRNet's memory consumption is still reasonably low (below 10 MB) even in the worst case.
  • Future Work: The paper focuses on IP addresses for hierarchical attribute handling. The authors suggest that their proposed methods are applicable to other hierarchical features and that further exploration of these is warranted. The paper also implies that FaRNet's ability to handle more dimensions and its speed make it suitable for near real-time analysis, a direction for future work.

Summary updated

BibTeX
@inproceedings{paredesoliva2013farnet,
  author = {Ignasi Paredes-Oliva and Pere Barlet-Ros and Xenofontas A. Dimitropoulos},
  title = {{FaRNet: fast recognition of high multi-dimensional network traffic patterns}},
  booktitle = {Sigmetrics},
  year = {2013},
  doi = {10.1145/2465529.2465743},
}
Figure