research-article

BitSense: Universal and Nearly Zero-Error Optimization for Sketch Counters with Compressive Sensing

Authors:

Qun HuangAuthors Info & Claims

ACM SIGCOMM '23: Proceedings of the ACM SIGCOMM 2023 Conference

Pages 220 - 238

https://doi.org/10.1145/3603269.3604865

Published: 01 September 2023 Publication History

Abstract

Sketch algorithms have been widely deployed for network measurement as they achieve high accuracy with restricted resource usage. They store measurement results compactly in fixed-size counters. However, as sketch counters are skewed towards low values, higher bits in most counters remain zero. Such massive unused bits impair the space efficiency valued by sketch algorithms. Unfortunately, efforts to mitigate the issue either apply to specific algorithms or compromise accuracy. In this paper, we design BitSense, a novel optimization framework that integrates with existing sketch algorithms. The key idea is to regard higher bits in sketch counters as a sparse vector and leverage compressive sensing techniques to compress and restore counters. Further, BitSense provides a programming model to help developers easily realize sketch algorithms without dealing with the details of compression and recovery. Bit-Sense proposes an automatic approach for parameter configuration. It theoretically guarantees nearly zero error under the configuration. We have built a BitSense prototype in P4 and a software platform and integrated it with fourteen sketch solutions. Extensive experiments show that BitSense significantly reduces the memory usage of existing sketch solutions by 25%-80% while incurring little overhead and almost zero accuracy drop, outperforming five state-of-the-art optimization frameworks.

References

[1]

Behnaz Arzani, Selim Ciraci, Luiz Chamon, Yibo Zhu, Hongqiang Harry Liu, Jitu Padhye, Boon Thau Loo, and Geoff Outhred. 2018. 007: Democratically finding the cause of packet drops. In Proc. of NSDI. 419--435.

[2]

Behnaz Arzani, Selim Ciraci, Boon Thau Loo, Assaf Schuster, and Geoff Outhred. 2016. Taking the blame game out of data centers operations with netpoirot. In Proc. of SIGCOMM. 440--453.

[3]

Ran Ben Basat, Gil Einziger, Michael Mitzenmacher, and Shay Vargaftik. 2021. SALSA: self-adjusting lean streaming analytics. In Proc. of ICDE. IEEE, 864--875.

[4]

Theophilus Benson, Aditya Akella, and David A Maltz. 2010. Network traffic characteristics of data centers in the wild. In Proc. of ACM IMC. 267--280.

Digital Library

[5]

Burton H Bloom. 1970. Space/time trade-offs in hash coding with allowable errors. Commun. ACM 13, 7 (1970), 422--426.

Digital Library

[6]

Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, and George Varghese. 2006. An improved construction for counting bloom filters. In Algorithms-ESA 2006: 14th Annual European Symposium, Zurich, Switzerland, September 11--13, 2006. Proceedings 14. Springer, 684--695.

[7]

caida [n.d.]. The CAIDA UCSD Statistical information for the CAIDA Anonymized Internet Traces. https://www.caida.org/data/passive/passive_trace_statistics.

[8]

Emmanuel J Candès, Justin K Romberg, and Terence Tao. 2006. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics 59, 8 (2006), 1207--1223.

[9]

Emmanuel J Candès and Terence Tao. 2006. Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE Transactions on Information Theory 52, 12 (2006), 5406--5425.

Digital Library

[10]

Emmanuel J Candès and Michael B Wakin. 2008. An introduction to compressive sampling. IEEE signal processing magazine 25, 2 (2008), 21--30.

[11]

Moses Charikar, Kevin Chen, and Martin Farach-Colton. 2002. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming. Springer, 693--703.

Digital Library

[12]

Min Chen, Shigang Chen, and Zhiping Cai. 2016. Counter tree: A scalable counter architecture for per-flow traffic measurement. IEEE/ACM ToN 25, 2 (2016), 1249--1262.

