  Network performance problems are notoriously difficult to diagnose. Prior
profiling systems collect performance statistics by keeping information about
each network flow, but maintaining per-flow state is not scalable on
resource-constrained NIC and switch hardware. Instead, we propose sketch-based
performance monitoring using memory that is sublinear in the number of flows.
Existing sketches estimate flow monitoring metrics based on flow sizes. In
contrast, performance monitoring typically requires combining information
across pairs of packets, such as matching a data packet with its acknowledgment
to compute a round-trip time. We define a new class of \emph{lean} algorithms
that use memory sublinear in both the size of input data and the number of
flows. We then introduce lean algorithms for a set of important statistics,
such as identifying flows with high latency, loss, out-of-order, or
retransmitted packets. We implement prototypes of our lean algorithms on a
commodity programmable switch using the P4 language. Our experiments show that
lean algorithms detect $\sim$82\% of top 100 problematic flows among real-world
packet traces using just 40KB memory.
