High-Performance String Matching Algorithm that accelerates network middlebox applications


DFC: High-Performance String Matching Algorithm


String matching is a performance-critical task for many middlebox applications, such as network intrusion detection systems and Web application firewalls. DFC is an efficient multi-pattern string matching algorithm that significantly reduces the number of memory accesses and cache misses by using small and cache-friendly data structures and avoids instruction pipeline stalls by minimizing sequential data dependency. Our evaluation shows that DFC improves performance by up to 3.6 times compared to the most widely used algorithm on real traffic workload. When applied to middlebox applications, DFC delivers 57-160% improvement in performance.


  1. NSDI
    DFC: Accelerating string pattern matching for network applications
    Byungkwon Choi, Jongwook Chae, Muhammad Jamshed, Kyoungsoo Park, and Dongsu Han
    In 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16) 2016