Low-Rate Overuse Flow Tracer (LOFT): An Efficient and Scalable Algorithm for Detecting Overuse Flows

Proceedings/Proceedings - Symposium on Reliable Distributed Systems, pp. 265–276

Abstract

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.50x overuse flows in one second, whereas prior approaches can only reliably detect flows that overuse their allocation by at least 3x. We demonstrate LOFT's suitability for high-speed packet processing with implementations in the DPDK framework and on an FPGA.

Authors 10

1. Simon Scherrer

   ETH Zurich

   Affiliation as printed

   ETH Zurich, Switzerland

   ETH Zürich

2. Che-Yu Wu

   National Taiwan University · ETH Zurich

   Affiliation as printed

   National Taiwan University, Taiwan

   ETH Zürich

3. Yu-Hsi Chiang

   National Taiwan University · ETH Zurich

   Affiliation as printed

   National Taiwan University, Taiwan

   ETH Zürich

4. Benjamin Rothenberger

   ETH Zurich

   Affiliation as printed

   ETH Zurich, Switzerland

   ETH Zürich

5. Daniele E. Asoni

   National Taiwan University · ETH Zurich

   Affiliation as printed

   ETH Zurich, Switzerland

   National Taiwan University

6. Arish Sateesan

   National Taiwan University · KU Leuven

   Affiliation as printed

   ESAT, KU Leuven, Belgium

   National Taiwan University

7. Jo Vliegen

   National Taiwan University · KU Leuven

   Affiliation as printed

   ESAT, KU Leuven, Belgium

   National Taiwan University

8. Nele Mentens Aachen

   Leiden University · KU Leuven

   Affiliation as printed

   ESAT, KU Leuven, Belgium

   LIACS, Leiden University, The Netherlands

   Katholieke Universiteit Leuven

9. Hsu‐Chun Hsiao

   National Taiwan University · KU Leuven

   Affiliation as printed

   National Taiwan University, Taiwan

   Katholieke Universiteit Leuven

10. Adrian Perrig

    ETH Zurich · KU Leuven

    Affiliation as printed

    ETH Zurich, Switzerland

    Katholieke Universiteit Leuven