Sketch-based change detection: Methods, evaluation, and applications

Balachander Krishnamurthy*, Subhabrata Sen, Yin Zhang, Yan Chen

*Corresponding author for this work

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

374 Scopus citations

Abstract

Traffic anomalies such as failures and attacks are commonplace in today's network, and identifying them rapidly and accurately is critical for large network operators. The detection typically treats the traffic as a collection of flows that need to be examined for significant changes in traffic pattern (e.g., volume, number of connections). However, as link speeds and the number of flows increase, keeping per-flow state is either too expensive or too slow. We propose building compact summaries of the traffic data using the notion of sketches. We have designed a variant of the sketch data structure, k-ary sketch, which uses a constant, small amount of memory, and has constant per-record update and reconstruction cost. Its linearity property enables us to summarize traffic at various levels. We then implement a variety of time series forecast models (ARIMA, Holt-Winters, etc.) on top of such summaries and detect significant changes by looking for flows with large forecast errors. We also present heuristics for automatically configuring the model parameters. Using a large amount of real Internet traffic data from an operational tier-1 ISP, we demonstrate that our sketch-based change detection method is highly accurate, and can be implemented at low computation and memory costs. Our preliminary results are promising and hint at the possibility of using our method as a building block for network anomaly detection and traffic measurement.

Original languageEnglish (US)
Title of host publicationProceedings of the 2003 ACM SIGCOMM Internet Measurement Conference, IMC 2003
Pages234-247
Number of pages14
StatePublished - Dec 1 2003
EventProceedings of the 2003 ACM SIGCOMM Internet Measurement Conference, IMC 2003 - Miami Beach, FL, United States
Duration: Oct 27 2003Oct 29 2003

Other

OtherProceedings of the 2003 ACM SIGCOMM Internet Measurement Conference, IMC 2003
Country/TerritoryUnited States
CityMiami Beach, FL
Period10/27/0310/29/03

Keywords

  • Change Detection
  • Data Stream Computation
  • Forecasting
  • Network Anomaly Detection
  • Sketch
  • Time Series Analysis

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint

Dive into the research topics of 'Sketch-based change detection: Methods, evaluation, and applications'. Together they form a unique fingerprint.

Cite this