Digital Library

[13]

Yi-Chao Chen, Lili Qiu, Yin Zhang, Guangtao Xue, and Zhenxian Hu. 2014. Robust network compressive sensing. In Proc. of MobiCom. 545--556.

Digital Library

[14]

Chun Tung Chou, Rajib Rana, and Wen Hu. 2009. Energy efficient information collection in wireless sensor networks using adaptive compressive sensing. In Proc. of LCN. IEEE, 443--450.

[15]

Saar Cohen and Yossi Matias. 2003. Spectral bloom filters. In Proc. of SIGMOD. 241--252.

Digital Library

[16]

Graham Cormode and Shan Muthukrishnan. 2005. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms 55, 1 (2005), 58--75.

Digital Library

[17]

Graham Cormode and Shan Muthukrishnan. 2005. Summarizing and mining skewed data streams. In Proc. of SDM. SIAM, 44--55.

[18]

Graham Cormode and Shanmugavelayutham Muthukrishnan. 2005. What's new: Finding significant differences in network data streams. IEEE/ACM ToN 13, 6 (2005), 1219--1232.

Digital Library

[19]

Olivier Dubois and Jacques Mandler. 2002. The 3-XORSAT threshold. Comptes Rendus Mathématique 335, 11 (2002), 963--966.

[20]

Gil Einziger and Roy Friedman. 2016. Counting with tinytable: Every bit counts!. In Proc. of ICDCN. 1--10.

Digital Library

[21]

Cristian Estan and George Varghese. 2002. New directions in traffic measurement and accounting. In Proc. of SIGCOMM. 323--336.

Digital Library

[22]

Rodrigo Fonseca, Tianrong Zhang, Karl Deng, and Lihua Yuan. 2019. dShark: A general, easy to program and scalable framework for analyzing in-network packet traces. (2019), 207--220.

[23]

Andreas Goerdt and Lutz Falke. 2012. Satisfiability Thresholds beyond k-XORSAT. In International Computer Science Symposium in Russia. Springer, 148--159.

[24]

Junzhi Gong, Tong Yang, Yang Zhou, Dongsheng Yang, Shigang Chen, Bin Cui, and Xiaoming Li. 2017. Abc: a practicable sketch framework for non-uniform multisets. In Proc. of IEEE International Conference on Big Data. 2380--2389.

[25]

Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.

[26]

Arpit Gupta, Rob Harrison, Marco Canini, Nick Feamster, Jennifer Rexford, and Walter Willinger. 2018. Sonata: Query-driven streaming network telemetry. In Proc. of SIGCOMM. 357--371.

Digital Library

[27]

Nan Hua, Bill Lin, Jun Xu, and Haiquan Zhao. 2008. Brick: A novel exact active statistics counter architecture. In Proc. of ANCS. 89--98.

Digital Library

[28]

Qun Huang, Xin Jin, Patrick PC Lee, Runhui Li, Lu Tang, Yi-Chao Chen, and Gong Zhang. 2017. Sketchvisor: Robust network measurement for software packet processing. In Proc. of SIGCOMM. 113--126.

Digital Library

[29]

Qun Huang, Patrick PC Lee, and Yungang Bao. 2018. Sketchlearn: relieving user burdens in approximate measurement with automated statistical inference. In Proc. of SIGCOMM. 576--590.

Digital Library

[30]

Qun Huang, Siyuan Sheng, Xiang Chen, Yungang Bao, Rui Zhang, Yanwei Xu, and Gong Zhang. 2021. Toward {Nearly-Zero-Error} Sketching via Compressive Sensing. In Proc. of NSDI. 1027--1044.

[31]

Gabriel Istrate, Stefan Boettcher, and Allon G Percus. 2005. Spines of random constraint satisfaction problems: definition and connection with computational complexity. Annals of Mathematics and Artificial Intelligence 44, 4 (2005), 353--372.

