Reconfigurable content-based router using hardware-accelerated language parser

ABSTRACT

This article presents a dense logic design for matching multiple regular expressions with a field programmable gate array (FPGA) at 10+ Gbps. It leverages on the design techniques that enforce the shortest critical path on most FPGA architectures while optimizing the circuit size. The architecture is capable of supporting a maximum throughput of 12.90 Gbps on a Xilinx Virtex 4 LX200 and its performance is linearly scalable with size. Additionally, this article presents techniques for parsing data streams to provide semantic information for patterns found within a data stream. We illustrate how a content-based router can be implemented with our parsing techniques using an XML parser as an example. The content-based router presented was designed, implemented, and tested in a Xilinx Virtex XCV2000E FPGA on the FPX platform. It is capable of processing 32-bits of data per clock cycle and runs at 100 MHz. This allows the system to process and route XML messages at 3.2 Gbps.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Andrew W. Appel, Modern compiler implementation in Java, Cambridge University Press, New York, NY, 1997
• 3: Baker, Z. and Hong-Jip Jung, V. K. P. 2006. Regular expression software deceleration for intrusion detection systems. In Proceedings of the International Conference on Field-Programmable Logic and Applications (FPL). Madrid, Spain.
• 4: Zachary K. Baker , Viktor K. Prasanna, A Methodology for Synthesis of Efficient Intrusion Detection Systems on FPGAs, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.135-144, April 20-23, 2004
• 5: Bispo, J., Sourdis, I., Cardoso, J. M., and Vassiliadis, S. 2006. Regular expression matching for reconfigurable packet inspection. In Proceedings of the International Conference on Field Programmable Technology (FPT). Bangkok, Thailand.
• 6: Cho, Y. H. and Mangione-Smith, W. H. 2005. High-performance context-free parser for polymorphic malware detection. In Proceedings of the Advanced Networking and Communications Hardware Workshop.
• 7: Young H. Cho , Shiva Navab , William H. Mangione-Smith, Specialized Hardware for Deep Network Packet Filtering, Proceedings of the Reconfigurable Computing Is Going Mainstream, 12th International Conference on Field-Programmable Logic and Applications, p.452-461, September 02-04, 2002
• 8: Cristian Ciressan , Eduardo Sanchez , Martin Rajman , Jean-Cedric Chappelier, An FPGA-Based Coprocessor for the Parsing of Context-Free Grammars, Proceedings of the 2000 IEEE Symposium on Field-Programmable Custom Computing Machines, p.236, April 17-19, 2000
• 9: Clark, C. R. and Schimmel, D. E. 2003. Efficient reconfigurable logic circuits for matching complex network intrusion detection patterns. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL). Lisbon, Portugal, 956--959.
• 10: Cristian-Raul, C., Eduardo, S., and Martin, R. 2001. An FPGA-based syntactic parser for real-life unrestricted context-free grammars. Tech. rep. No. 01/373 01/373, Swiss Federal Institute of Technology (EPFL), Lausanne, (Switzerland).
• 11: B. L. Hutchings , R. Franklin , D. Carver, Assisting Network Intrusion Detection with Reconfigurable Hardware, Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.111, September 22-24, 2002
• 12: A Parallel Parsing VLSI Architecture for Arbitrary Context Free Grammars, Proceedings of the 1998 International Conference on Parallel and Distributed Systems, p.783, December 14-16, 1998
• 13: James Moscola , Young H. Cho , John W. Lockwood, A Reconfigurable Architecture for Multi-Gigabit Speed Content-Based Routing, Proceedings of the 14th IEEE Symposium on High-Performance Interconnects, p.61-66, August 23-25, 2006 [doi>10.1109/HOTI.2006.7]
• 14: Moscola, J., Cho, Y. H., and Lockwood, J. W. 2006b. Fast semantic based identification of regular expressions using reconfigurable devices. Submitted to IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM). Napa, CA.
• 15: Moscola, J., Cho, Y. H., and Lockwood, J. W. 2006c. Reconfigurable context-free grammar based data processing hardware with error recovery. In Proceedings of International Parallel & Distributed Processing Symposium (IPDPS/RAW). Rhodes Island, Greece.
• 16: James Moscola , John Lockwood , Ronald P. Loui , Michael Pachos, Implementation of a Content-Scanning Module for an Internet Firewall, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.31, April 09-11, 2003
• 17: Martin Roesch, Snort - Lightweight Intrusion Detection for Networks, Proceedings of the 13th USENIX conference on System administration, November 07-12, 1999, Seattle, Washington
• 18: Reetinder Sidhu , Viktor K. Prasanna, Fast Regular Expression Matching Using FPGAs, Proceedings of the the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.227-238, April 29-May 02, 2001 [doi>10.1109/FCCM.2001.22]
• 19: Sourdis, I. and Pnevmatikatos, D. 2003. Fast, large-scale string match for a 10Gbps FPGA-based network intrusion detection system. In Proceedings of the 13th Conference on Field Programmable Logic and Applications. Springer-Verlag.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Design, Languages, Performance

Keywords:
Parsing, XML, content-based routing, parser hardware, pattern matching, regular expressions