封包分類演算法吸引了路由器設計者的廣泛興趣，這是路由器提供服務的最重要功能之一，例如服務品質（QoS），轉發封包，防火牆和虛擬私人網路(VPN)。隨著網路規模的擴大和軟體定義網路的興起，現有的方法已經難以支持大規模和多維度規則集的快速分類時間。此外，還必須解決日益重要的更新問題。
在此論文中，我們針對通用處理器和TCAM架構上的多維度封包分類問題提出了一種雜湊的分組方法。它是一個兩階段的設計，旨在選擇合適的維度來建立用於搜尋的資料結構，以便我們可以快速縮小搜尋空間以找到匹配的規則。使用的雜湊表比樹或其他搜尋結構更加有效。在第一階段，根據IP維度的前綴長度將規則分配給四個子集合，然後為每個子集合創建適當大小的基於雜湊之segmentation table，以將規則分配到它們的相應segment中。在第二階段，將segment分為大和小，然後使用更合適的數據結構將其分別處理，以加快分類性能。在TCAM架構上，我們還提出了一種混合範圍編碼方法，以解決將範圍格式的資料轉換為可儲存在TCAM中的三元格式的問題。實驗結果表明，與六個最新提出的方法CutTSS，TabTree，TupleMerge，CutSplit，PartitionSort和PTSSS相比，我們提出的方法在記憶體使用量，建構時間，分類時間和更新時間這四個性能指標中表現最佳。在TCAM架構上的模擬也表明該方案是有效的。與其他方法相比，每個規則所需的平均位元組僅為其他方法所需的27~99%。我們方法的建構時間比這六個方法快2.06到327.82倍。對於最重要的吞吐量比較，我們的性能比其他方法快1.92到16.65倍。最後，我們方法的更新時間快了2.22到4.54倍。在TCAM架構上的模擬還表明，該方法可以有效地降低功耗，而不會損失太多的分類性能。

Packet classification that attracts wide interests in router designers is one of the most important functionalities of routers to provide services such as Quality of Service (QoS), packet forwarding, firewall, and virtual private network (VPN). With the expansion of the network scale and the rise of software-defined networks, existing schemes had become difficult to support fast classification time for large-scale and multi-field classifiers. In addition, it is also necessary to solve the increasingly important update issues.
In this thesis, we propose a hash-based partitioning scheme for multi-field packet classification problem on general-purpose processor and TCAM architecture. It is a two-stage design that selects the suitable fields to construct the search data structure so that we can quickly narrow down the search space to find matching rules. The hash table used is more effective than the tree or other search data structures. In the first stage, the rules are divided into four subsets according to the prefix lengths of the IP address fields, and a hash based segmentation table of appropriate size for each subset is created to distribute the rules into their corresponding segments. In the second stage, segments are categorized into small and big ones that are separately processed with more suitable data structures to speed up the classification performance. On the TCAM architecture, we also propose a hybrid range encoding method to solve the problem of converting range fields into ternary format that can be stored in TCAM. The experimental results show that our proposed scheme performs best in all four performance metrics of memory consumption, construction time, classification time, and update time compared with the six most recent proposed schemes, CutTSS, TabTree, TupleMerge, CutSplit, PartitionSort, and PTSSS. The average number of bytes required per rule is only 27-99% of that needed in other methods. The construction time of our scheme is 2.06 to 327.82 times faster than these six schemes. For the most important throughput comparison, our performance is 1.92-16.65 times faster than others. Finally, the update time of our scheme is 2.22-4.54 times faster. The simulation on the TCAM architecture also shows that this scheme can effectively reduce power consumption without losing too much classification performance.

