Skip navigation
Please use this identifier to cite or link to this item:
Title: Designing Compact Data Structures for Network Measurement and Control
Authors: Chen, Xiaoqi
Advisors: Rexford, Jennifer
Contributors: Computer Science Department
Keywords: Network Measurement
Programmable Data Plane
Software-Defined Networking
Streaming Algorithm
Subjects: Computer science
Computer engineering
Issue Date: 2023
Publisher: Princeton, NJ : Princeton University
Abstract: This dissertation explores the implementation of network measurement and closed-loop control in the data plane of high-speed programmable switches. After discussing the algorithmic constraints imposed by the switch pipeline architecture, primarily stemming from the requirement of high-speed processing, we share our experience in tailoring algorithms for the data plane. Initially, we focus on efficient measurement algorithms, and present two works for detecting heavy hitters and executing multiple distinct-count queries; both require designing novel approximate data structures to meet the tight memory access constraints. Subsequently, we pivot towards using real-time, closed-loop control in the data plane for performance optimization, and present two works for mitigating microbursts and enforcing fair bandwidth limits; both require approximated computation and exploit the sub-millisecond reaction latency unattainable through conventional control planes. We hope by sharing our experience and techniques, which are widely applicable to various algorithms and other data-plane hardware targets, we can lay the foundation for future innovations in the field of network programming for researchers and practitioners alike.
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Computer Science

Files in This Item:
File Description SizeFormat 
Chen_princeton_0181D_14809.pdf7.29 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.