封包分類和路由器之間有著密切的關係，在網路通信的結構中扮演著重要的角色。它不僅能幫助路由器快速辨識和分類封包，提高效能和效率，還支援服務品質管理（QoS），同時在網路安全中也扮演著重要的角色，例如提供防火牆、流量控制、虛擬私人網路（VPN）和負載平衡等功能。隨著時間的推移，網路的規模不斷擴大，為了更好地利用路由器在網路中的作用，軟體定義網路（SDN）的網路架構和管理方法逐漸興起，需要支援大規模和多維度規則集的快速分類。儘管基於軟體的方法具有靈活性和支援動態更新的優勢，但它需要較多的指令和計算，因此速度相對較慢。相比之下，基於硬體的封包分類方法能夠提供更高的處理速度和效能，實現快速的封包分類。然而，過去硬體方法受限於FPGA本身的記憶體資源大小，僅能支援5k、10k大小的規則集，無法應對更大的規則集。
在本論文中我們將架構實作於具有 Ultra RAM 的FPGA平台上，並對該方法進行硬體設計。Ultra RAM 是一種新提出的技術，它提供了大量的儲存資源，然而Ultra RAM 在實際應用中面臨一些挑戰和限制，例如固定的配置大小為4Kx72位。我們提出了一種儲存方法可以有效地減少在記憶體中儲存規則集所需的空間，並且通過對規則集的特徵分析將其分割為4個子集，再根據每個子集中欄位的特性，選擇最合適的記憶體來存儲欄位以供下一階段封包比對使用。同時我們將封包比對分成多個階段來執行，以獲得優先權最高的匹配規則。
由於硬體資源中每種類型的記憶體具有不同的特性，我們的方法不僅關注如何使用更少的記憶體存儲更多的規則，還考慮了如何高效地利用Ultra RAM來優化數據結構。實驗結果表明我們的方法非常有效，透過管線化設計及平行處理的技巧使速度能夠達到264 MHz，將實驗結果與近期發表的TcbTree方法相比記憶體消耗減少了80%以上且速度加快了39%，並可以支援超過100k的多維規則集。

Packet classification and routers are closely linked and essential in network communication. They assist routers in rapidly identifying and classifying packets, improving performance and efficiency, while also enabling Quality of Service (QoS) management. Moreover, they contribute to network security through functionalities like firewalls, traffic control, Virtual Private Networks (VPNs), and load balancing. As networks continue to expand, Software-Defined Networking (SDN) architecture and management approaches have emerged to enhance router utilization, necessitating support for fast classification of large-scale and multi-dimensional rule sets.
Software-based methods offer flexibility and dynamic updates but entail more instructions and computations, resulting in relatively slower speeds. Conversely, hardware-based packet classification methods deliver higher processing speeds and performance, facilitating fast packet classification. However, traditional hardware methods were restricted by the FPGA's memory resource size, limiting their support to rule sets of sizes like 5k or 10k and preventing handling larger rule sets.
This paper presents an FPGA implementation of an architecture using Ultra RAM and conducts hardware design for this approach. Ultra RAM is a recently proposed technology that provides a significant amount of storage resources, offering a more efficient memory solution. However, Ultra RAM faces challenges and limitations in practical applications, such as a fixed configuration size of 4Kx72 bits. To address this, we propose a storage method that effectively reduces the required space for storing rule sets in memory. Additionally, through feature analysis on the rules, we group it into four subsets and select the most suitable memory for storing fields in each subset based on their characteristics for subsequent packet matching. Simultaneously, we divide packet matching into multiple stages to execute the highest priority matching rules.
Since each type of memory has different characteristics in hardware resources, our approach not only focuses on how to store more rules using less memory, but also considers how to efficiently use Ultra RAM to optimize the data structure. The experimental results show that our approach is very effective, achieving speedups up to 264 MHz through pipelined design and parallel processing techniques, reducing memory consumption by more than 80% and speeding up by 39% compared to the recently published TcbTree scheme, and supporting multidimensional rule sets of more than 100k.