Digital Library

[32]

Lavanya Jose, Minlan Yu, and Jennifer Rexford. 2011. Online Measurement of Large Traffic Aggregates on Commodity Switches. In Workshop on Hot-ICE.

[33]

Changhoon Kim, Anirudh Sivaraman, Naga Katta, Antonin Bas, Advait Dixit, and Lawrence J Wobker. 2015. In-band network telemetry via programmable dataplanes. In Proc. of SIGCOMM, Vol. 15.

[34]

Gene Moo Lee, Huiya Liu, Young Yoon, and Yin Zhang. 2005. Improving sketch reconstruction accuracy using linear least squares method. In Proc. of ACM IMC. 24--24.

[35]

Haoyu Li, Qizhi Chen, Yixin Zhang, Tong Yang, and Bin Cui. 2022. Stingy sketch: a sketch framework for accurate and fast frequency estimation. Proc. of VLDB 15, 7 (2022), 1426--1438.

Digital Library

[36]

Jizhou Li, Zikun Li, Yifei Xu, Shiqi Jiang, Tong Yang, Bin Cui, Yafei Dai, and Gong Zhang. 2020. Wavingsketch: An unbiased and generic sketch for finding top-k items in data streams. In Proc. of SIGKDD. 1574--1584.

Digital Library

[37]

Tao Li, Shigang Chen, and Yibei Ling. 2012. Per-flow traffic measurement through randomized counter sharing. IEEE/ACM ToN 20, 5 (2012), 1622--1634.

Digital Library

[38]

Yuliang Li, Rui Miao, Changhoon Kim, and Minlan Yu. 2016. FlowRadar: A Better NetFlow for Data Centers. In Proc. of NSDI. 311--324.

[39]

Yuliang Li, Rui Miao, Hongqiang Harry Liu, Yan Zhuang, Fei Feng, Lingbo Tang, Zheng Cao, Ming Zhang, Frank Kelly, Mohammad Alizadeh, et al. 2019. HPCC: High precision congestion control. In Proc. of SIGCOMM. 44--58.

Digital Library

[40]

Yang Li, Hao Wu, Tian Pan, Huichen Dai, Jianyuan Lu, and Bin Liu. 2016. Case: Cache-assisted stretchable estimator for high speed per-flow measurement. In Proc. of INFOCOM. IEEE, 1--9.

Digital Library

[41]

Kate Ching-Ju Lin and Wei-Lun Lai. 2022. MC-Sketch: Enabling Heterogeneous Network Monitoring Resolutions with Multi-Class Sketch. In Proc. of INFOCOM. IEEE, 220--229.

[42]

Lingtong Liu, Yulong Shen, Yibo Yan, Tong Yang, Muhammad Shahzad, Bin Cui, and Gaogang Xie. 2020. Sf-sketch: a two-stage sketch for data streams. IEEE TPDS 31, 10 (2020), 2263--2276.

[43]

Zaoxing Liu, Ran Ben-Basat, Gil Einziger, Yaron Kassner, Vladimir Braverman, Roy Friedman, and Vyas Sekar. 2019. Nitrosketch: Robust and general sketch-based monitoring in software switches. In Proc. of SIGCOMM. 334--350.

Digital Library

[44]

Zaoxing Liu, Antonis Manousis, Gregory Vorsanger, Vyas Sekar, and Vladimir Braverman. 2016. One sketch to rule them all: Rethinking network flow monitoring with UnivMon. In Proc. of SIGCOMM. 101--114.

Digital Library

[45]

Zaoxing Liu, Hun Namkung, Georgios Nikolaidis, Jeongkeun Lee, Changhoon Kim, Xin Jin, Vladimir Braverman, Minlan Yu, and Vyas Sekar. 2021. Jaqen: A {High-Performance} {Switch-Native} Approach for Detecting and Mitigating Volumetric {DDoS} Attacks with Programmable Switches. In 30th USENIX Security Symposium (USENIX Security 21). 3829--3846.

