High-speed programmable switches allow network operators to run succinct,
customized algorithms to process individual packets, providing us a prime
opportunity to improve network performance and security. In my research, I
adopt approximation techniques to design algorithms that fit the switches’ strict
memory and computational constraints, allowing more granular network
measurement and real-time, closed-loop control. I then deploy these algorithms
in real-world campus and carrier networks to improve user experience. In this
talk, I will first introduce BeauCoup, a framework for simultaneously executing
a large number of traffic measurement queries without exceeding the memory
access constraints of the switch hardware. BeauCoup utilizes coupon collectors
to approximately answer each count-distinct query using less than one memory
access per packet on average. Second, I will present ConQuest, an algorithm
that approximately analyzes the switch’s queuing buffer and identifies bursty
flows. ConQuest enables the switch to react to bursts in real time and protect
other user traffic from suffering high delay or packet loss.