Reverse hashing for high-speed network monitoring: Algorithms, evaluation, and applications

Robert Schweller*, Zhichun Li, Yan Chen, Yan Gao, Ashish Gupta, Yin Zhangf, Peter A Dinda, Ming-Yang Kao, Gokhan Memik

*Corresponding author for this work

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

27 Citations (Scopus)

Abstract

A key function for network traffic monitoring and analysis is the ability to perform aggregate queries over multiple data streams. Change detection is an important primitive which can be extended to construct many aggregate queries. The recently proposed sketches [1] are among the very few that can detect heavy changes online for high speed links, and thus support various aggregate queries in both temporal and spatial domains. However, it does not preserve the keys (e.g., source IP address) of flows, making it difficult to reconstruct the desired set of anomalous keys. In an earlier abstract we proposed a framework for a reversible sketch data structure that offers hope for efficient extraction of keys [2]. However, this scheme is only able to detect a single heavy change key and places restrictions on the statistical properties of the key space. To address these challenges, we propose an efficient reverse hashing scheme to infer the keys of culprit flows from reversible sketches. There are two phases. The first operates online, recording the packet stream in a compact representation with negligible extra memory and few extra memory accesses. Our prototype single FPGA board implementation can achieve a throughput of over 16 Gbps for 40-byte-packet streams (the worst case). The second phase identifies heavy changes and their keys from the representation in nearly real time. We evaluate our scheme using traces from large edge routers with OC-12 or higher links. Both the analytical and experimental results show that we are able to achieve online traffic monitoring and accurate change/intrusion detection over massive data streams on high speed links, all in a manner that scales to large key space size. To the best of our knowledge, our system is the first to achieve these properties simultaneously.

Original languageEnglish (US)
Title of host publicationProceedings - INFOCOM 2006
Subtitle of host publication25th IEEE International Conference on Computer Communications
DOIs
StatePublished - Dec 1 2006
EventINFOCOM 2006: 25th IEEE International Conference on Computer Communications - Barcelona, Spain
Duration: Apr 23 2006Apr 29 2006

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Other

OtherINFOCOM 2006: 25th IEEE International Conference on Computer Communications
CountrySpain
CityBarcelona
Period4/23/064/29/06

Fingerprint

HIgh speed networks
Monitoring
Data storage equipment
Intrusion detection
Routers
Data structures
Field programmable gate arrays (FPGA)
Throughput

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Cite this

