Reverse Hashing for Sketch-based Change Detection on High-speed Networks
Robert Schweller, Yan Chen, Elliot Parsons, Ashish Gupta, Gokhan Memik, Yin Zhang⋆ · 2004
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.