Toward Nearly-Zero-Error Sketching via Compressive Sensing


Qun Huang, Peking University and Pengcheng Lab; Siyuan Sheng, Institute of Computing Technology, CAS; Xiang Chen, Peking University and Pengcheng Lab and Fuzhou University; Yungang Bao, Institute of Computing Technology, CAS; Rui Zhang, Yanwei Xu, and Gong Zhang, Huawei Theory Department


Sketch algorithms have been extensively studied in the area of network measurement, given their limited resource usage and theoretically bounded errors. However, error bounds provided by existing algorithms remain too coarse-grained: in practice, only a small number of flows (e.g., heavy hitters) actually benefit from the bounds, while the remaining flows still suffer from serious errors. In this paper, we aim to design nearly-zero-error sketch that achieves negligible per-flow error for almost all flows. We base our study on a technique named compressive sensing. We exploit compressive sensing in two aspects. First, we incorporate the near-perfect recovery of compressive sensing to boost sketch accuracy. Second, we leverage compressive sensing as a novel and uniform methodology to analyze various design choices of sketch algorithms. Guided by the analysis, we propose two sketch algorithms that seamlessly embrace compressive sensing to reach nearly zero errors. We implement our algorithms in OpenVSwitch and P4. Experimental results show that the two algorithms incur less than 0.1% per-flow error for more than 99.72% flows, while preserving the resource efficiency of sketch algorithms. The efficiency demonstrates the power of our new methodology for sketch analysis and design.

NSDI '21 Open Access Sponsored by NetApp

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {265057,
author = {Qun Huang and Siyuan Sheng and Xiang Chen and Yungang Bao and Rui Zhang and Yanwei Xu and Gong Zhang},
title = {Toward {Nearly-Zero-Error} Sketching via Compressive Sensing},
booktitle = {18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21)},
year = {2021},
isbn = {978-1-939133-21-2},
pages = {1027--1044},
url = {},
publisher = {USENIX Association},
month = apr

Presentation Video