封包分類在現今的網路架構中，扮演著一個相當重要的角色，它可以提供的服務像是防火牆、頻寬品質管理(QoS)、網路流量控制與虛擬私有網路(VPNs)等其他服務。但在近年來，隨著網路發展快速與軟體定義網路的出現(SDN)，針對傳統五維的規則集所使用的封包分類方法必須被延伸支援現在的十二維及十五維的規則集。因此，現在所面臨到的議題是如何同時支援更多的維度與容納大量的規則集並且達到高效能。為了達到高效能，現存方法都是實作於硬體FPGA上，而這些方法雖然都含有較高的效能，卻往往因使用到的記憶體超過FPGA本身所包含的記憶體而無法容納較大的規則集。
在這篇論文中，我們透過觀察現存的方法[11]，發現到當在使用Virtex系列的 FPGA時，會受到FPGA本身的記憶體特性的影響，可能會額外配置一些沒有被使用到的記憶體空間，而這些浪費掉的空間就會影響到可以支援的規則數。因此，我們會基於stride與使用Bit-Vector的方式來提出一個分組方法來改善上述的問題與更新的架構，而伴隨而來的好處是其他資源的使用量也會減少。根據實作在Xilinx Virtex-7 XC7V2000T FPGA上的實驗結果，我們的方法可以支援5K條以上的十二維的規則，而透過管線化設計以及平行處裡技巧，使速度能夠達到366MHz，並且相較於現存的方法使用了較少的記憶體(bytes/rule)與可以支援較多的規則數。

Packet classification plays a very important role in today's network architecture, and that can support many services such as firewall, Quality of Service (QoS), traffic control, virtual private network (VPNs), etc. But in recent years, with the rapid development of the Internet and the emergence of software-defined networking (SDN), the methods used for the traditional 5-dimensional packet classification must be extended to support the current rule set which is 12-dimension or 15-dimension. Therefore, how to simultaneously support more dimensions and support large rule sets and still achieve high throughput is the major issue of current design. To achieve high performance, the existing methods are implementations on hardware FPGA. Although these methods contain a high performance, they are often unable to accommodate the larger set of rules because of the restriction of on-chip memory on FPGA. In this thesis, by observing the existing methods [11], we can find that when using the memory of Xilinx Virtex-Series FPGA, the memory may be configured more than we need because of the affected memory characteristics FPGA itself. These wasted space will affect the number of rules that can be supported. Therefore, we will propose a grouping method and update architecture based on stride-based method with Bit-Vector to solve the problem. And the consequent benefit is the amount of other resources that will also be reduced. Based on our implementation result on Xilinx Virtex-7 XC7V2000T, we can support more than 5K 12-dimension rules. By using the pipelined and parallel architecture, the sustained clock rate is more than 366 MHz, and our approach uses less memory (bytes / rule) and can support more number of rules than the existing methods.

[1] P. Gupta and N. McKeown, “Algorithms for packet classification.” IEEE Network, vol.15, no. 2, pp.24–32, 2001.
[2] N. McKeown, T. Anderson,H.Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “OpenFlow: Enabling innovation in campus networks,” SIGCOMM Comput. Commun. Rev., vol. 38, no. 2, pp. 69–74, 2008.
[3] OpenFlow Foundation, “OpenFlow Switch Specification Version 1.0.0.”Available: http://www.openflowswitch.org/documents/openflow-spec-v1.0.0.pdf
[4] OpenFlow Foundation, “OpenFlow Switch Specification Version 1.1.0.”Available: http://archive.openflow.org/documents/openflow-spec-v1.1.0.pdf
[5] S. Singh, F. Baboescu, G. Varghese, and J. Wang, “Packet classification using multidimensional cutting,” in Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications (ACM SIGCOMM 2003), 2003, pp. 213–224.
[6] B. Vamanan, G. Voskuilen, and T. N. Vijaykumar. “EffiCuts: Optimizing Packet Classification for Memory and Throughput,” in Proceedings of the 2010 conference on Applications, technologies, architectures, and protocols for computer communications, 2010, pp. 207-218
[7] W. Jiang and V. K. Prasanna. “Field-split parallel architecture for high performance multi-match packet classification using FPGA.” In Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, SPAA ’09, pages 188–196, New York, NY, USA, 2009. ACM.
[8] T. Ganegedara and V. K. Prasanna, “StrideBV: Single Chip 400G+ Packet Classification.” In 13th IEEE International Conference on High Performance Switching and Routing (HPSR), 2012, pp. 1-6.
[9] F. Yu, R. H. Katz, and T. V. Lakshman, “Efficient Multi match Packet Classification and Lookup with TCAM.” IEEE Micro, vol. 25, no. 1, pp. 50-59, 2005.
[10] K. Lakshminarayanan, A. Rangarajan, and S. Venkatachary, “Algorithms for Advanced Packet Classification with Ternary CAMs.” in Proc. ACMSIGCOMM, 2005, pp. 193-204.
[11] Chang, Yeim-Kuan; Hsueh, Chun-Sheng, “Range Enhanced Packet Classification Design on FPGA.” Emerging Topics in Computing, IEEE Transactions on, 2015.
[12] P. Gupta and N. McKeown. “Packet classification on multiple fields.” In Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, SIGCOMM ’99,pages 147–160, New York, NY, USA, 1999. ACM.
[13] H. Song and J. W. Lockwood. “Efficient packet classification for network intrusion detection using FPGA.” In Proceedings of the 2005ACM/SIGDA 13th international symposium on Field-programmable gate arrays, FPGA ’05, pages 238–245, New York, NY, USA, 2005. ACM.
[14] P. Gupta and N. McKeown. “Classifying packets with hierarchical intelligent cuttings.” Micro, IEEE, 20(1):34–41, Jan/Feb 2000.
[15] Xilinx, “Virtex-6 Family Overview” Available: http://www.xilinx.com/support/documentation/data_sheets/ds150.pdf
[16] Xilinx, “7 Series FPGAs Overview” Available: http://www.xilinx.com/support/documentation/data_sheets/ds180_7Series_Overview.pdf.
[17] Yun R. Qu, Shijie Zhou, and Viktor K. Prasanna, “High-performance architecture for dynamically updatable packet classification on FPGA.”ANCS, 2013.
[18] A. Basu and G. Narlikar, &ldquo,Fast Incremental Updates for Pipelined Forwarding Engines,&rdquo, Proc. IEEE INFOCOM ',03, pp. ,64-74, 2003.
[19] T. Ganegedara, W. Jiang, and V. Prasanna, "Frug: A benchmark for packet forwarding in future networks," in Proc. IPCCC '10, IPCCC '10, 2010.
[20] W. Jiang and V. K. Prasanna, “Scalable Packet Classification on FPGA, ” IEEE Trans. VLSI Syst., vol. 20, no. 9, pp. 1668–1680, 2012.
[21] T. Ganegedara, W. Jiang, and V. K. Prasanna.“A Scalable and Modular Architecture for High-Performance Packet Classification,” TPDS, 2013.