[46]

Yi Lu, Andrea Montanari, Balaji Prabhakar, Sarang Dharmapurikar, and Abdul Kabbani. 2008. Counter braids: a novel counter architecture for per-flow measurement. ACM SIGMETRICS Performance Evaluation Review 36, 1 (2008), 121--132.

Digital Library

[47]

Yi Lu and Balaji Prabhakar. 2009. Robust counting via counter braids: An error-resilient network measurement architecture. In Proc. of INFOCOM. IEEE, 522--530.

[48]

Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. 2005. Efficient computation of frequent and top-k elements in data streams. In International conference on database theory. Springer, 398--412.

[49]

Rui Miao, Hongyi Zeng, Changhoon Kim, Jeongkeun Lee, and Minlan Yu. 2017. Silkroad: Making stateful layer-4 load balancing fast and cheap using switching asics. In Proc. of SIGCOMM. 15--28.

Digital Library

[50]

Hun Namkung, Zaoxing Liu, Daehyeok Kim, Vyas Sekar, and Peter Steenkiste. 2023. Sketchovsky: Enabling Ensembles of Sketches on Programmable Switches. In Proc. of NSDI. 1273--1292.

[51]

p4 2022. P4 Language. http://p4.org.

[52]

Boris Pittel and Gregory B Sorkin. 2016. The satisfiability threshold for k-XORSAT. Combinatorics, Probability and Computing 25, 2 (2016), 236--268.

[53]

Jiuhua Qi, Wenjun Li, Tong Yang, Dagang Li, and Hui Li. 2019. Cuckoo counter: A novel framework for accurate per-flow frequency estimation in network measurement. In Proc. of ANCS. IEEE, 1--7.

[54]

Sriram Ramabhadran and George Varghese. 2003. Efficient implementation of a statistics counter architecture. In Proc. of the ACM SIGMETRICS international conference on Measurement and modeling of computer systems. 261--271.

Digital Library

[55]

Pratanu Roy, Arijit Khan, and Gustavo Alonso. 2016. Augmented sketch: Faster and more accurate stream processing. In Proc. of SIGMOD. 1449--1463.

Digital Library

[56]

Devavrat Shah, Sundar Iyer, Balaji Prabhakar, and Nick McKeown. 2001. Analysis of a statistics counter architecture. In HOT 9 Interconnects. Symposium on High Performance Interconnects. IEEE, 107--111.

[57]

Siyuan Sheng, Qun Huang, Sa Wang, and Yungang Bao. 2021. PR-sketch: monitoring per-key aggregation of streaming data with nearly full accuracy. Proc. of VLDB 14, 10 (2021), 1783--1796.

Digital Library

[58]

Anirudh Sivaraman, Alvin Cheung, Mihai Budiu, Changhoon Kim, Mohammad Alizadeh, Hari Balakrishnan, George Varghese, Nick McKeown, and Steve Licking. 2016. Packet transactions: High-level programming for line-rate switches. In Proc. of SIGCOMM. 15--28.

Digital Library

[59]

Vibhaalakshmi Sivaraman, Srinivas Narayana, Ori Rottenstreich, Shan Muthukrishnan, and Jennifer Rexford. 2017. Heavy-hitter detection entirely in the data plane. In Proc. of ACM SOSR. 164--176.

Digital Library

[60]

Cha Hwan Song, Pravein Govindan Kannan, Bryan Kian Hsiang Low, and Mun Choon Chan. 2020. FCM-sketch: generic network measurements with data plane support. In Proc. of CoNEXT. 78--92.

Digital Library

[61]

Lu Tang, Qun Huang, and Patrick PC Lee. 2019. Mv-sketch: A fast and compact invertible sketch for heavy flow detection in network data streams. In Proc. of INFOCOM. IEEE, 2026--2034.

