Packet delay is a crucial performance metric for real-time, network-based applications. Obtaining per-flow delay measurements is particularly important to network operators, but is computationally challenging in high-speed links. Recently, passive delay measurement techniques have been proposed that outperform traditional active probing in terms of accuracy and network overhead. However, such techniques rely on the empirical observation that packet delays across different flows are temporally correlated, an assumption that is not met in presence of traffic prioritization, load balancing policies, or due to intricacies of the switch fabric. We present a novel data structure called Lossy Difference Sketch (LDS) that provides per-flow delay measurements without relying on any specific delay model. LDS obtains a notable accuracy improvement compared to the state of the art with a small memory footprint and network overhead. The data structure can be sized according to target accuracy requirements or to fit a low memory budget. We deploy an actual implementation of LDS in an opera- tional research and education network and show that it obtains higher accuracy than temporal correlation-based techniques without exploiting any knowledge about the underlying delay model.

Peer Reviewed