  Current probabilistic flow-size monitoring can only detect heavy hitters
(e.g., flows utilizing 10 times their permitted bandwidth), but cannot detect
smaller overuse (e.g., flows utilizing 50-100% more than their permitted
bandwidth). Thus, these systems lack accuracy in the challenging environment of
high-throughput packet processing, where fast-memory resources are scarce.
Nevertheless, many applications rely on accurate flow-size estimation, e.g. for
network monitoring, anomaly detection and Quality of Service.
  We design, analyze, implement, and evaluate LOFT, a new approach for
efficiently detecting overuse flows that achieves dramatically better
properties than prior work. LOFT can detect 1.5x overuse flows in one second,
whereas prior approaches fail to detect 2x overuse flows within a timeout of
300 seconds. We demonstrate LOFT's suitability for high-speed packet processing
with implementations in the DPDK framework and on an FPGA.