Digital Library

[62]

tofino 2022. Barefoot's Tofino. https://www.barefootnetworks.com/technology.

[63]

Yibo Yan, Cheng Chen, Huiping Lin, Olivier Ruas, Tengjiao Wang, and Tong Yang. 2020. Priority-aware per-flow measurement using cuckoo sketch. In Proc. of IFIP Networking Conference (Networking). IEEE, 622--624.

[64]

Mingran Yang, Alex Baban, Valery Kugel, Jeff Libby, Scott Mackie, Swamy Sadashivaiah Renu Kananda, Chang-Hong Wu, and Manya Ghobadi. 2022. Using trio: juniper networks' programmable chipset-for emerging in-network applications. In Proc. of SIGCOMM. 633--648.

Digital Library

[65]

Tong Yang, Siang Gao, Zhouyi Sun, Yufei Wang, Yulong Shen, and Xiaoming Li. 2019. Diamond sketch: Accurate per-flow measurement for big streaming data. IEEE TPDS 30, 12 (2019), 2650--2662.

[66]

Tong Yang, Jie Jiang, Peng Liu, Qun Huang, Junzhi Gong, Yang Zhou, Rui Miao, Xiaoming Li, and Steve Uhlig. 2018. Elastic sketch: Adaptive and fast network-wide measurements. In Proc. of SIGCOMM. 561--575.

Digital Library

[67]

Tong Yang, Haowei Zhang, Jinyang Li, Junzhi Gong, Steve Uhlig, Shigang Chen, and Xiaoming Li. 2019. HeavyKeeper: An Accurate Algorithm for Finding Top-k Elephant Flows. IEEE/ACM ToN 27, 5 (2019), 1845--1858.

Digital Library

[68]

Tong Yang, Yang Zhou, Hao Jin, Shigang Chen, and Xiaoming Li. 2017. Pyramid sketch: A sketch framework for frequency estimation of data streams. Proc. of VLDB 10, 11 (2017), 1442--1453.

Digital Library

[69]

Minlan Yu. 2019. Network telemetry: towards a top-down approach. ACM SIGCOMM Computer Communication Review 49, 1 (2019), 11--17.

Digital Library

[70]

Minlan Yu, Lavanya Jose, and Rui Miao. 2013. Software {Defined}{Traffic} Measurement with {OpenSketch}. In Proc. of NSDI. 29--42.

[71]

Ying Zhang. 2013. An adaptive flow counting method for anomaly detection in SDN. In Proc. of CoNEXT. 25--30.

Digital Library

[72]

Bohan Zhao, Xiang Li, Boyu Tian, Zhiyu Mei, and Wenfei Wu. 2021. DHS: Adaptive Memory Layout Organization of Sketch Slots for Fast and Accurate Data Stream Processing. In Proc. of SIGKDD. 2285--2293.

Digital Library

[73]

Qi Zhao, Jun Xu, and Zhen Liu. 2006. Design of a novel statistics counter architecture with optimal space and time efficiency. In Proc. of the joint international conference on Measurement and modeling of computer systems. 323--334.

Digital Library

[74]

Xiaolei Zhao, Mei Wen, Minjin Tang, Qun Huang, and Chunyuan Zhang. 2020. HybridSketch: A Memory-centric Precise Approach for Flow Measurement. In Proc. of ICC. IEEE, 1--7.

[75]

Yikai Zhao, Kaicheng Yang, Zirui Liu, Tong Yang, Li Chen, Shiyi Liu, Naiqian Zheng, Ruixin Wang, Hanbo Wu, Yi Wang, et al. 2021. {LightGuardian}: A {full-visibility}, lightweight, in-band telemetry system using sketchlets. In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21). 991--1010.

[76]

Yang Zhou, Hao Jin, Peng Liu, Haowei Zhang, Tong Yang, and Xiaoming Li. 2018. Accurate per-flow measurement with bloom sketch. In Proc. of NFOCOM WKSHPS. IEEE, 1--2.

