Current software-based packet classification algorithms exhibit relatively poor performance, prompting many researchers to concentrate on novel frameworks and architectures that employ both hardware and software components. The Packet Classification with Incremental Update (PCIU) algorithm, Ahmed et al. (2010), is a novel and efficient packet classification algorithm with a unique incremental update capability that demonstrated excellent results and was shown to be scalable for many different tasks and clients. While a pure software implementation can generate powerful results on a server machine, an embedded solution may be more desirable for some applications and clients. Embedded, specialized hardware accelerator based solutions are typically much more efficient in speed, cost, and size than solutions that are implemented on general-purpose processor systems. This paper seeks to explore the design space of translating the PCIU algorithm into hardware by utilizing several optimization techniques, ranging from fine grain to coarse grain and parallel coarse grain approaches. The paper presents a detailed implementation of a hardware accelerator of the PCIU based on an Electronic System Level (ESL) approach. Results obtained indicate that the hardware accelerator achieves on average 27x speedup over a state-of-the-art Xeon processor. 1. Introduction The task of packet classification entails the matching of an incoming packet with rules (established in an existing classifier) to determine the type of action that would be appropriate. Although this problem has been studied extensively, the fast emergence of new network applications, coupled with the rapid growth of the Internet, has introduced many new challenges, and the research community remains motivated to design novel and efficient packet classification solutions. Packet classification plays a crucial role for a number of network services, including, but not limited to, policy-based routing, traffic billing, and preventing unauthorized access using firewalls. Moreover, packet classification algorithms that will scale to large, multifield databases are becoming essential for a variety of applications, including load balancers, network security appliances, and quality of service filtering. Unfortunately, the current, software-based packet classification algorithms exhibit relatively poor performance, prompting many researchers to concentrate on novel frameworks and architectures that employ both hardware and software components. The continuous explosive growth of Internet traffic will ultimately
References
[1]
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.
[2]
O. Ahmed and S. Areibi, “Software implementation of the PCIU algorithm,” 2013, http://deimos.eos.uoguelph.ca/sareibi/PUBLICATIONS_dr/software_code_dr/PCIU_Software.html.
[3]
RG, “Handel-C language reference manual,” Tech. Rep., Celoxica, Europe, 2005.
Calypto, “Catapult C synthesis,” 2012, http://www.calypto.com.
[6]
C. Bobda, Introduction to Reconfigurable Computing: Architectures, Algorithms and Applications, Springer, Dordrecht, The Netherlands, 2007.
[7]
J. Cong, B. Liu, S. Neuendorffer, J. Noguera, K. Vissers, and Z. Zhang, “High-level synthesis for FPGAs: from prototyping to deployment,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 4, pp. 473–491, 2011.
[8]
D. E. Taylor and J. S. Turner, “ClassBench: a packet classification benchmark,” in Proceedings of the 24th IEEE International Conference on Computer Communications (INFOCOM '05), pp. 2068–2079, Miami, Fla, USA, March 2005.
[9]
H. Lim and J. H. Mun, “High-speed packet classification using binary search on length,” in Proceedings of the 3rd ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS '07), pp. 137–144, New York, NY, USA, December 2007.
[10]
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.
[11]
G. S. Jedhe, A. Ramamoorthy, 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, Palo Alto, Calif, USA, April 2008.
[12]
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.
[13]
Y.-K. Chang, C.-I. Lee, and C.-C. Su, “Multi-field range encoding for packet classification in TCAM,” in Proceedings of the 30th IEEE International Conference on Computer Communications (INFOCOM '11), pp. 196–200, Shanghai, China, April 2011.
[14]
H. Le, W. Jiang, and V. K. Prasanna, “Scalable high-throughput sram-based architecture for ip-lookup using FPGA,” in Proceedings of the International Conference on Field Programmable Logic and Applications (FPL '08), pp. 137–142, September 2008.
[15]
I. Papaefstathiou and V. Papaefstathiou, “Memory-efficient 5D packet classification at 40 Gbps,” in Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM '07), pp. 1370–1378, Anchorage , Alaska , USA, May 2007.
[16]
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.
[17]
O. Ahmed, S. Areibi, K. Chattha, and B. Kelly, “PCIU: Hardware implementations of an efficient packet classification algorithm with an incremental update capability,” International Journal of Reconfigurable Computing, vol. 2011, Article ID 648483, 21 pages, 2011.
[18]
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, usa, May 2010.
[19]
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.
[20]
W. Jiang and V. K. Prasanna, “Scalable packet classification on FPGA,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, no. 99, pp. 1668–1680, 2011.
[21]
O. Ahmed, S. Areibi, and G. Grewal, “Hardware accelerators targeting a novel group based packet classification algorithm,” Journal of Reconfigurable Computing, vol. 2013, Article ID 681894, 33 pages, 2013.
[22]
D. E. Taylor, “Survey and taxonomy of packet classification techniques,” ACM Computing Surveys, vol. 37, no. 3, pp. 238–275, 2005.
[23]
D. Pellerin and S. Thibault, Practical FPGA Programming in C, Prentice Hall Press, Upper Saddle River, NJ, USA, 1st edition, 2005.
[24]
Xilinx, “C-based design: high level synthesis with vivado hls,” 2013, http://www.xilinx.com/training/dsp/high-level-synthesis-with-vivado-hls.htm.
