For network administrators, performance monitoring provides valuable insights into network quality and security. The emergence of programmable network devices makes it possible to measure performance metrics in the data plane, where packets fly by. Running measurement tasks directly in the data plane improves eciency, preserves user privacy, and enables the possibility of real-time actions based on the analysis. However, programmable data planes have limited memory size and memory accesses. Meanwhile, measuring performance metrics fundamentally requires a large amount of memory resources, as each packet must be processed relative to its predecessor in the same flow.

This dissertation tackles the specific challenges that arise from running performance measurements with limited memory. The first part of this dissertation introduces new data-plane algorithms for monitoring two canonical performance metrics related to Transmission Control Protocol (TCP): delay and TCP packet reordering.

• In measuring delay distribution, existing algorithms often exhibit bias against larger delays. We present fridges, a novel data structure that allows for the correction of the survivorship bias due to hash collisions. The main idea is to keep track of the probability p that a delay sample is collected, and count it as 1/p samples. Using multiple fridges together, we can further improve the accuracy by computing a weighted average of single-fridge estimators.

• We present ecient algorithms for identifying IP prefixes with heavy packet reordering. First, we sample as many flows as possible, regardless of their sizes, but only for a short period at a time. Next, we separately monitor the large flows over long periods, in addition to the flow sampling. Both algorithms measure at the flow level, and aggregate statistics at the prefix level.

Existing counter-based algorithms for identifying heavy-hitter flows could also be modified to measure performance metrics. However, many of such algorithms, despite of showing good empirical performance, lack theoretical guarantees. In the second part, we present the first formal analysis for the performance of one such algorithm,

the Random Admission Policy (RAP).

• We show that, for a highly skewed packet stream with k heavy flows, RAP with memory size k stores O(k) heavy flows with constant probability.