CocoSketch: High-Performance Sketch-Based Measurement Over Arbitrary Partial Key Query

Sketch-based measurement has emerged as a promising solutions due to its high accuracy and resource efficiency. Prior sketches focus on measuring single flow keys and cannot support measurement on multiple keys. This work takes a significant step towards supporting arbitrary partial key queries, which aims to provide information for any key in the predefined range of possible flow keys. The designed system, CocoSketch, casts arbitrary partial key queries to the subset sum estimation problem and makes the theoretical tools for subset sum estimation practical. CocoSketch utilizes 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. This paper extends the conference version by discussing how CocoSketch adapts to new measurement requirements, including: (1) collecting the exact information of specified flow keys, and (2) distributed measurement. CocoSketch is implemented on five popular platforms (CPU, Open vSwitch, Redis, P4, and FPGA). Experiment results show that compared to baselines that use traditional single-key sketches, CocoSketch improves average packet processing throughput by $27.2\times $ and accuracy by $10.4\times $ when measuring six flow keys.

I. Introduction

Network monitoring and measurement have been critical to various network management tasks, such as traffic engineering [2], [3], accounting [4], [5], [6], load balancing [7], [8], [9], flow scheduling [10], [11], and anomaly detection [12], [13], [14]. These tasks often require timely and accurate estimates of the network flow metrics, e.g., heavy hitters [15], [16], [17], [18], flow size distribution [19], or heavy changes [20], [21]. In response, recent efforts have demonstrated that sketching algorithms (sketches) can estimate these metrics with high fidelity at a high throughput using only small amounts of resources [22], [23].