[1] D. E. Taylor, “Survey and Taxonomy of Packet Classification Techniques,” ACM Computing Surveys, vol. 37, no. 3, 2005.
[2] P. Gupta and N. McKeown, “Classifying packets with hierarchical intelligent cuttings,” IEEE Micro, Vol. 20, No. 1, pp. 34-41, 2000.
[3] S. Singh, F. Baboescu, G. Varghese, and J. Wang, “Packet classification using multidimensional cutting,” SIGCOMM '03, 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,” in SIGCOMM 99, pp. 135–146, 1999.
[6] Y.-K. Chang and H.-C. Chen, “Fast packet classification using recursive endpoint-cutting and bucket compression on FPGA,” Comput. J., vol. 62, no. 2, pp. 198-214, Feb. 2019.
[7] E. Liang, H. Zhu, X. Jin, and I. Stoica, “Neural packet classification,” in ACM SIGCOMM, 2019.
[8] W. Li, X. Li, H. Li, and G. Xie, “Cutsplit: A decision-tree combining cutting and splitting for scalable packet classification,” in IEEE INFOCOM, 2018.
[9] Y. Qi, L. Xu, B. Yang, Y. Xue, and J. Li, “Packet classification algorithms: From theory to practice,” in IEEE INFOCOM, 2009.
[10] 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, 2019.
[11] 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.
[12] 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.
[13] B. Pfaff and et al, “The design and implementation of open vSwitch,” in USENIX NSDI, 2015.
[14] J. Daly and E. Torng, “TupleMerge: Building online packet classifiers by omitting bits,” in IEEE ICCCN, 2017.
[15] J. Daly and et al, “Tuplemerge: Fast software packet processing for online packet classification,” IEEE/ACM Transactions on Networking, 2019.
[16] C. Hsieh, N. Weng, and W. Wei, “Scalable many-field packet classification for traffic steering in SDN switches”, IEEE Transactions on Network and Service Management, vol. 16, no. 1, pp. 348–361, Mar. 2019.
[17] S. Yingchareonthawornchai, J. Daly, A. X. Liu, and E. Torng, “A Sorted-Partitioning approach to fast and scalable dynamic packet classification,” IEEE/ACM Transactions on Networking, vol. 26, no. 4, pp. 1907–1920, 2018.
[18] W. Li, T. Yang, Y.-K. Chang, T. Li, and H. Li, “TabTree: A TSS-assisted bit-selecting tree scheme for packet classification with balanced rule mapping,” in ACM/IEEE ANCS, 2019.
[19] W. Li, Tong Yang, Ori Rottenstreich, X. Li, G. Xie, H. Li, Balajee Vamanan, D. Li, and H. Lin, “Tuple Space Assisted Packet Classification with High Performance on Both Search and Update,” IEEE Journal on Selected Areas in Communications, April 2020.
[20] R Pagh, “Cuckoo Hashing”, Journal of Algorithms, vol. 51, pp. 122-144, 2004.
[21] 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.
[22] 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.
[23] 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.
[24] Y.-C. Cheng and P.-C. Wang, “Scalable multi-match packet classification using TCAM and SRAM,” IEEE Trans. Comput., vol. 65, no. 7, pp. 2257–2269, Jul. 2016.
[25] X.Li, Y.Lin and W.Li, “GreenTCAM:A memory- and energy-efficient TCAM-based packet classification,” In International Conference on Computing, Networking and Communications (ICNC), 2016.
[26] Abbasi, Mahdi, Shakoor Vakilian, Ali Fanian and Mohammad R. Khosravi. “Ingredients to Enhance the Performance of Two-Stage TCAM-Based Packet Classifiers in Internet of Things: Greedy Layering, Bit Auctioning and Range Encoding.” EURASIP Journal on Wireless Communications and Networking, pp.1-15 2019.
[27] Y.-K. Chang, C.-C. Su, Y.-C. Lin, and S.-Y. Hsieh, “Efficient gray-code-based range encoding schemes for packet classification in TCAM,” IEEE/ACM Trans. Netw., vol. 21, no. 4, pp. 1201–1214, Aug. 2013.
[28] Y.-K. Chang and Y.-C. Lin, “Dynamic segment trees for ranges and prefixes,” IEEE Trans. Comput., vol. 56, no. 6, pp. 769–784, Jun. 2007.
[29] A. Bremler-Barr, Y. Harchol, D. Hay, and Y. Hel-Or, “Encoding short ranges in tcam without expansion: Efficient algorithm and applications,” IEEE/ACM Transactions on Networking, vol. 26, no. 2, pp. 835–850, 2018.
[30] 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.
[31] H. Alimohammadi, M. Ahmadi, Clustering-based many-field packet classification in software-defined networking. Journal of Network and Computer Applications 147, 102428 (2019).
[32] 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.