Reversible sketches for efficient and accurate change detection over network data streams

Robert Schweller*, Ashish Gupta, Elliot Parsons, Yan Chen

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

96 Scopus citations

Abstract

Traffic anomalies such as failures and attacks are increasing in frequency and severity, and thus identifying them rapidly and accurately is critical for large network operators. The detection typically treats the traffic as a collection of flows and looks for heavy changes in traffic patterns (e.g., volume, number of connections). However, as link speeds and the number of flows increase, keeping per-flow state is not scalable. The recently proposed sketch-based schemes [14] are among the very few that can detect heavy changes and anomalies over massive data streams at network traffic speeds. However, sketches do not preserve the key (e.g., source IP address) of the flows. Hence, even if anomalies are detected, it is difficult to infer the culprit flows, making it a big practical hurdle for online deployment. Meanwhile, the number of keys is too large to record. To address this challenge, we propose efficient reversible hashing algorithms to infer the keys of culprit flows from sketches without storing any explicit key information. No extra memory or memory accesses are needed for recording the streaming data. Meanwhile, the heavy change detection daemon runs in the background with space complexity and computational time sublinear to the key space size. This short paper describes the conceptual framework of the reversible sketches, as well as some initial approaches for implementation. See [23] for the optimized algorithms in details. Evaluated with netflow traffic traces of a large edge router, we demonstrate that the reverse hashing can quickly infer the keys of culprit flows even for many changes with high accuracy.

Original languageEnglish (US)
Title of host publicationProceedings of the 2004 ACM SIGCOMM Internet Measurement Conference, IMC 2004
PublisherAssociation for Computing Machinery (ACM)
Pages207-212
Number of pages6
ISBN (Print)1581138210, 9781581138214
DOIs
StatePublished - 2004
EventProceedings of the 2004 ACM SIGCOMM Internet Measurement Conference, IMC 2004 - Taormina, Italy
Duration: Oct 25 2004Oct 27 2004

Publication series

NameProceedings of the 2004 ACM SIGCOMM Internet Measurement Conference, IMC 2004

Other

OtherProceedings of the 2004 ACM SIGCOMM Internet Measurement Conference, IMC 2004
CountryItaly
CityTaormina
Period10/25/0410/27/04

Keywords

  • Change detection
  • Data stream computation
  • IP mangling
  • Modular hashing
  • Network anomaly detection
  • Reverse hashing
  • Sketch

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Reversible sketches for efficient and accurate change detection over network data streams'. Together they form a unique fingerprint.

Cite this