Toward Nearly-Zero-Error Sketching via Compressive Sensing
summary
Claims near-zero per-flow error for almost all flows by combining compressive sensing with sketch structures, producing two algorithms called SiX sketch and Embedded sketch. Designs use Bloom filter key tracking, candidate-large-flow splitting and fractional updates, construct sensing matrices with low RIP, and run in hardware/software (implemented in OpenVSwitch and P4). Evaluation shows a few hundred KB handles 1M flows and yields <0.1% per-flow error for 99.72% of flows, preserving sketch efficiency.
AI-written summary · about
chapters (13)
- 0:00Intro
- 0:35Flow-level Network Monitoring
- 2:05Existing Guarantees Are Not Enough
- 2:28Example
- 3:39Our Contributions
- 5:01Compressive Sensing Recovery Operation
- 6:041st Attempt: Directly Adopt
- 6:582nd Attempt: Formulate Sketch
- 7:56Key Matrix Property: Orthonormality
- 9:06Revisit Sketch Design How common approaches affect matrix?
- 10:19New Algorithms
- 11:03Results
- 11:28Conclusion
related talks
15mSketchPipe: Toward Accurate Sketch-based Network Measurement on Multi-Pipeline...
17mDefeating Slow-and-Low Threats via Diffusion Model-based Generative Inference
15mSketchLib: Enabling Efficient Sketch-based Monitoring on Programmable Switches
29mCompressive Sensing
01h 24mStreaming, Sketching and Sufficient Statistics I
26mLearning Sparse Data with Near-optimal Speed and Efficiency from a Variety of Measurement Processes
01h 26mStreaming, Sketching and Sufficient Statistics II
17mSketchovsky: Enabling Ensembles of Sketches on Programmable Switches