Avoiding Flow Size Overestimation in the Count-Min Sketch with Bloom Filter Constructions

e-Archivo Repository

Show simple item record

dc.contributor.author Rottenstreich, Ori
dc.contributor.author Reviriego Vasallo, Pedro
dc.contributor.author Porat, Ely
dc.contributor.author Muthukrishnan, S.
dc.date.accessioned 2021-09-13T11:18:34Z
dc.date.available 2021-09-13T11:18:34Z
dc.date.issued 2021-09
dc.identifier.bibliographicCitation Rottenstreich, O., Reviriego, P., Porat, E. & Muthukrishnan, S. (2021). Avoiding Flow Size Overestimation in Count-Min Sketch With Bloom Filter Constructions. IEEE Transactions on Network and Service Management, 18(3), pp. 3662–3676.
dc.identifier.issn 1932-4537
dc.identifier.uri http://hdl.handle.net/10016/33264
dc.description.abstract The Count-Min sketch is the most popular data structure for flow size estimation, a basic measurement task required in many networks. Typically the number of potential flows is large, eliminating the possibility to maintain a counter per flow within memory of high access rate. The Count-Min sketch is probabilistic and relies on mapping each flow to multiple counters through hashing. This implies potential estimation error such that the size of a flow is overestimated when all flow counters are shared with other flows with observed traffic. Although the error in the estimation can be probabilistically bounded, many applications can benefit from accurate flow size estimation and the guarantee to completely avoid overestimation. We describe a design of the Count-Min sketch with accurate estimations whenever the number of flows with observed traffic follows a known bound, regardless of the identity of these particular flows. We make use of a concept of Bloom filters that avoid false positives and indicate the limitations of existing Bloom filter designs towards accurate size estimation. We suggest new Bloom filter constructions that allow scalability with the support for a larger number of flows and explain how these can imply the unique guarantee of accurate flow size estimation in the well known Count-Min sketch.
dc.description.sponsorship Ori Rottenstreich was partially supported by the German-Israeli Foundation for Scientic Research and Development (GIF), by the Gordon Fund for System Engineering as well as by the Technion Hiroshi Fujiwara Cyber Security Research Center and the Israel National Cyber Directorate. Pedro Reviriego would like to acknowledge the sup-port of the ACHILLES project PID2019-104207RB-I00 and the Go2Edge network RED2018-102585-T funded by the Spanish Ministry of Science and Innovation and of the Madrid Community research project TAPIR-CM grant no. P2018/TCS-4496.
dc.format.extent 15
dc.language.iso eng
dc.publisher IEEE
dc.rights © 2021, IEEE
dc.subject.other Network algorithms
dc.subject.other Measurement
dc.subject.other Bloom filter
dc.subject.other Count-Min Sketch
dc.title Avoiding Flow Size Overestimation in the Count-Min Sketch with Bloom Filter Constructions
dc.type article
dc.subject.eciencia Telecomunicaciones
dc.identifier.doi https://doi.org/10.1109/TNSM.2021.3068604
dc.rights.accessRights openAccess
dc.relation.projectID Gobierno de España. PID2019-104207RB-I00
dc.relation.projectID Gobierno de España. RED2018-102585-T
dc.relation.projectID Comunidad de Madrid. P2018/TCS-4496
dc.type.version acceptedVersion
dc.identifier.publicationfirstpage 3662
dc.identifier.publicationissue 3
dc.identifier.publicationlastpage 3676
dc.identifier.publicationtitle IEEE Transactions on Network and Service Management
dc.identifier.publicationvolume 18
dc.identifier.uxxi AR/0000027526
dc.contributor.funder Comunidad de Madrid
dc.contributor.funder Ministerio de Ciencia, Innovación y Universidades (España)
dc.affiliation.dpto UC3M. Departamento de Ingeniería Telemática
dc.affiliation.grupoinv UC3M. Grupo de Investigación: Network Technologies
 Find Full text

Files in this item

*Click on file's image for preview. (Embargoed files's preview is not supported)

This item appears in the following Collection(s)

Show simple item record