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
References
[1]
D. Joseph, Packet classification as a fundamental network primitive [Ph.D. thesis], EECS Department, University of California, Berkeley, NC, USA, 2009.
[2]
S. S. F. Baboescu and G. Varghese, “Packet classification for core routers: is there an alternative to CAMs?” in Proceedings of the Conference of the IEEE Computer and Communications, vol. 1, pp. 53–63, April 2003.
[3]
O. Ahmed, K. Chattha, and S. Areibi, “A hardware/software co-design architecture for packet classification,” in Proceedings of the IEEE International Conference on Microelectronics, pp. 96–99, Cairo, Egypt, December 2010.
[4]
D. Taylor, “Survey and taxonomy of packet classification techniques,” ACM Computing Surveys, vol. 37, no. 3, pp. 238–275, 2005.
[5]
P. Gupta and N. McKeown, “Classifying packets with hierarchical intelligent cuttings,” IEEE Micro, vol. 20, no. 1, pp. 34–41, 2000.
[6]
G. V. S. Singh, F. Baboescu, and J. Wang, “Packet classification using multidimensional cutting,” in Proceedings of the Conference on Applications, Architectures and Protocols for Computer Communications, pp. 213–224, ACM, New York, NY, USA, 2003.
[7]
A. G. Priya and H. Lim, “Hierarchical packet classification using a Bloom filter and rule-priority tries,” Computer Communications, vol. 33, no. 10, pp. 1215–1226, 2010.
[8]
P. Gupta and N. McKeown, “Packet classification on multiple fields,” in Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, pp. 147–160, ACM, New York, NY, USA, 1999.
[9]
F. Baboescu and G. Varghese, “Scalable packet classification,” IEEE/ACM Transactions on Networking, vol. 13, no. 1, pp. 2–14, 2005.
[10]
T. Lakshman and D. Stiliadis, “High-speed policy-based packet forwarding using efficient multi-dimensional range matching,” ACM SIGCOMM Computer Communication Review, vol. 28, no. 4, pp. 203–214, 1998.
[11]
O. Ahmed, S. Areibi, and D. Fayek, “PCIU: an efficient packet classification algorithm with an incremental update capability,” in Proceedings of the International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS '10), pp. 81–88, Ottawa, Canada, July 2010.
[12]
S. S. V. Srinivasan and G. Varghese, “Packet classification using tuple space search,” in Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, pp. 135–146, ACM, New York, NY, USA, 1999.
[13]
S. S. P. Warkhede and G. Varghese, “Fast packet classification for two-dimensional conflict-free filters,” in Proceedings of the Conference of the IEEE Computer and Communications Societies (INFOCOM '01), vol. 3, pp. 1434–1443, 2001.
[14]
A. Ramamoorthy, G. S. Jedhe, and K. Varghese, “A scalable high throughput firewall in FPGA,” in Proceedings of the 16th IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM '08), pp. 43–52, April 2008.
[15]
C. R. Meiners, A. X. Liu, and E. Torng, “Topological transformation approaches to TCAM-Based packet classification,” IEEE/ACM Transactions on Networking, vol. 19, no. 1, pp. 237–250, 2011.
[16]
Y.-K. Chang, C.-I. Lee, and C.-C. Su, “Multi-field range encoding for packet classification in TCAM,” in Proceedings of the IEEE INFOCOM, pp. 196–200, April 2011.
[17]
H. Le, W. Jiang, and V. K. Prasanna, “Scalable high-throughput sram-based architecture for ip-lookup using FPGA,” in Proceedings of the 2008 International Conference on Field Programmable Logic and Applications (FPL '08), pp. 137–142, September 2008.
[18]
I. Papaefstathiou and V. Papaefstathiou, “Memory-efficient 5D packet classification at 40？Gbps,” in Proceedings of the 26th IEEE International Conference on Computer Communications (IEEE INFOCOM '07), pp. 1370–1378, May 2007.
[19]
A. Nikitakis and I. Papaefstathiou, “A memory-efficient FPGA-based classification engine,” in Proceedings of the 16th IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM '08), pp. 53–62, April 2008.
[20]
O. Ahmed, K. Chattha, S. Areibi, and B. Kelly, “PCIU: hardware implementation of an efficient packet classification algorithm with an incremental update capability,” International Journal of Reconfigurable Computing, 2011.
[21]
Y.-K. Chang, Y.-S. Lin, and C.-C. Su, “A high-speed and memory efficient pipeline architecture for packet classification,” in Proceedings of the 18th IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM '10), pp. 215–218, May 2010.
[22]
G. Antichi, A. Di Pietro, S. Giordano, G. Procissi, D. Ficara, and F. Vitucci, “On the use of compressed DFAs for packet classification,” in Proceedings of the 15th IEEE International Workshop on Computer Aided Modeling, Analysis and Design of Communication Links and Networks (CAMAD '10), pp. 21–25, December 2010.
[23]
W. Jiang and V. K. Prasanna, “Scalable packet classification on FPGA,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 20, no. 9, pp. 1668–1680, 2011.
[24]
Z. Liu, A. Kennedy, X. Wang, and B. Liu, “Low power architecture for high speed packet classification,” in Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS '08), pp. 131–140, ACM, New York, NY, USA, November 2008.
[25]
D. Taylor and J. Turner, “Classbench: a packet classification benchmark,” in Proceedings of the IEEE INFOCOM, pp. 2068–2079, 2005.
[26]
O. Ahmed and S. Areibi, “GBSA: a group based search algorithm for packet classification,” in Proceedings of the IEEE International Workshop on Traffic Analysis and Classification (TRAC '11), pp. 1789–1794, Istanbul, Turkey, July 2011.
[27]
“Xtensa instruction set architecture (ISA),” Technical Publications 95054, Tensilica Inc., Santa Clara, Calif, USA, 2012.
[28]
Tensilica, “Xtensa processor extensions for fast ip packet classification,” Tech. Rep. AN02-603-00, Tensilica Inc., Santa Clara, Calif, USA, 2002.