[1] D. E. Taylor, “Survey and Taxonomy of Packet Classification Techniques,” ACM Computing Surveys (CSUR), vol. 37, no. 3, pp. 238–275, Sep. 2005, doi: 10.1145/1108956.1108958.
[2] P. Gupta and N. McKeown, “Classifying Packets with Hierarchical Intelligent Cuttings,” IEEE Micro, vol. 20, no. 1, pp. 34–41, Jan. 2000, doi: 10.1109/40.820051.
[3] S. Singh, F. Baboescu, G. Varghese, and J. Wang, “Packet Classification Using Multidimensional Cutting,” 2003.
[4] P. Gupta and N. McKeown, “Packet Classification on Multiple Fields,” in ACM Sigcomm, August 1999.
[5] V. Srinivasan, S. Suri, and G. Varghese, “Packet Classification Using Tuple Space Search,” ACM SIGCOMM Computer Communication Review, vol. 29, no. 4, pp. 135–146, Aug. 1999, doi: 10.1145/316194.316216.
[6] 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, doi: 10.1109/MM.2005.8.
[7] K. Lakshminarayanan, A. Rangarajan, and S. Venkatachary, “Algorithms for Advanced Packet Classification with Ternary CAMs.” in Proc. ACMSIGCOMM, 2005, pp. 193-204.
[8] S. Yi, B. K. Kim, J. Oh, J. Jang, G. Kesidis, and C. R. Das, “Memory-efficient Content Filtering Hardware for High-speed Intrusion Detection Systems,” Proceedings of the ACM Symposium on Applied Computing, pp. 264–269, 2007, doi: 10.1145/1244002.1244068.
[9] A. Majumdar et al., “A Massively Parallel, Energy Efficient Programmable Accelerator for Learning and Classification,” ACM Transactions on Architecture and Code Optimization (TACO), vol. 9, no. 1, Mar. 2012, doi: 10.1145/2133382.2133388.
[10] W. Li, X. Li, H. Li, and G. Xie, “CutSplit: A Decision-Tree Combining Cutting and Splitting for Scalable Packet Classification,” Proceedings - IEEE INFOCOM, vol. 2018-April, pp. 2645–2653, Oct. 2018, doi: 10.1109/INFOCOM.2018.8485947.
[11] Y. K. Chang and H. C. Chen, “Fast Packet Classification Using Recursive Endpoint-cutting and Bucket Compression on FPGA,” Computer Journal, vol. 62, no. 2, pp. 198–204, Feb. 2019, doi: 10.1093/COMJNL/BXY052.
[12] Y. Qi, L. Xu, B. Yang, Y. Xue, and J. Li, “Packet Classification Algorithms: From Theory to Practice,” Proceedings - IEEE INFOCOM, pp. 648–656, 2009, doi: 10.1109/INFCOM.2009.5061972.
[13] W. Jiang and V. K. Prasanna, “Field-split Parallel Architecture for High Performance Multi-match Packet Classification Using FPGAs,” Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 188–196, 2009, doi: 10.1145/1583991.1584044.
[14] T. Ganegedara and V. K. Prasanna, “StrideBV: Single Chip 400G+ Packet Classification,” 2012 IEEE 13th International Conference on High Performance Switching and Routing, HPSR 2012, pp. 1–6, 2012, doi: 10.1109/HPSR.2012.6260820.
[15] W. Li, D. Li, Y. Bai, W. Le, and H. Li, “Memory-efficient recursive scheme for multi-field packet classification,” IET Communications, vol. 13, no. 9, pp. 1319–1325, Jun. 2019, doi: 10.1049/IET-COM.2018.6038.
[16] B. Pfaff and et al, “The Design and Implementation of Open vSwitch,” in USENIX NSDI, 2015.
[17] J. Daly and E. Torng, “TupleMerge: Building Online Packet Classifiers by Omitting Bits,” in IEEE ICCCN, 2017.
[18] J. Daly and et al, “Tuplemerge: Fast Software Packet Processing for Online Packet Classification,” IEEE/ACM Transactions on Networking, 2019.
[19] Y. K. Chang and C. S. Hsueh, “Range-Enhanced Packet Classification Design on FPGA,” IEEE Trans Emerg Top Comput, vol. 4, no. 2, pp. 214–224, Apr. 2016, doi: 10.1109/TETC.2015.2449666.
[20] Xilinx, “7 Series FPGAs Overview” Available: http://www.xilinx.com/support/documentation/data_sheets/ds180_7Series_Overview.pdf.
[21] Xilinx, “UltraScale Architecture and Product Data Sheet: Overview” Available:
https://www.xilinx.com/support/documentation/data_sheets/ds890-ultrascale-overview.pdf
[22] D. E. Taylor and J. S. Turner, “Classbench: A Packet Classification Benchmark.” IEEE/ACM Trans. Networking, vol. 15, no. 3, pp. 499-511, Jun. 2007.
[23] Chang, Yeim-Kuan “An Improved Stride-based Encoding Scheme for Packet Classification with Update” in NCKU CIAL thesis,2015
[24] T. Banerjee-Mishra, S. Sahni, and G. S. Seetharaman, “PC-TRIO: A power efficient TCAM architecture for packet classifiers,” IEEE Trans. Computers, vol. 64, no. 4, pp. 1104–1118, 2015.
[25] F. Zane, G. Narlikar, and A. Basu, “CoolCAMs: Power-efficient TCAMs for forwarding engines,” in Proc. 22nd Annu. Joint Conf. IEEE Comput. Commun., pp. 42–52, 2003.
[26] K. Lakshminarayan, A. Rangarajan, and S. Venkatachary, “Algorithms for advanced packet classification with ternary CAMs,” in Proc. Conf. Appl., Technol., Archit., Protocols Comput. Commun., pp. 193–204, 2005.
[27] W. Jiang and V. K. Prasanna, “Scalable Packet Classification on FPGA,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 20, no. 9, pp. 1668–1680, Sep. 2012.
[28] Y. Chang and Y. Wang, “CubeCuts: A Novel Cutting Scheme for Packet Classification,” in Proc. AINA Workshops, 2012, pp. 274–279.
[29] Glenn Slayden, “Maximally entropy-preserving hash for reducing from 32-bits to...,” Retrieved Dec 10, 2019, from https://stackoverflow.com/questions/3058139/hash-32bit-int-to-16bit-int.
[30] Y. Xin, W. Li, G. Tang, T. Yang, X. Hu and Y. Wang, "FPGA-Based Updatable Packet Classification Using TSS-Combined Bit-Selecting Tree," in IEEE/ACM Transactions on Networking, 2022