H-TD Sketch: An H-Shaped Sketch for Identifying Multiple Super Hosts

In ultra-high-speed networks, identifying hosts with high source or destination cardinality, or large cardinality changes, provides compact measurements for network monitoring and security analysis. Currently, schemes for super-host identification have demonstrated good performance, and most of them target one type of super host. However, real networks contain multiple types of super hosts with different distributions. Supporting source cardinalities, destination cardinalities, and inter-cycle changes within one memory-bounded structure requires coordinating measurement and address recovery. To address this challenge, we present H-TD Sketch, a novel sketch structure that enables rapid and accurate identification of multiple super-host types under limited memory constraints by maintaining counts of both source and destination cardinalities. The H-shaped Bloom filter and information groups enable direct traceability of super-host addresses at the end of the measurement cycle. We conduct a theoretical analysis of H-TD Sketch, covering its space and time complexity and the accuracy of its cardinality estimates. We evaluate cardinality estimation and super-host identification on a CPU platform using real-world CAIDA traces. We also integrate H-TD Sketch into Open vSwitch and evaluate its packet-processing throughput using generated traffic. Our experimental findings demonstrate that H-TD Sketch exhibits superior accuracy and performance in both host-cardinality estimation and super-host identification tasks.