CONIX Publication

With increasing virtualization of services and network functions, virtual switches are emerging as an important measurement vantage point. Given the tight resource requirements, sketching algorithms appear as a promising alternative to traditional monitoring (e.g., sampling or full packet capture). However, sketching algorithms are typically designed with memory-oriented optimization goals in theory and incur significant computational overhead in software. Unfortunately, existing optimizations that try to address this performance issue have to make compromises on the worst-case theoretical guarantees or make strong assumptions about the traffic distributions or only work for specific sketches. This paper presents NitroSketch, a general and efficient software sketching platform to offer optimized packet processing speed for a broad spectrum sketches. NitroSketch has provable worst-case guarantees, without needing any distributional assumptions. We do this by systematically identifying the fundamental performance bottlenecks of sketches and developing rigorous solutions to tackle these. With NitroSketch, sketching algorithms can run even faster than simple hash tables with only a small increase in memory footprint. We implement a NitroSketch prototype integrated with two popular software switching platforms: Open vSwitch-DPDK and fd.io/VPP. We evaluate the performance of NitroSketch on commodity servers and show that it can improve the performance of sketches by up to 27 times while reducing the CPU usage by 45\%45%.