Unbiased Delay Measurement in the Data Plane
Yufei Zheng, Xiaoqi Chen, Mark Braverman, Jennifer Rexford · Society for Industrial and Applied Mathematics eBooks · 2022
Network administrators are interested in measuring the distribution of delays (the time between a request and its response), by directly running succinct algorithms within high-speed network devices. Unfortunately, the considerable gap between the small available memory and the huge volume of arriving traffic makes it challenging to design an algorithm that accurately measures delays. Existing algorithms exhibit bias against samples with higher delays. We present fridges, a novel data structure that corrects for the survivorship bias due to hash collisions, producing unbiased estimates of the delay distribution. The key idea is to consider a sample that was lucky enough to survive many insertions into the data structure as a representative for other similar samples that did not survive. We also show how to combine results from multiple fridges, each optimized for a different range of delays, for further accuracy gains. Simulation experiments show our design outperforms prior work using naive hash-indexed arrays, achieving 2x-4x memory saving. We implement a prototype P4 program running on the Intel Tofino programmable switch, using only moderate hardware resources.