On-Demand Regular Expression Matching on FPGAs for Efficient Deep Packet Inspection

Deep Packet Inspection (DPI) faces significant bottlenecks in regular expression (regex) matching due to escalating rule complexity and traffic volume. Existing FPGA-based solutions inefficiently process all packets through every automaton, incurring substantial resource overhead. This paper proposes OD-REM, an on-demand regex matching architecture for FPGAs that dramatically improves efficiency. In addition to this novel architecture, OD-REM also introduces three innovations: (1) A counter-enabled Fast Reconfigurable Automaton (cFRA) compresses regex states by 97.5% via counting semantics, eliminating state explosion for bounded repetitions; (2) A Ring Queue (RQ) scheduler dynamically dispatches packets only to automata relevant to their candidate rules (identified via pre-filtering); (3) A modular pipeline for per-packet, on-chip runtime reconfiguration. Implemented on a Xilinx VU9P FPGA with 32 parallel cFRAs, OD-REM achieves 41.18 Gbps throughput—roughly 3× - 40× higher than the similar works while still performing a full reconfiguration on every packet. It reduces packet latency by 3.73 µs versus sliding-window scheduling. Integrated with Pigasus, OD-REM offloads complex rules, accelerating Hyperscan software matching by up to 37×. This work demonstrates FPGA-centric regex matching as a scalable, high-throughput solution for modern DPI systems.

• Publication year

  2025

• Venue

  ACM Transactions on Reconfigurable Technology and Systems

• Publication date

  2025-11-11

• Fields of study

  Not labeled

• Identifiers
  DOI 10.1145/3774651
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Combining MLIR Dialects with Domain-Specific Architecture for Efficient Regular Expression Matching

  2025cited by this paper
• BVAP: Energy and Memory Efficient Automata Processing for Regular Expressions with Bounded Repetitions

  2024cited by this paper
• ALVEARE: a Domain-Specific Framework for Regular Expressions

  2024cited by this paper
• vPIFO: Virtualized Packet Scheduler for Programmable Hierarchical Scheduling in High-Speed Networks

  2024cited by this paper
• Efficient Matching of Regular Expressions with Lookaround Assertions

  2024cited by this paper
• An Energy-Efficient Domain-Specific Architecture for Regular Expressions

  2023cited by this paper
• FPGA-CPU Architecture Accelerated Regular Expression Matching With Fast Preprocessing

  2023cited by this paper
• Regular Expression Matching using Bit Vector Automata

  2023cited by this paper
• Fidas: fortifying the cloud via comprehensive FPGA-based offloading for intrusion detection: industrial product

  2022influential reference
• Rosebud: Making FPGA-Accelerated Middlebox Development More Pleasant

  2022cited by this paper
• FRA-FPGA: Fast Reconfigurable Automata Processing on FPGAs

  2022influential reference
• Reconfigurable regular expression matching architecture for real-time pattern update and payload inspection

  2022cited by this paper
• FpgaNIC: An FPGA-based Versatile 100Gb SmartNIC for GPUs

  2022cited by this paper
• LAP: A Lightweight Automata Processor for Pattern Matching Tasks

  2021cited by this paper
• Reinhardt: Real-time Reconfigurable Hardware Architecture for Regular Expression Matching in DPI

  2021influential reference
• Teddy: An Efficient SIMD-based Literal Matching Engine for Scalable Deep Packet Inspection

  2021cited by this paper
• CICERO: A Domain-Specific Architecture for Efficient Regular Expression Matching

  2021cited by this paper
• High throughput token driven FSM based regex pattern matching for network intrusion detection system

  2021cited by this paper
• Regex matching with counting-set automata

  2020cited by this paper
• Grapefruit: An Open-Source, Full-Stack, and Customizable Automata Processing on FPGAs

  2020influential reference
• Fast, scalable, and programmable packet scheduler in hardware

  2019cited by this paper
• Hyperscan: A Fast Multi-pattern Regex Matcher for Modern CPUs

  2019influential reference
• Azure Accelerated Networking: SmartNICs in the Public Cloud

  2018cited by this paper
• A Dynamically Reconfigurable Automata Processor Overlay

  2017cited by this paper
• HARE: Hardware accelerator for regular expressions

  2016cited by this paper
• ANMLzoo: a benchmark suite for exploring bottlenecks in automata processing engines and architectures

  2016influential reference
• A Survey on Regular Expression Matching for Deep Packet Inspection: Applications, Algorithms, and Hardware Platforms

  2016cited by this paper
• Programmable Packet Scheduling at Line Rate

  2016cited by this paper
• Fast support for unstructured data processing: The unified automata processor

  2015influential reference
• An Efficient and Scalable Semiconductor Architecture for Parallel Automata Processing

  2014influential reference
• A Real-time Updatable FPGA-based Architecture for Fast Regular Expression Matching

  2014cited by this paper
• FLOWGUARD: building robust firewalls for software-defined networks

  2014cited by this paper
• A reconfigurable fabric for accelerating large-scale datacenter services

  2014cited by this paper
• A Dynamically Reconfigurable FPGA-Based Pattern Matching Hardware for Subclasses of Regular Expressions

  2012cited by this paper
• Designing a Programmable Wire-Speed Regular-Expression Matching Accelerator

  2012cited by this paper
• Dynamic reconfigurable bit-parallel architecture for large-scale regular expression matching

  2010cited by this paper
• Compact DFA Structure for Multiple Regular Expressions Matching

  2009cited by this paper
• Extending finite automata to efficiently match Perl-compatible regular expressions

  2008cited by this paper
• Optimization of Pattern Matching Circuits for Regular Expression on FPGA

  2007cited by this paper
• Regular expression matching for reconfigurable packet inspection

  2006cited by this paper
• Fast Regular Expression Matching Using FPGAs

  2001cited by this paper
• A new algorithm for scheduling periodic, real-time tasks

  1989cited by this paper
• Analysis and simulation of a fair queueing algorithm

  1989cited by this paper
• The compilation of regular expressions into integrated circuits

  1980cited by this paper
• The Queue M/G/1 with the Shortest Remaining Processing Time Discipline

  1966cited by this paper
• THE ABSTRACT THEORY OF AUTOMATA

  1961cited by this paper

• No citing papers are available for this paper.