Advertisement
Published in:
2010 | OriginalPaper | Chapter
10. Fast Packet Pattern-Matching Algorithms
Authors : Fang Yu, Yanlei Diao, Randy H. Katz, T. V. Lakshman
Published in: Algorithms for Next Generation Networks
Publisher: Springer London
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Packet content scanning at high speed has become extremely important due to its applications in network security, network monitoring, HTTP load balancing, etc. In content scanning, the packet payload is compared to a set of patterns specified as regular expressions. In this chapter, we first describe the typical patterns used in packet-scanning applications and show that for some of these patterns the memory requirements can be prohibitively high when traditional matching methods are used. We then review techniques for efficient regular expression matching and explore regular expression rewrite techniques that can significantly reduce memory usage. Based on new rewrite insights, we propose guidelines for pattern writers to make matching fast and practical. Furthermore, we discuss deterministic finite automaton (DFA) link compression techniques and review algorithms and data structures that are specifically designed for matching regular expressions in networking applications.