SketchLib - Enabling Efficient Sketch-based Monitoring on Programmable Switches

Aug 20, 2026

SketchLib enables accurate network measurement with low resource footprints by bringing sketch-based monitoring to programmable switch hardware. The work analyzes hardware bottlenecks in existing sketch implementations, including hash-call cost, limited per-packet memory accesses, pipeline-stage constraints, and heavy-flowkey tracking overheads. It then introduces correct-by-construction optimization techniques and packages them as an easy-to-use library. Evaluations with state-of-the-art sketches show SketchLib cuts switch hardware resource usage by up to 96% while preserving measurement fidelity.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages18

Reading Time45 min

AccessFree to download

Abstract

Introduction

Sketch-based monitoring overview

Hardware challenges for sketch implementation

Resource bottlenecks on RMT switches

SketchLib: Enabling Efficient Sketch-based Monitoring on Programmable Switches Hun Namkung, Carnegie Mellon University; Zaoxing Liu, Boston University; Daehyeok Kim, Carnegie Mellon University and Microsoft; Vyas Sekar and Peter Steenkiste, Carnegie Mellon University [https://www.usenix.org/conference/nsdi22/presentation/namkung](https://www.usenix.org/conference/nsdi22/presentation/namkung) This paper is included in the Proceedings of the 19th USENIX Symposium on Networked Systems Design and Implementation . April 4–6, 2022 • Renton, WA, USA 978-1-939133-27-4 Open access to the Proceedings of the 19th USENIX Symposium on Networked Systems Design and Implementation is sponsored by SketchLib: Enabling Efﬁcient Sketch-based Monitoring on Programmable Switches Hun Namkung?, Zaoxing Liu†, Daehyeok Kim?§, Vyas Sekar? , Peter Steenkiste?? Carnegie Mellon University, †Boston University, § Microsoft Abstract Sketching algorithms or sketches enable accurate network measurement results with low resource footprints. While emerging programmable switches are an attractive target to get these beneﬁts, current implementations of sketches are either inefﬁcient and/or infeasible on hardware. Our contributions in the paper are: (1) systematically analyzing the resource bottlenecks of existing sketch implementations in hardware; (2) identifying practical and correct-by-construction optimization techniques to tackle the identiﬁed bottlenecks; and (3) designing an easy-to-use library called SketchLib to help developers efﬁciently implement their sketch algorithms in switch hardware to beneﬁt from these resource optimizations. Our evaluation on state-of-the-art sketches demonstrates that SketchLib reduces the hardware resource footprint up to 96% without impacting ﬁdelity. 1 Introduction The ability to monitor network trafﬁc is necessary for various network management tasks such as trafﬁc engineering, anomaly detection, load balancing, and resource provisioning [10, 13, 27, 29, 43, 45, 54] . In this respect, recent developments in programmable switches and attendant languages [9, 14] make it possible to support richer ﬁne-grained and real-time monitoring capabilities. With this network programmability, sketch-based monitoring has emerged as a promising alternative to traditional sampling-based techniques [19, 49] . At a high-level, sketch algorithms consist of updating multiple counter arrays with a series of independent hash function calls and counter updates. Sketch-based approaches have been developed to support abroad spectrum of measurement tasks with provable resourceaccuracy trade-offs, including heavy-hitter detection or quantile estimation (e.g., [17, 21]), general estimation capabilities (e.g., UnivMon [41]), and more expressive multidimensional analytics (e.g., R-HHH [12]) . While prior efforts have demonstrated the feasibility of expressing sketches using these language APIs [32, 41, 46, 53], implementing sketches efﬁciently in hardware remains an open challenge. For example, off-the-shelf sketch implementations often cannot run with the desired accuracy levels due to insufﬁcient hardware resources (see §3) . Indeed, some proposed sketches (e.g., [41]) are infeasible as implemented, or even if they are feasible, consume signiﬁcant resources. Even if more hardware resources may become available, so too do operators’ demands of in-switch applications, and the resources consumed by sketches will be unavailable for other switch functions. Thus, it is essential to explore if, and how, we can efﬁciently realize sketch-based telemetry on programmable switches. This is the central question that this paper tackles. Speciﬁcally, we focus on programmable hardware switches based on the Reconﬁgurable Match-Action Tables (RMT) paradigm [1] . We identify and analyze four key resource bottlenecks for realizing sketches on RMT switch hardware: • Hash calls: Sketches make a number of counter updates based on indepe

FAQs

How does SketchLib achieve resource reductions without losing fidelity?

The paper combines multiple correct-by-construction optimizations and packages them into a library. Experiments report up to 96% reduction in hardware resource footprint while keeping measurement fidelity.

Aug 20, 2026

Upload by Jordan Avery