Reverse Hashing for Sketch-based Change Detection on High-speed Networks

With the ever-increasing link speeds and traffic volumes of the Internet, monitoring and analyzing network traffic usage becomes a challenging but essential service for network administrators of large ISPs or institutions. There are two popular primitives for efficient analysis over massive data streams: heavy hitter detection and heavy change detection. Although numerous approaches have been proposed for efficient heavy hitter detection [1], [2], [3], [4], [5], the sketch-based scheme [6] is one of the very few that can detect heavy changes and anomalies over massive data streams at network traffic speeds. However, sketches do not preserve keys (e.g., source IP address) of the flows. Thus even if anomalies are detected, it is difficult to infer the culprit flows. To address this challenge, we propose efficient reversible hashing schemes to infer the keys of culprit flows from sketches with negligible extra memory and few extra memory accesses for recording streaming data implementing on a single FPGA board, we can achieve a throughput of over 16Gbps for all 40-byte-packet streams (the worst case traffic). Meanwhile, the heavy change detection daemon runs in the background with space complexity and computational time sublinear to the key space size. Evaluation with traces from a large edge router show that we can infer the keys for even 1,000 heavy changes while achieving over a 99% real positive percentage and less than a 0.5% false positive percentage in 22 seconds.