FD-Filter: A Compact Data Structure for Fine-Grained Intra-Flow Packet Delay Monitoring

Packet delay is a key indicator of network health. Traditional packet delays focus on coarse-grained per-hop or end-to-end delays. However, this paper focuses on Intra-Flow Packet Delay (IFPD). It is the arrival time span between two adjacent packets in each flow. IFPD allows detailed traffic arrival pattern analysis, addressing cases such as arrival jitter and APT detection, etc. Existing solutions fail to monitor IFPD with small memory and high accuracy. To this end, we propose FD-Filter, an extension of Bloom Filter, for IFPD. It comprises several window filters and an existence filter. The window filters store approximate timestamps for IFPD estimation. The existence filter selects newly-arrival flows for higher accuracy. FD-Filter employs four novel techniques: per-bit update and query for better accuracy, filter recycle for prolonged monitoring, counter combination for faster query, and lazy aging for hardware compatibility. Our experiments on real-world traces demonstrate the accuracy and efficiency of FD-Filter over existing approaches.