SketchLib: Enabling Efficient Sketch-based Monitoring on Programmable Switches

on YouTube ↗15m

" summary

SketchLib is a P4-targeted library that implements six correct-by-construction optimizations after identifying four hardware bottlenecks (hash units, SLUs, pipeline stages, heavy-key tracking). It consolidates counters and slices long hashes to cut hash calls by ~3x or more, reports up to 96% reduction in hardware footprint (example: 91% fewer hash calls, 90% fewer SLU uses, 65% fewer stages for one multi-level sketch), ships 15 sketches implemented, and preserves accuracy (median error change <1%); code is open source.

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 1:09Let's try to run sketches on programmable switches
3. 2:09Sketch is inefficient or infeasible on programmable switch
4. 3:00Our work: Sketchlib bridges the gap!
5. 3:47Outline
6. 4:32Sketches have four common steps
7. 5:18Sketch imposes burden on hardware resources
8. 7:01Hash calls and SALUs are resource bottlenecks
9. 7:58Overview of optimizations and SketchLib API
10. 8:2401. Consolidate short hash calls
11. 9:4405. Remove unnecessary SALU allocation
12. 11:01End-to-end code example
13. 11:54Applicability of SketchLib
14. 12:27Sketchlib reduces resource bottlenecks
15. 13:30Sketch Lib preserves accuracy
16. 14:25Conclusion

" related talks

• 17mSketchovsky: Enabling Ensembles of Sketches on Programmable SwitchesZaoxing Liu, Hun Namkung, Daehyeok Kim, Vyas Sekar, Peter Steenkiste · NSDI 2023
• 15mSketchPipe: Toward Accurate Sketch-based Network Measurement on Multi-Pipeline...Chunming Wu, Xiang Chen, Longlong Zhu, Linying Zheng, Hongyang Du, Dong Zhang, Jianshan Zhang, Xuan Liu, Qun Huang, Dusit Niyato, Haifeng Zhou, Hongyan Liu, Kui Ren · NSDI '26
• 14mOctoSketch: Enabling Real-Time, Continuous Network Monitoring over Multiple CoresZaoxing Liu, Yinda Zhang, Peiqing Chen · 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24)
• 15mAutoSketch: Automatic Sketch-Oriented Compiler for Query-driven Network TelemetryXin Yao, Wei Wang, Gong Zhang, Haifeng Sun, Yungang Bao, Fuliang Li, Qun Huang, Jinbo Sun, Jiaheng Li · 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24)
• 22mSoftware Defined Traffic Measurement with OpenSketchMinlan Yu, Rui Miao, Lavanya Jose · NSDI 2013
• 15mSynthesizing Runtime Programmable Switch UpdatesRyan Beckett, Ang Chen, Yiming Qiu · NSDI 2023
• 12mToward Nearly-Zero-Error Sketching via Compressive SensingGong Zhang, Rui Zhang, Yungang Bao, Xiang Chen, Qun Huang, Yanwei Xu, Siyuan Sheng · NSDI ’21
• 12mLightGuardian: A Full-Visibility, Lightweight, In-band Telemetry System Using SketchletsLi Chen, Yi Wang, Ruixin Wang, Shiyi Liu, Naiqian Zheng, Nicholas Zhang, Kaicheng Yang, Tong Yang, Yikai Zhao, Zirui Liu, Hanbo Wu · NSDI ’21