2019/11/16 by Zaoxing Liu, Liu, Zaoxing, Samson Zhou +7 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Network Traffic and Congestion Control #Networking and Internet Architecture (cs.NI) #Software System Performance and Reliability #Software-Defined Networks and 5G
paper · pdf · doi:10.48550/arxiv.1911.06951
openalex publication_date 2019/11/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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 ∼82% of top 100 problematic flows among real-world packet traces using just 40KB memory.