Enabling Practical and Performant Sketch-based Network Telemetry on Programmable Switches

Network telemetry plays an essential role in managing network systems. Various flow-level traffic measurement results (e.g., identifying heavy flows) are needed by network operators to make the right management decisions. In this thesis, we envision performant and practical flow-level network telemetry that satisfies four requirements: (1) low resource footprint, (2) high measurement accuracy, (3) high packet processing speed, and (4) support for diverse measurement results. State-of-the-art techniques of packet sampling suffer from low measurement accuracy. Instead, an alternative type of technique called sketching algorithms, or sketches, has received considerable attention due to their high measurement accuracy and resource efficiency. With recent advances in programmable network hardware technology, programmable switches have become a promising platform to program and deploy sketches with Tbps scale of high packet processing speed. 

Although running sketches on a programmable switch is a promising way to achieve the goal of satisfying the four requirements, there is a gap between sketches and programmable switches. While there have been continuous improvements on the theoretical side of sketching algorithms for better resource-accuracy tradeoffs, much less attention has been paid to how to efficiently run sketches on actual hardware switches. Specifically, there are three practical challenges: first, sketch implementations require excessive resources on the hardware switch, making rich sketch-based telemetry often infeasible. Second, it takes a long time for developers to implement sketches on programmable switches because of the complex underlying hardware architecture. Third, while packets update counters in the switch data plane, the switch control plane also reads and resets the counters, causing consistency problems that degrade measurement accuracy significantly. 

In this thesis, we present techniques that enable performant and practical sketch-based network telemetry on programmable switches by proposing optimizations to the sketch implementations, as well as by providing APIs and the code composition framework that automatically generates optimized sketch codes. In particular, we designed four novel systems. SketchLib and Sketchovsky propose optimizations for a single sketch and multiple sketches to reduce the hardware resources in the data plane. Autocode composition framework automatically generates optimized data plane sketch code. CounterFetchLib presents optimizations and APIs for minimizing read and reset delays in the control plane to address the counter contention problem. We show the feasibility and effectiveness of optimizations through extensive hands-on evaluations using the actual hardware. Using auto-code composition framework and APIs, developers can quickly implement accurate and performant sketches on the programmable switch without worrying about the complexities of the underlying hardware architecture.