Minimizing Noise in HyperLogLog-Based Spread Estimation of Multiple Flows

Dinh Nguyen Dao, Rhongho Jang, Changhun Jung, David Mohaisen, Dae Hun Nyang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

Cardinality estimation has become an essential building block of modern network monitoring systems due to the increasing concerns of cyberattacks (e.g., Denial-of-Service, worm, spammer, scanner, etc.). However, the ever-increasing attack scale and the diversity of patterns (i.e., flow size distribution) will produce a biased estimation of existing solutions if apply a monotonic hypothesis for network traffic. The most representative solution is virtual HyperLogLog (vHLL), which extended the proven HLL, a single element cardinality estimation solution, to a multi-tenant version using a memory random sharing and noise elimination approach. In this paper, we show that the assumption made by vHLL's does not work for large-scale network traffic with diverse flow distributions. To resolve the issue, we propose a novel noise elimination method, called Rank Recovery-based Spread Estimator (RRSE), which is tolerant to both attack and normal traffic scenarios while using limited computation and storage. We show that our recovery function is more reliable than state-of-the-art approaches. Moreover, we implemented RRSE in a programmable switch to show the feasibility.

Original languageEnglish
Title of host publicationProceedings - 52nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages331-342
Number of pages12
ISBN (Electronic)9781665416931
DOIs
StatePublished - 2022
Event52nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2022 - Baltimore, United States
Duration: 27 Jun 202230 Jun 2022

Publication series

NameProceedings - 52nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2022

Conference

Conference52nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2022
Country/TerritoryUnited States
CityBaltimore
Period27/06/2230/06/22

Keywords

  • Cardinality Estimation
  • Network Anomaly Detection
  • Programmable Switch
  • Sketch

Fingerprint

Dive into the research topics of 'Minimizing Noise in HyperLogLog-Based Spread Estimation of Multiple Flows'. Together they form a unique fingerprint.

Cite this