%0 Journal Article
%T Hardware Accelerators Targeting a Novel Group Based Packet Classification Algorithm
%A O. Ahmed
%A S. Areibi
%A G. Grewal
%J International Journal of Reconfigurable Computing
%D 2013
%I Hindawi Publishing Corporation
%R 10.1155/2013/681894
%X Packet classification is a ubiquitous and key building block for many critical network devices. However, it remains as one of the main bottlenecks faced when designing fast network devices. In this paper, we propose a novel Group Based Search packet classification Algorithm (GBSA) that is scalable, fast, and efficient. GBSA consumes an average of 0.4£¿megabytes of memory for a 10£¿k rule set. The worst-case classification time per packet is 2 microseconds, and the preprocessing speed is 3 M rules/second based on an Xeon processor operating at 3.4£¿GHz. When compared with other state-of-the-art classification techniques, the results showed that GBSA outperforms the competition with respect to speed, memory usage, and processing time. Moreover, GBSA is amenable to implementation in hardware. Three different hardware implementations are also presented in this paper including an Application Specific Instruction Set Processor (ASIP) implementation and two pure Register-Transfer Level (RTL) implementations based on Impulse-C and Handel-C flows, respectively. Speedups achieved with these hardware accelerators ranged from 9x to 18x compared with a pure software implementation running on an Xeon processor. 1. Introduction Packet classification is the process whereby packets are categorized into classes in any network device. A packet is said to match a particular rule if all the fields of the header of satisfy the regular expression of . Table 1 gives an example of a twelve-rule classifier. Each rule contains five fields. The source and destination IP address are 32 bits each, while the source and destination port address are 16 bits each. An 8-bit address represents the protocol. Both IP and protocol are in starting ¡°base/mask¡± format, while the ports are in range (starting£¿:£¿ending) format. The IP address should be converted to a range format by using the mask field. For example, an IP address ¡°0.83.4.0/22¡± can be converted to a range by using the mask of 22 bits or 255.255.252.0 to produce the low part of the range (0.83.4.0). The high part of the range can be generated using the following formula: High = Low OR . Thus, the IP 0.83.4.0/22 can be converted to 0.83.4.0 as the low part and 0.83.7.255 as the high part. When the mask equals 32, the IP is represented in exact format, which translates to a match of the IP. All fields which are in prefix (or exact format) in Table 1 can be easily converted to a range of high and low fields using the above formula. It is important to remember that when the IP address is converted to a range format, the length of the IP
%U http://www.hindawi.com/journals/ijrc/2013/681894/