A FPGA-based Parallel Architecture for Scalable High-Speed Packet Classification
Authors:
- Weirong JiangWJWeirong Jiang
- Viktor K. PrasannaVPViktor K. Prasanna
- 1 July 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636862,p. 24-31
Abstract
Multi-field packet classification is a critical function that enables network routers to support a variety of applications such as firewall processing, quality of service differentiation, traffic billing, and other value added services. Explosive growth of Internet traffic requires the future packet classifiers be implemented in hardware. However, most of the existing packet classification algorithms need large amount of memory, which inhibits efficient hardware implementations. This paper exploits the modern FPGA technology and presents a partitioning-based parallel architecture for scalable and high-speed packet classification. We propose a coarse-grained independent sets algorithm and then combine it seamlessly with the cross-producting scheme. After partitioning the original rule set into several coarse-grained independent sets and applying the cross-producting scheme for the remaining rules, the memory requirement is dramatically reduced. Our FPGA implementation results show that our architecture can store 10 K real-life rules in a single state-of-the-art FPGA while consuming a small amount of on-chip resources. Post place and route results show that the design sustains 90 Gbps throughput for minimum size (40 bytes) packets, which is more than twice the current backbone network link rate.Keywords
This publication has 21 references indexed in Scilit:
- Scalable packet classification with controlled cross-productingComputer Networks, 2009
- Acceleration of decision tree searching for IP traffic classification2008
- Low power architecture for high speed packet classification2008
- A Scalable High Throughput Firewall in FPGA2008
- Packet classification consuming small amount of memoryIEEE/ACM Transactions on Networking, 2005
- Scalable packet classification using distributed crossproducting of field labels2005
- Tree bitmapACM SIGCOMM Computer Communication Review, 2004
- Packet classification using multidimensional cutting2003
- High-speed policy-based packet forwarding using efficient multi-dimensional range matchingACM SIGCOMM Computer Communication Review, 1998
- Fast and scalable layer four switchingACM SIGCOMM Computer Communication Review, 1998