Paper Info
Title
CocoSketch: high-performance sketch-based measurement over arbitrary partial key query
Abstract
ABSTRACTSketch-based measurement has emerged as a promising alternative to the traditional sampling-based network measurement approaches due to its high accuracy and resource efficiency. While there have been various designs around sketches, they focus on measuring one particular flow key, and it is infeasible to support many keys based on these sketches. In this work, we take a significant step towards supporting arbitrary partial key queries, where we only need to specify a full range of possible flow keys that are of interest before measurement starts, and in query time, we can extract the information of any key in that range. We design CocoSketch, which casts arbitrary partial key queries to the subset sum estimation problem and makes the theoretical tools for subset sum estimation practical. To realize desirable resource-accuracy tradeoffs in software and hardware platforms, we propose two techniques: (1) stochastic variance minimization to significantly reduce per-packet update delay, and (2) removing circular dependencies in the per-packet update logic to make the implementation hardware-friendly. We implement CocoSketch on four popular platforms (CPU, Open vSwitch, P4, and FPGA) and show that compared to baselines that use traditional single-key sketches, CocoSketch improves average packet processing throughput by 27.2x and accuracy by 10.4x when measuring six flow keys.
Year
DOI
Venue
2021
10.1145/3452296.3472892
COMM
Keywords
DocType
Citations 
Sketch, Arbitrary Partial Key Query, P4, FPGA
Conference
2
PageRank 
References 
Authors
0.37
0
9
Name
Order
Citations
PageRank
Yinda Zhang171.44
Zaoxing Liu21049.79
Ruixin Wang320.71
Tong Yang420837.35
Jin Li583.38
Ruijie Miao620.37
Peng Liu721.04
Ruwen Zhang820.37
Junchen Jiang941.42