More Like this

1. SketchLib: Enabling Efficient Sketch-based Monitoring on Programmable Switches

   Namkung, Hun; Liu, Zaoxing; Kim, Daehyeok; Sekar, Vyas; Steenkiste, Peter (April 2022, 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI'22))

   Sketching algorithms or sketches enable accurate network measurement results with low resource footprints. While emerging programmable switches are an attractive target to get these benefits, current implementations of sketches are either inefficient 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 identified bottlenecks; and (3) designing an easy-to-use library called SketchLib to help developers efficiently implement their sketch algorithms in switch hardware to benefit 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 fidelity. 

   more » « less
2. SketchLib: Enabling Efficient Sketch-based Monitoring on Programmable Switches

   Namkung, Hun; Liu, Zaoxing; Kim, Daehyeok; Sekar, Vyas; Steenkiste, Peter (April 2022, USENIX Symposium on Networked Systems Design and Implementation)

   Sketching algorithms or sketches enable accurate network measurement results with low resource footprints. While emerging programmable switches are an attractive target to get these benefits, current implementations of sketches are either inefficient 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 identified bottlenecks; and (3) designing an easy-to-use library called SketchLib to help developers efficiently implement their sketch algorithms in switch hardware to benefit 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 fidelity. 

   more » « less
3. Telemetry Retrieval Inaccuracy in Programmable Switches: Analysis and Recommendations

   https://doi.org/10.1145/3482898.3483359  

   Namkung, Hun; Kim, Daehyeok; Liu, Zaoxing; Sekar, Vyas; Steenkiste, Peter (October 2021, SOSR '21: Proceedings of the ACM SIGCOMM Symposium on SDN Research (SOSR))

   Sketching algorithms or sketches are attractive as telemetry capabilities on programmable hardware switches since they offer rigorous accuracy guarantees and use compact data structures. However, we find that in practice, their actual implementations can have a significant (up to 94×) accuracy drop compared to theoretical expectations. We find that the delays incurred by pulling and resetting the data plane state induce accuracy degradation. We design and implement solutions to reduce the delays and show that our solutions can help eliminate almost all the inaccuracy of existing sketch workflows. 

   more » « less
4. Approximate Sketches

   https://doi.org/10.1145/3639321  

   Tsan, Brian; Datta, Asoke; Izenov, Yesdaulet; Rusu, Florin (March 2024, Proceedings of the ACM on Management of Data)

   Sketches are single-pass small-space data summaries that can quickly estimate the cardinality of join queries. However, sketches are not directly applicable to join queries with dynamic filter conditions --- where arbitrary selection predicate(s) are applied --- since a sketch is limited to a fixed selection. While multiple sketches for various selections can be used in combination, they each incur individual storage and maintenance costs. Alternatively, exact sketches can be built during runtime for every selection. To make this process scale, a high-degree of parallelism --- available in hardware accelerators such as GPUs --- is required. Therefore, sketch usage for cardinality estimation in query optimization is limited. Following recent work that applies transformers to cardinality estimation, we design a novel learning-based method to approximate the sketch of any arbitrary selection, enabling sketches for join queries with filter conditions. We train a transformer on each table to estimate the sketch of any subset of the table, i.e., any arbitrary selection. Transformers achieve this by learning the joint distribution amongst table attributes, which is equivalent to a multidimensional sketch. Subsequently, transformers can approximate any sketch, enabling sketches for join cardinality estimation. In turn, estimating joins via approximate sketches allows tables to be modeled individually and thus scales linearly with the number of tables. We evaluate the accuracy and efficacy of approximate sketches on queries with selection predicates consisting of conjunctions of point and range conditions. Approximate sketches achieve similar accuracy to exact sketches with at least one order of magnitude less overhead. 

   more » « less
5. Sketchy With a Chance of Adoption: Can Sketch-Based Telemetry Be Ready for Prime Time?

   Liu, Zaoxing; Namkung, Hun; Agarwal, Anup; Manousis, Antonis; Steenkiste, Peter; Seshan, Srinivasan; Sekar, Vyas (June 2021, IEEE Conference on Network Softwarization NetSoft)

   null (Ed.)

   Sketching algorithms or sketches have emerged as a promising alternative to the traditional packet sampling-based network telemetry solutions. At a high level, they are attractive because of their high resource efficiency and provable accuracy guarantees. While there have been significant recent advances in various aspects of sketching for networking tasks, many fundamental challenges remain unsolved that are likely stumbling blocks for adoption. Our contribution in this paper is in identifying and formulating these research challenges across the ecosystem encompassing network operators, platform vendors/developers, and algorithm designers. We hope that these serve as a necessary fillip for the community to enable the broader adoption of sketch-based telemetry. 

   more » « less