[77]

Yang Zhou, Peng Liu, Hao Jin, Tong Yang, Shoujiang Dang, and Xiaoming Li. 2017. One memory access sketch: a more accurate and faster sketch for per-flow measurement. In Proc. of GLOBECOM. IEEE, 1--6.

Digital Library

[78]

Yang Zhou, Ying Zhang, Minlan Yu, Guangyu Wang, Dexter Cao, Eric Sung, and Starsky Wong. 2022. Evolvable Network Telemetry at Facebook. In Proc. of NSDI. USENIX Association.

[79]

Yibo Zhu, Nanxi Kang, Jiaxin Cao, Albert Greenberg, Guohan Lu, Ratul Mahajan, Dave Maltz, Lihua Yuan, Ming Zhang, Ben Y Zhao, et al. 2015. Packet-level telemetry in large datacenter networks. In Proc. of SIGCOMM. 479--491.

Digital Library

Cited By

Li FGuo KShen JWang X(2024)Effective Network-Wide Traffic Measurement: A Lightweight Distributed Sketch DeploymentIEEE INFOCOM 2024 - IEEE Conference on Computer Communications10.1109/INFOCOM52122.2024.10621384(181-190)Online publication date: 20-May-2024
https://doi.org/10.1109/INFOCOM52122.2024.10621384
Wu YYuan AShi ZLi YZhao YChen PYang TCui B(2024)Online Detection of Outstanding Quantiles with QuantileFilter2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00069(831-844)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00069

Index Terms

BitSense: Universal and Nearly Zero-Error Optimization for Sketch Counters with Compressive Sensing
1. Networks
  1. Network performance evaluation
    1. Network measurement

Recommendations

Image compressive sensing via Truncated Schatten-p Norm regularization

Low-rank property as a useful image prior has attracted much attention in image processing communities. Recently, a nonlocal low-rank regularization (NLR) approach toward exploiting low-rank property has shown the state-of-the-art performance in ...
Compressive sensing via nonlocal low-rank tensor regularization

The aim of Compressing sensing (CS) is to acquire an original signal, when it is sampled at a lower rate than Nyquist rate previously. In the framework of CS, the original signal is often assumed to be sparse and correlated in some domain. Recently, ...
Block compressive sensing

Iterative re-weighted l1 norm minimization reconstruction algorithm.Joint reconstruction algorithm for multiview images and video frames.The correlation between multiple images is exploited through joint sparsity model. Compressive sensing provides ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ACM SIGCOMM '23: Proceedings of the ACM SIGCOMM 2023 Conference

September 2023

1217 pages

ISBN:9798400702365

DOI:10.1145/3603269

Chairs:
Henning Schulzrinne,
Vishal Misra,
Program Chairs:
Eddie Kohler,
David Maltz

Copyright © 2023 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

National Key R&D Program of China
Joint Funds of the National Natural Science Foundation of China
National Natural Science Foundation of China

Conference

ACM SIGCOMM '23

Sponsor:

SIGCOMM

ACM SIGCOMM '23: ACM SIGCOMM 2023 Conference

September 10, 2023

NY, New York, USA

Acceptance Rates

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
838
Total Downloads

Downloads (Last 12 months)838
Downloads (Last 6 weeks)29

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li FGuo KShen JWang X(2024)Effective Network-Wide Traffic Measurement: A Lightweight Distributed Sketch DeploymentIEEE INFOCOM 2024 - IEEE Conference on Computer Communications10.1109/INFOCOM52122.2024.10621384(181-190)Online publication date: 20-May-2024
https://doi.org/10.1109/INFOCOM52122.2024.10621384
Wu YYuan AShi ZLi YZhao YChen PYang TCui B(2024)Online Detection of Outstanding Quantiles with QuantileFilter2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00069(831-844)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00069

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents