隨著網路的快速發展，封包分類演算法逐漸成為網路中重要的角色，在很多地方都需要用到封包分類演算法，例如：防火牆、頻寬流量品質(QoS)、網路流量監測、虛擬私人網路(Virtual Private Network 簡稱VPN)等網路服務。
近年來，因為軟體定義網路(Software Defined Networking簡稱SDN)的出現，SDN所利用的是OpenFlow協定，所以傳統的封包分類演算法也需要跟著有所變動，在傳統的封包分類中，有五個維度，分別是Source IP、Destination IP、Source Port、
Destination Port 和 Protocal，然而在OpenFlow裡，封包分類方法必須支援到十二維或是十五維，在這篇論文中，我們的方法是根據方法[1]，進行延伸讓他可以支援到十二維。
高效能一直是封包分類演算法所追求的，在目前的演算法之中，實做在FPGA上面的方法，都擁有較高的效能，所以我們提出的方法也是實做在FPGA上，雖然實做在FPGA上可以提升效能，但是FPGA上的記憶體有一定的限制，所以如何分配記憶體使用是必須要克服的問題，加上為了實現管線化設計，將封包分類的規則分組平行處理也是個問題，針對上述的這些問題，我們根據OpenFlow 的封包規則特性提出了一個有效將封包規則分類成多個小群組並且不會產生太多的規則重複，可以有效的降低我們所用的資料結構大小，並且可以合適的放進FPGA上的記憶體。除此之外，透過將系統模組化的方法，我們可以將每一個管線裡的規則數量再降低，這樣可以更加的讓所需要的記憶體更少，最後我們使用折疊的方法，將管線的長度降低以減少過長的管線帶來的延遲。
我們所提出的方法是從An Improved Stride-based Encoding Scheme for Packet Classification with Update [2] 和Range Enhanced Packet Classification Designed on FPGA [16] 這兩篇論文延伸出來的，並且可以支援到5K的規則，速度可以達到255MHz，雖然速度上不及[2]、[16]和一些實做在FPGA上的方法，但是在硬體資源使用上，當規則數在5K時在virtex-6的FPGA硬體資源使用上只用到1%的36KB的Block RAM、10%的18KB的Block RAM和5%的slice LUT，而在[2]和[16]的方法中須分別使用到15%的Block RAM和48%的slice LUT與90%的Block RAM和56%的slice LUT，明顯地，我們的方法有更好的硬體資源使用效率，因此，我們所提出的方法可以比其他方法支援到最多50K的rules，甚至是實做雙管線架構來達到443MHz的高效能，如此一來就比其他的方法擁有更高的輸出效能。

With the rapid development of the Internet, packet classification becomes an important role gradually. Packet classification has been used everywhere, e.g., Firewall, Quality of Service (Qos), network traffic monitoring, Virtual Private Network (VPN).
In recent year, because of emergence of Software Defined Networking (SDN) which is associated with OpenFlow protocol. So the methods which supported traditional 5-dimension packet must be redesigned. There are 5 dimensions in traditional packet and they are source IP, destination IP, source port, destination port and protocol respectively. However, in the OpenFlow protocol, methods of packet classification need to support 12 or 15 dimension. In this thesis, we propose a method base on [1]. We extended this method to support 12-dimension packet classification.
To achieve high performance, we implement our method on FPGA. Because the existing methods which implemented on FPGA often performed better. Although packet classification on FPGA can get high performance, the problem of memory usage needs to be consider. To raise the throughput, we use the architecture of pipeline to classify packets in parallel. Thus, to deal with those problem we propose a grouping method that can split the rule table into 129 small subgroups and cause little rule duplication according to OpenFlow table’s characteristic. It can help to reduce the size of data structure in the system and let data structure fit into FPGA’s memory. Besides, we use module scheme to cut down the number of rules in the each pipeline and it can reduce the data structure’s size again. Finally, the fold scheme we use can solve the problem that the latency result from the long pipeline stages.
The method we proposed is extended from An Improved Stride-based Encoding Scheme for Packet Classification with Update [2] and Range Enhanced Packet Classification Designed on FPGA [16] and it can support 5K rule table. The clock rate can reach 255MHz. It is slightly lower than other existing method but our method has good performance in term of hardware resource usage.
In hardware resource, our method only needs 1% of 36KB Block RAM, 10% of 18KB Block RAM and 5% of slice LUTs on virtex-6 FPGA when rule size is 5K but it needs 15% of 36KB Block RAM and 48% of slice LUTs in [2]. And it needs 56% of Block RAM and 90% of slice LUTs. Obviously, our method has the better resource efficiency. Because of resource efficiency, our method can support up to 50K rules. Even more, our method can be implemented in the architecture of dual port to reach the 443MHz of clock rate then the performance will better than [2], [16] and other existing method.

[1] 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, ACM. 1999.
[2] H. J. Yang and Y. K. Chang, “An Improved Stride-based Encoding Scheme for Packet Classification with Update.” Available:
http://ir.lib.ncku.edu.tw/handle/987654321/157104
[3] 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, ACM New York, NY, USA, 2009.
[4] T. Ganegedara and V. K. Prasanna. “StrideBV: Single Chip 400G+ Packet Classification.” In 13th IEEE International Conference on High Performance Switching and Routing (HPSR), pages 1-6, 2012.
[5] B. Vamanan, G. Voskuilen and T.N. Vijaykumar. “EffiCuts: Optimizing Packet Classification for Memory and Throughput.” In SIGCOMM '10 Proceedings of the ACM SIGCOMM, pages 207-218, 2010.
[6] S. Singh, F. Baboescu, G. Varghese and J. Wang. “Packet Classification Using Multidimensional Cutting.” In SIGCOMM '03 Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, pages 213-224.
[7] P. Gupta and N. McKeown, “Algorithms for packet classification.” IEEE Network, vol.15, no. 2, pp.24–32, 2001.

[8] N. McKeown, T. Anderson, H.Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker and J. Turner, “OpenFlow: Enabling innovation in campus networks,” In ACM SIGCOMM Computer Communication. Volume 38 Issue 2, pages 69-74, April 2008.
[9] OpenFlow Foundation, “OpenFlow Switch Specification Version 1.1.0.” Available: http://archive.openflow.org/documents/openflow-spec-v1.1.0.pdf
[10] S. H. Shaikot and M. S. Kim, “Lightweight Traffic-Aware Packet Classification for Continuous Operation.” In SAINT '10 Proceedings of the 2010 10th IEEE/IPSJ International Symposium on Applications and the Internet, pages 59-67.
[11] T. Ganegedara and V. K. Prasanna, “StrideBV: Single Chip 400G+ Packet Classification.” In 13th IEEE International Conference on High Performance Switching and Routing (HPSR), pp. 1-6, 2012.
[12] Z. Ruan, X. F. Li and W. J. Li, “An Energy-efficient TCAM-based Packet Classification with Decision-tree Mapping.” In IEEE International Conference of IEEE Region 10 (TENCON 2013), pages 1-5 , 2013.
[13] S. Alinezhad and H. Saidi “Efficient Low Power Packet Classification by Grouping TCAM Rules.” In Telecommunications Forum (TELFOR), pages 1531-1535, 2011.
[14] Y. C. Cheng and P.C. Wang. “Scalable Multi-match Packet Classification Using
TCAM and SRAM.” In IEEE Transactions on Computers (Volume:65, Issue: 7, pages 2257-2269)
[15] S. Zhou, S. Zhao and Viktor K. Prasanna. “400 Gbps Energy-Efficient Multi-Field Packet Classification on FPGA.” In 2014 International Conference on ReConFigurable Computing and FPGAs (ReConFig14), pages. 1-6.
[16] Y. K. Chang and C. S. Hsueh, “Range Enhanced Packet Classification Design on FPGA.” Emerging Topics in Computing, IEEE Transactions on, 2015.
[17] T. Ganegedara, W. Jiang, and V. Prasanna, "Frug: A benchmark for packet forwarding in future networks," in Proc. IPCCC '10, IPCCC '10, 2010.
[18] Xilinx, “Virtex-6 Family Overview” Available: http://www.xilinx.com/support/documentation/data_sheets/ds150.pdf
[19] Xilinx, “7 Series FPGAs Overview” Available: http://www.xilinx.com/support/documentation/data_sheets/ds180_7Series_Overview.pdf.
[20] T. Ganegedara, W. Jiang, and V. K. Prasanna.“A Scalable and Modular Architecture for High-Performance Packet Classification.” In IEEE transactions on parallel and distributed systems (TPDS), 2013.
[21] W. Jiang and V. K. Prasanna, “Scalable Packet Classification on FPGA.” In IEEE Transactions on Very Large Scale Integration (VLSI) Systems(Volume:20, Issue: 9), pages 1668–1680, 2012.
[22] Y. R. Qu, S. J. Zhou, and V. K. Prasanna, “High-performance architecture for dynamically updatable packet classification on FPGA.” In Architectures for Networking and Communications Systems (ANCS), 2013 ACM/IEEE Symposium on.
[23] Route Views by University of Oregon [Online]:
http://www.routeviews.org.