This paper proposes a decision-tree-based linear multi-pipeline architecture on FPGA’s for packet sorting. We reflect on the next-generation packet classification problems where more than 5-tuple packet header fields has been classified. From traditional fixed 5-tuple matching, Multi-field packet classification has been evolved for flexible matching with arbitrary combination of numerous packet header fields. The recently proposed Open Flow switching requires classifying each packet using up to 12-tuple packet header fields. It become a great task to develop scalable solutions for next-generation packet classification that support larger rule sets, additional packet header fields and higher throughput. This paper proposes a 2-D multi-pipeline decision-tree-based architecture for next-generation packet classification which exploits the abundant parallelism and other desirable features such as current field-programmable gate arrays (FPGAs),. We propose several optimization techniques for the state-of-the-art decision-tree-based algorithm by examine the various traditional 5-tuple packet classification methods. By using set of 12-tuple rules, the framework has been developed to partition the rule set into multiple subsets each of which is built into an optimized decision tree. To maximize the memory utilization. a tree-to-pipeline mapping scheme is carefully designed while underneath high throughput. Our proposed architecture can store up to 1K synthetic 12-tuple rules or 10K real-life 5-tuple rules in on-chip memory of a single up to date FPGA, and maintain 80 or 40 Gbps throughput for least packets of size (40 bytes) respectively. To utilize the memory properly and to sustaining high throughput, a mapping scheme based on tree-to-pipeline is designed carefully. This paper deal with the profuse parallelism and other preferred features provided by present field-programmable gate arrays and propose a 2-D multi-pipeline decision tree based architecture for next-generation packet sorting. The Verilog Hardware description languages (VHDL) are used to design the proposed architecture and synthesized using Xilinx Software.
| Published in | International Journal of Wireless Communications and Mobile Computing (Volume 3, Issue 3) |
| DOI | 10.11648/j.wcmc.20150303.11 |
| Page(s) | 27-32 |
| Creative Commons |
This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited. |
| Copyright |
Copyright © The Author(s), 2024. Published by Science Publishing Group |
Field Programmable Gate Array (FPGA), Multi-Pipeline Architecture, Multi-Field Packet Classification, Open Flow Switching, 2-D Multi-Pipeline Decision-Tree-Based Architecture, 12-Tuple Rules, 5-Tuple Rules, Verilog Hardware Description Languages (VHDL)
| [1] | M. Casado, T. Koponen, D. Moon, and S. Shenker, “Rethinking packet forwarding hardware,” in Proc. Hot Nets—VII, 2008, pp. 1–6. |
| [2] | N. Mc Keown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “Open Flow: Enabling innovation in campus networks,” SIGCOMM Comput. Commun. Rev., vol. 38, no. 2, pp. 69–74, 2008. |
| [3] | Open Flow Foundation, “Open Flow Switch Specification, Version 1.0.0,” 2009. [Online]. Available: http://www.openflowswitch.org/documents/openflow-spec-v1.0.0.pdf |
| [4] | P. Gupta and N. Mc Keown, “Algorithms for packet classification,” IEEE Network, vol. 15, no. 2, pp. 24–32, 2001. |
| [5] | F. Yu, R. H. Katz, and T. V. Lakshman, “Efficient multimatch packet classification and lookup with TCAM,” IEEE Micro, vol. 25, no. 1, pp. 50–59, Jan. 2005. |
| [6] | K. Lakshminarayanan, A. Rangarajan, and S. Venkatachary, “Algorithms for advanced packet classification with ternary CAMs,” in Proc. SIGCOMM, 2005, pp. 193–204. |
| [7] | H. Song and J. W. Lockwood, “Efficient packet classification for network intrusion detection using FPGA,” in Proc. FPGA, 2005, pp. 238–245. |
| [8] | S. Dharmapurikar, H. Song, J. S. Turner, and J. W. Lockwood, “Fast packet classification using bloom filters,” in Proc. ANCS, 2006, pp. 61–70. |
| [9] | I. Papaefstathiou and V. Papaefstathiou, “Memory-efficient 5D packet classification at 40 Gbps,” in Proc. INFOCOM, 2007, pp. 1370–1378. |
| [10] | A. Nikitakis and I. Papaefstathiou, “A memory-efficient FPGA-based classification engine,” in Proc. FCCM, 2008, pp. 53–62. |
| [11] | W. Jiang and V. K. Prasanna, “Sequence-preserving parallel IP lookup using multiple SRAM-based pipelines,” J. Parallel Distrib. Comput., vol. 69, no. 9, pp. 778–789, 2009. |
| [12] | H. Yu and R. Mahapatra, “A power- and throughput-efficient packet classifier with n bloom filters,” IEEE Trans. Comput., vol. 60, no. 8, pp. 1182–1193, Aug. 2011. |
| [13] | W. Jiang and V. K. Prasanna, “Large-scale wire-speed packet classification on FPGAs,” in Proc. FPGA, 2009, pp. 219–228. |
| [14] | I. Sourdis, “Designs & algorithms for packet and content inspection” Ph.D. dissertation, Comput. Eng. Div., Delft Univ. Technol., Delft, The Netherlands, 2007. [Online]. Available: http://ce.et.tudelft.nl/publicationfiles/ 1464_564 sourdis phdthesis.pdf |
| [15] | G. S. Jedhe, A. Ramamoorthy, and K. Varghese, “A scalable high throughput firewall in FPGA,” in Proc. FCCM, 2008, pp. 43–52. |
| [16] | Xilinx, Inc., San Jose, CA, “Xilinx Virtex-6 FPGA family,”2009.[Online].Available:www.xilinx.com/products/virtex6/ |
| [17] | Altera Corp., San Jose, CA, “Altera Stratix IV FPGA,” 2009.[Online].Available:http://www.altera.com/products/devices/stratix-fpgas/ stratix-iv/ |
| [18] | D. E. Taylor, “Survey and taxonomy of packet classification techniques,” ACM Comput. Surv., vol. 37, no. 3, pp. 238–275, 2005. |
| [19] | T. V. Lakshman and D. Stiliadis, “High-speed policy-based packet forwarding using efficient multi-dimensional range matching,” in Proc. SIGCOMM, 1998, pp. 203–214. |
| [20] | S. Singh, F. Baboescu, G. Varghese, and J. Wang, “Packet classification using multidimensional cutting,” in Proc. SIGCOMM, 2003, pp. 213–224. |
| [21] | P. Gupta and N. McKeown, “Classifying packets with hierarchical intelligent cuttings,” IEEE Micro, vol. 20, no. 1, pp. 34–41, 2000. |
| [22] | D. E. Taylor and J. S. Turner, “Scalable packet classification using distributed crossproducing of field labels,” in Proc. INFOCOM, 2005, pp. 269–280. |
| [23] | W. Eatherton, G. Varghese, and Z. Dittia, “Tree bitmap: Hardware/ software IP lookups with incremental updates,” SIGCOMM Comput. Commun. Rev., vol. 34, no. 2, pp. 97–122, 2004. |
| [24] | Y. Luo, K. Xiang, and S. Li, “Acceleration of decision tree searching for IP traffic classification,” in Proc. ANCS, 2008, pp. 40–49. |
| [25] | A. Kennedy, X.Wang, Z. Liu, and B. Liu, “Low power architecture for high speed packet classification,” in Proc. ANCS, 2008, pp. 131–140. |
| [26] | Y. Luo, P. Cascon, E. Murray, and J. Ortega, “Accelerating Open Flow switching with network processors,” in Proc. ANCS, 2009, pp. 70–71. |
| [27] | J. Naous, D. Erickson, G. A. Covington, G. Appenzeller, and N. Mc Keown, “Implementing an Open Flow switch on the Net FPGA platform,” in Proc. ANCS, 2008, pp |
APA Style
R. Sathesh Raaj, J. Kumarnath. (2015). FPGA Based Packet Classification Using Multi-Pipeline Architecture. International Journal of Wireless Communications and Mobile Computing, 3(3), 27-32. https://doi.org/10.11648/j.wcmc.20150303.11
ACS Style
R. Sathesh Raaj; J. Kumarnath. FPGA Based Packet Classification Using Multi-Pipeline Architecture. Int. J. Wirel. Commun. Mobile Comput. 2015, 3(3), 27-32. doi: 10.11648/j.wcmc.20150303.11
AMA Style
R. Sathesh Raaj, J. Kumarnath. FPGA Based Packet Classification Using Multi-Pipeline Architecture. Int J Wirel Commun Mobile Comput. 2015;3(3):27-32. doi: 10.11648/j.wcmc.20150303.11
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.wcmc.20150303.11,
author = {R. Sathesh Raaj and J. Kumarnath},
title = {FPGA Based Packet Classification Using Multi-Pipeline Architecture},
journal = {International Journal of Wireless Communications and Mobile Computing},
volume = {3},
number = {3},
pages = {27-32},
doi = {10.11648/j.wcmc.20150303.11},
url = {https://doi.org/10.11648/j.wcmc.20150303.11},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.wcmc.20150303.11},
abstract = {This paper proposes a decision-tree-based linear multi-pipeline architecture on FPGA’s for packet sorting. We reflect on the next-generation packet classification problems where more than 5-tuple packet header fields has been classified. From traditional fixed 5-tuple matching, Multi-field packet classification has been evolved for flexible matching with arbitrary combination of numerous packet header fields. The recently proposed Open Flow switching requires classifying each packet using up to 12-tuple packet header fields. It become a great task to develop scalable solutions for next-generation packet classification that support larger rule sets, additional packet header fields and higher throughput. This paper proposes a 2-D multi-pipeline decision-tree-based architecture for next-generation packet classification which exploits the abundant parallelism and other desirable features such as current field-programmable gate arrays (FPGAs),. We propose several optimization techniques for the state-of-the-art decision-tree-based algorithm by examine the various traditional 5-tuple packet classification methods. By using set of 12-tuple rules, the framework has been developed to partition the rule set into multiple subsets each of which is built into an optimized decision tree. To maximize the memory utilization. a tree-to-pipeline mapping scheme is carefully designed while underneath high throughput. Our proposed architecture can store up to 1K synthetic 12-tuple rules or 10K real-life 5-tuple rules in on-chip memory of a single up to date FPGA, and maintain 80 or 40 Gbps throughput for least packets of size (40 bytes) respectively. To utilize the memory properly and to sustaining high throughput, a mapping scheme based on tree-to-pipeline is designed carefully. This paper deal with the profuse parallelism and other preferred features provided by present field-programmable gate arrays and propose a 2-D multi-pipeline decision tree based architecture for next-generation packet sorting. The Verilog Hardware description languages (VHDL) are used to design the proposed architecture and synthesized using Xilinx Software.},
year = {2015}
}
TY - JOUR T1 - FPGA Based Packet Classification Using Multi-Pipeline Architecture AU - R. Sathesh Raaj AU - J. Kumarnath Y1 - 2015/05/11 PY - 2015 N1 - https://doi.org/10.11648/j.wcmc.20150303.11 DO - 10.11648/j.wcmc.20150303.11 T2 - International Journal of Wireless Communications and Mobile Computing JF - International Journal of Wireless Communications and Mobile Computing JO - International Journal of Wireless Communications and Mobile Computing SP - 27 EP - 32 PB - Science Publishing Group SN - 2330-1015 UR - https://doi.org/10.11648/j.wcmc.20150303.11 AB - This paper proposes a decision-tree-based linear multi-pipeline architecture on FPGA’s for packet sorting. We reflect on the next-generation packet classification problems where more than 5-tuple packet header fields has been classified. From traditional fixed 5-tuple matching, Multi-field packet classification has been evolved for flexible matching with arbitrary combination of numerous packet header fields. The recently proposed Open Flow switching requires classifying each packet using up to 12-tuple packet header fields. It become a great task to develop scalable solutions for next-generation packet classification that support larger rule sets, additional packet header fields and higher throughput. This paper proposes a 2-D multi-pipeline decision-tree-based architecture for next-generation packet classification which exploits the abundant parallelism and other desirable features such as current field-programmable gate arrays (FPGAs),. We propose several optimization techniques for the state-of-the-art decision-tree-based algorithm by examine the various traditional 5-tuple packet classification methods. By using set of 12-tuple rules, the framework has been developed to partition the rule set into multiple subsets each of which is built into an optimized decision tree. To maximize the memory utilization. a tree-to-pipeline mapping scheme is carefully designed while underneath high throughput. Our proposed architecture can store up to 1K synthetic 12-tuple rules or 10K real-life 5-tuple rules in on-chip memory of a single up to date FPGA, and maintain 80 or 40 Gbps throughput for least packets of size (40 bytes) respectively. To utilize the memory properly and to sustaining high throughput, a mapping scheme based on tree-to-pipeline is designed carefully. This paper deal with the profuse parallelism and other preferred features provided by present field-programmable gate arrays and propose a 2-D multi-pipeline decision tree based architecture for next-generation packet sorting. The Verilog Hardware description languages (VHDL) are used to design the proposed architecture and synthesized using Xilinx Software. VL - 3 IS - 3 ER -
Information
Email: