SPArch: A Hardware-oriented Sketch-based Architecture for High-speed Network Flow Measurements

ACM Transactions on Privacy and Security, vol. 27, pp. 1–34

Abstract

Network flow measurement is an integral part of modern high-speed applications for network security and data-stream processing. However, processing at line rate while maintaining the required data structure within the on-chip memory of the hardware platform is a challenging task for measurement algorithms, especially when accuracy is of primary importance, such as in network security applications. Most of the existing measurement algorithms are no exception to such issues when deployed in high-speed networking environments and are also not tailored for efficient hardware implementation. Sketch-based measurement algorithms minimize the memory requirement and are suitable for high-speed networks but possess a low memory-accuracy trade-off and lack the versatility of individual flow mapping. To address these challenges, we present a hardware-friendly data structure named Sketch-based Pseudo-associative array Architecture (SPArch). SPArch is highly accurate and extremely memory-efficient, making it suitable for network flow measurement and security applications. The parallelism in SPArch ensures minimal and constant memory access cycles. Unlike other sketch architectures, SPArch provides the functionality of individual flow mapping similar to associative arrays, and the optimized version of SPArch allows the organization of counters in multiple buckets based on the flow sizes. An in-depth analysis of SPArch is carried out in this article and implemented SPArch on the Alveo data center accelerator card, demonstrating its suitability for high-speed networks.

Authors 6

1. Arish Sateesan

   KU Leuven

   Affiliation as printed

   ES&S-COSIC, ESAT, KU Leuven, Leuven, Belgium

2. Jo Vliegen

   KU Leuven

   Affiliation as printed

   ES&S-COSIC, ESAT, KU Leuven, Leuven Belgium

3. Simon Scherrer

   ETH Zurich

   Affiliation as printed

   Department of Computer Science, ETH Zurich, Zurich Switzerland

4. Hsu‐Chun Hsiao

   National Taiwan University · Academia Sinica

   Affiliation as printed

   National Taiwan University, Taipei Taiwan and Academia Sinica, Taipei Taiwan

   National Taiwan University, Taipei Taiwan

5. Adrian Perrig

   ETH Zurich

   Affiliation as printed

   Department of Computer Science, ETH Zurich, Zurich, Switzerland

6. Nele Mentens Aachen ES&S-COSIC

   Leiden University · KU Leuven

   Affiliation as printed

   ES&S-COSIC, ESAT, KU Leuven, Leuven Belgium and LIACS, Leiden University, Leiden, Netherlands

   LIACS, Leiden University, Leiden, Netherlands