Computer Science

Super spreader edentification using geometric-min filter

Document Type

Article

Abstract

Super spreader identification has a lot of applications in network management and security monitoring. It is a more difficult problem than heavy hitter identification because flow spread is harder to measure than flow size due to the requirement of duplicate removal. The prior work either incurs heavy memory overhead or requires heavy computations. This paper designs a new super-spreader monitor capable of identifying all flows whose spreads are greater than a user-specified threshold with a probability that can be arbitrarily set. It introduces a generalized geometric hash function, a generalized geometric counter, and a novel geometric-min filter that blocks out the vast majority of small/medium flows from being tracked, allowing us to focus on a small number of flows in which super spreaders are identified. We provide an analytical way of properly setting the system threshold to meet probabilistically guaranteed identification of super spreaders, and implement it on both hardware (FPGA) and software platforms. We perform extensive experiments based on real Internet traffic traces from CAIDA. The results show that with proper parameter settings, the new monitor can identify more than 99% super spreaders with a low memory requirement, better than the prior art.

Publication Title

IEEE/ACM Transactions on Networking

Publication Date

2022

Volume

30

Issue

1

First Page

299

Last Page

312

ISSN

1063-6692

DOI

10.1109/TNET.2021.3108033

Keywords

super spreader identification, traffic measurement

APA Citation

Ma, C., Chen, S., Zhang, Y., Xiao, Q., & Odegbile, O. O. (2021). Super spreader identification using geometric-min filter. IEEE/ACM Transactions on Networking, 30(1), 299-312.

Link to Full Text

Share

COinS