Abstract: In today's high-speed networks, it is becoming increasingly challenging for network managers to understand the nature of the traffic carried in their networks. A major problem for traffic analysis is extracting a concise yet accurate summary of relevant aggregate traffic flows from network traces. This paper presents two summarization techniques designed to minimize the size of traffic flow reports generated by a hierarchical cluster analysis tool. By analyzing the accuracy and compaction gain of our approach on a standard benchmark dataset, we demonstrate that our approach achieves more accurate summaries than those of existing tools based on frequent itemset mining.
Introduction
In the environment of high-speed networking, administrators are often overwhelmed by the sheer volume of data. Every connection, or "flow," generates a record. During events like Distributed Denial of Service (DDoS) attacks or massive network scans, a single incident can trigger thousands of near-identical log entries. Manually analyzing these logs is impossible, and storing them in their raw form is prohibitively expensive.
Existing tools often rely on "Top-K" lists (e.g., the top 10 most active IP addresses), which are frequently ad-hoc and miss the "long tail" of smaller flows that collectively represent a significant portion of traffic. The challenge lies in creating a summary that is both compact (containing few entries) and accurate (preserving the essential characteristics of the original data).
The Echidna Framework
The researchers developed their approach using a tool called Echidna, which utilizes a hierarchical clustering algorithm. The pipeline operates as follows:
- Data Representation: Network traffic is treated as a 6-tuple: Source IP, Destination IP, Protocol, Source Port, Destination Port, and Byte count. The system treats IP addresses hierarchically (using prefixes) and ports categorically (grouping them into "Well Known," "Registered," or "High" ports).
- Cluster Feature (CF) Tree: As data flows into the system, Echidna builds a tree where each node represents a cluster of similar flows.
- Summarization Strategies: The core contribution of this work is the development of two methods to "prune" this tree into a readable report:
- Summarization by Size: This method reports only those clusters containing a number of records above a specific threshold ($T_r$).
- Summarization by Homogeneity: This novel technique uses a ratio of Maximum Intra-cluster (MI) distance to Average Intra-cluster (AI) distance. If a cluster is sufficiently "tight" or homogeneous, the algorithm stops and reports the aggregate. If it is "loose" (e.g., bimodal), the algorithm drills down into sub-clusters to provide more granular detail.
Key Insights: Why Homogeneity Matters
The study's most significant finding is that pruning by homogeneity—measuring how similar the flows are—is far more effective than pruning simply by size. This approach prevents reports from being cluttered with redundant sub-clusters that do not provide new information.
As shown in the classification tests, the homogeneity-based summary achieved higher Area Under the Curve (AUC) values in distinguishing between attack and normal traffic across all report sizes compared to size-based summarization. Furthermore, the researchers observed a "More is Better" paradox: larger input datasets actually led to lower information loss for a fixed report size. With more data, hierarchical clusters become more stable and representative, leading to superior generalizations.
Performance Comparison
The researchers evaluated their approach using the 1998 DARPA Intrusion Detection dataset. They compared Echidna against AutoFocus, a well-known tool based on frequent itemset mining.
Echidna consistently produced reports with lower information loss for the same level of "compaction gain" (the ratio of raw records to summary entries). Unlike frequent itemset mining, which treats features as independent, the hierarchical approach respects the inherent structure of network data (such as IP subnets), making the resulting summaries more intuitive for network administrators. Additionally, the hierarchical approach is computationally efficient, avoiding the heavy memory overhead associated with finding all frequent patterns in massive transactional datasets.
Conclusion and Future Work
While the results demonstrate that hierarchical clustering—particularly when guided by homogeneity—is a powerful tool for network summarization, several avenues for future research remain. The study utilized empirical testing to establish thresholds (such as $T_c = 1.3$ for homogeneity); however, real-world dynamic networks may require adaptive thresholds. Furthermore, as modern traffic becomes increasingly encrypted (HTTPS/TLS), the utility of port-based categorization may need to be re-evaluated in the context of contemporary network benchmarks.
Reference: Mahmood, A., Leckie, C., and Udaya, P. (2009). Creating Concise Summaries of Network Traffic Using Hierarchical Clustering. Bangladesh J. Sci. Ind. Res. 44(3), 281-288.
Summary updated