Schweller, R., Li, Z., Chen, Y., Gao, Y., Gupta, A., Zhangf, Y., ... Memik, G. (2006). Reverse hashing for high-speed network monitoring: Algorithms, evaluation, and applications. In Proceedings - INFOCOM 2006: 25th IEEE International Conference on Computer Communications [4146856] (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFOCOM.2006.203
Schweller, Robert ; Li, Zhichun ; Chen, Yan ; Gao, Yan ; Gupta, Ashish ; Zhangf, Yin ; Dinda, Peter A ; Kao, Ming-Yang ; Memik, Gokhan. / Reverse hashing for high-speed network monitoring : Algorithms, evaluation, and applications. Proceedings - INFOCOM 2006: 25th IEEE International Conference on Computer Communications. 2006. (Proceedings - IEEE INFOCOM).
@inproceedings{8955e85bca8045a29cc039c59191c19b,
title = "Reverse hashing for high-speed network monitoring: Algorithms, evaluation, and applications",
abstract = "A key function for network traffic monitoring and analysis is the ability to perform aggregate queries over multiple data streams. Change detection is an important primitive which can be extended to construct many aggregate queries. The recently proposed sketches [1] are among the very few that can detect heavy changes online for high speed links, and thus support various aggregate queries in both temporal and spatial domains. However, it does not preserve the keys (e.g., source IP address) of flows, making it difficult to reconstruct the desired set of anomalous keys. In an earlier abstract we proposed a framework for a reversible sketch data structure that offers hope for efficient extraction of keys [2]. However, this scheme is only able to detect a single heavy change key and places restrictions on the statistical properties of the key space. To address these challenges, we propose an efficient reverse hashing scheme to infer the keys of culprit flows from reversible sketches. There are two phases. The first operates online, recording the packet stream in a compact representation with negligible extra memory and few extra memory accesses. Our prototype single FPGA board implementation can achieve a throughput of over 16 Gbps for 40-byte-packet streams (the worst case). The second phase identifies heavy changes and their keys from the representation in nearly real time. We evaluate our scheme using traces from large edge routers with OC-12 or higher links. Both the analytical and experimental results show that we are able to achieve online traffic monitoring and accurate change/intrusion detection over massive data streams on high speed links, all in a manner that scales to large key space size. To the best of our knowledge, our system is the first to achieve these properties simultaneously.",
author = "Robert Schweller and Zhichun Li and Yan Chen and Yan Gao and Ashish Gupta and Yin Zhangf and Dinda, {Peter A} and Ming-Yang Kao and Gokhan Memik",
year = "2006",
month = "12",
day = "1",
doi = "10.1109/INFOCOM.2006.203",
language = "English (US)",
isbn = "1424402212",
series = "Proceedings - IEEE INFOCOM",
booktitle = "Proceedings - INFOCOM 2006",

}

Schweller, R, Li, Z, Chen, Y, Gao, Y, Gupta, A, Zhangf, Y, Dinda, PA, Kao, M-Y & Memik, G 2006, Reverse hashing for high-speed network monitoring: Algorithms, evaluation, and applications. in Proceedings - INFOCOM 2006: 25th IEEE International Conference on Computer Communications., 4146856, Proceedings - IEEE INFOCOM, INFOCOM 2006: 25th IEEE International Conference on Computer Communications, Barcelona, Spain, 4/23/06. https://doi.org/10.1109/INFOCOM.2006.203

Reverse hashing for high-speed network monitoring : Algorithms, evaluation, and applications. / Schweller, Robert; Li, Zhichun; Chen, Yan; Gao, Yan; Gupta, Ashish; Zhangf, Yin; Dinda, Peter A; Kao, Ming-Yang; Memik, Gokhan.

Proceedings - INFOCOM 2006: 25th IEEE International Conference on Computer Communications. 2006. 4146856 (Proceedings - IEEE INFOCOM).

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

TY - GEN

T1 - Reverse hashing for high-speed network monitoring

T2 - Algorithms, evaluation, and applications

AU - Schweller, Robert

AU - Li, Zhichun

AU - Chen, Yan

AU - Gao, Yan

AU - Gupta, Ashish

AU - Zhangf, Yin

AU - Dinda, Peter A

AU - Kao, Ming-Yang

AU - Memik, Gokhan

PY - 2006/12/1

Y1 - 2006/12/1

N2 - A key function for network traffic monitoring and analysis is the ability to perform aggregate queries over multiple data streams. Change detection is an important primitive which can be extended to construct many aggregate queries. The recently proposed sketches [1] are among the very few that can detect heavy changes online for high speed links, and thus support various aggregate queries in both temporal and spatial domains. However, it does not preserve the keys (e.g., source IP address) of flows, making it difficult to reconstruct the desired set of anomalous keys. In an earlier abstract we proposed a framework for a reversible sketch data structure that offers hope for efficient extraction of keys [2]. However, this scheme is only able to detect a single heavy change key and places restrictions on the statistical properties of the key space. To address these challenges, we propose an efficient reverse hashing scheme to infer the keys of culprit flows from reversible sketches. There are two phases. The first operates online, recording the packet stream in a compact representation with negligible extra memory and few extra memory accesses. Our prototype single FPGA board implementation can achieve a throughput of over 16 Gbps for 40-byte-packet streams (the worst case). The second phase identifies heavy changes and their keys from the representation in nearly real time. We evaluate our scheme using traces from large edge routers with OC-12 or higher links. Both the analytical and experimental results show that we are able to achieve online traffic monitoring and accurate change/intrusion detection over massive data streams on high speed links, all in a manner that scales to large key space size. To the best of our knowledge, our system is the first to achieve these properties simultaneously.

AB - A key function for network traffic monitoring and analysis is the ability to perform aggregate queries over multiple data streams. Change detection is an important primitive which can be extended to construct many aggregate queries. The recently proposed sketches [1] are among the very few that can detect heavy changes online for high speed links, and thus support various aggregate queries in both temporal and spatial domains. However, it does not preserve the keys (e.g., source IP address) of flows, making it difficult to reconstruct the desired set of anomalous keys. In an earlier abstract we proposed a framework for a reversible sketch data structure that offers hope for efficient extraction of keys [2]. However, this scheme is only able to detect a single heavy change key and places restrictions on the statistical properties of the key space. To address these challenges, we propose an efficient reverse hashing scheme to infer the keys of culprit flows from reversible sketches. There are two phases. The first operates online, recording the packet stream in a compact representation with negligible extra memory and few extra memory accesses. Our prototype single FPGA board implementation can achieve a throughput of over 16 Gbps for 40-byte-packet streams (the worst case). The second phase identifies heavy changes and their keys from the representation in nearly real time. We evaluate our scheme using traces from large edge routers with OC-12 or higher links. Both the analytical and experimental results show that we are able to achieve online traffic monitoring and accurate change/intrusion detection over massive data streams on high speed links, all in a manner that scales to large key space size. To the best of our knowledge, our system is the first to achieve these properties simultaneously.

UR - http://www.scopus.com/inward/record.url?scp=34249780184&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34249780184&partnerID=8YFLogxK

U2 - 10.1109/INFOCOM.2006.203

DO - 10.1109/INFOCOM.2006.203

M3 - Conference contribution

AN - SCOPUS:34249780184

SN - 1424402212

SN - 9781424402212

T3 - Proceedings - IEEE INFOCOM

BT - Proceedings - INFOCOM 2006

ER -

Schweller R, Li Z, Chen Y, Gao Y, Gupta A, Zhangf Y et al. Reverse hashing for high-speed network monitoring: Algorithms, evaluation, and applications. In Proceedings - INFOCOM 2006: 25th IEEE International Conference on Computer Communications. 2006. 4146856. (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFOCOM.2006.203