封包分類在現今的路由器中扮演著很重要的腳色，它提供了許多不同的功能服務，如: VPN、 QoS及防火牆。而現今的封包分類面臨許多挑戰，如:支援大量的規則、維持好的效能表現等，而為了達成這些挑戰，有很多演算法嘗試解決這些問題，如決策樹演算法:HiCuts、 HyperCuts、EffiCuts；分解類型演算法:RFC，上述方法對於搜尋速度上是有幫助的，但會導致大量的規則複製，因此也會使的需要大量的記憶體來儲存這些複製的規則。
因此，在此論文中，我們提出Maintree with Segmentation Table(MST)。MST先利用EffiCuts的分類方法將規則集合做分類，再將這些分類後的子集合建成樹狀結構，在利用其中的一棵樹當成主樹，並利用此樹對其它的樹聯結避免要搜尋其它樹時還要從頭開始搜尋。並在樹葉中除了使用線性搜尋演算法外，也使用了查詢表來加速線性搜尋，查詢表是用來減少需要搜尋的規則數目，目的是為了減少記憶體存取。另外，規則擁有不同的優先權，當封包找到某條規則後，會記錄此規則的優先權值，之後再對其它的規則做檢查時，就可以利用這個優先權值來找到最符合的規則。這也可以幫助我們減少搜尋不必要的規則。與其它的方法比較，如EffiCuts這類的樹狀結構的演算法，MLT有較少的記憶體使用量及記憶體存取次數，在記憶體使用量上，MLT平均一條規則需要使用31 bytes ， 而EffiCuts一條規則需要267 bytes；記憶體存取次數方面，MLT平均一個封包需要存取33次，而EffiCuts平均一個封包需要存取53次。

Packet classification plays an important role in router. It provides many service, such as: Virtual Private Network(VPN)、 Quality of Service (QoS) and Fire Wall(FW). However, packet classification has some major challenges, such as supporting large rule set, sustaining high performance and so on. Many algorithms were used to solve these problems include decision tree based algorithms, such as HiCuts, HyperCuts and EffiCuts and decomposition based algorithms, such as RFC. These algorithms have good performance on memory access. However, they suffer from duplication rules. Therefore, these algorithms need more memory to store these duplication of rules.
In this thesis, we propose an algorithm, named Maintree with Segmentation Table (MST), which uses the partition of the EffiCuts algorithm to group the ruleset into subsets. And these subsets will be constructed as trees. Then, a tree called main-tree, is chosen form these trees and links to the related nodes in the other trees to avoid traversing these other trees from scratch. We also construct the lookup table in the bucket to speedup the linear search in the buckets. The lookup table is used to decrease number of rules that need to be searched for the input headers. Besides, the rules have different priorities. If the input packet matched a rule, the priority of the matched rule is recorded. When the rules in a bucket are ready to be compared, we check if the priority of the matched rule found previously is already higher than the local maximum priority of the bucket in order to avoid comparing the rules in the bucket entirely. Hence, the priority helps us using less memory access on the searching of the rules. Compared with the well-known method such as EffiCuts, MLT has less memory usage and memory access. The average of memory usage is 31 bytes per rule in MLT and the average of memory usage is 267 bytes per rule in EffiCuts. The average of memory access is 33 per packet in MLT and the average of memory access is 53 per packet in EffiCuts.

[1] P. Gupta and N. McKeown, “Algorithms for packet classification.” IEEE Network,
vol.15, no. 2, pp.24–32, 2001.
[2] DAVID E. TAYLOR, “Survey and Taxonomy of Packet Classification Techniques.” ACM Computing Surveys, Vol 37, no. 3, pp. 238-275, 2005.
[3] Peng He, Hongtao Guan, Laurent Mathy, Kavé Salamatian and Gaogang Xie, “Toward Predictable Performance in Decision Tree based Packet Classification Algorithms”, Local & Metropolitan Area Networks (LANMAN), 2013 19th IEEE Workshop on, pp. 1-6, April. 2013.
[4] P.Gupta, “Classifying packets with hierarchical intelligent cuttings.” IEEE Micro,
vol. 20, no. 1, pp. 34-41, 2000.
[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), pp. 213–224, 2003
[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, pp. 207-218, 2010.
[7] Wenjun Li and Xianfeng Li, “HybridCuts: A Scheme Combining Decomposition and Cutting for Packet Classification” 2013 IEEE 21st Annual Symposium on High-Performance Interconnects, pp. 41-48, Aug. 2013.
[8] Chang Chen, Liangwei Cai and Yang Xiang; Jun Li, “SwinTop: Optimizing memory efficiency of packet classification in network devices”, Communication Software and Networks (ICCSN), 2015 IEEE International Conference on, pp. 125-133, June. 2015.
[9] Og̃uzhan Erdem, Hoang Le and Viktor K. Prasanna,“Hierarchical hybrid search structure for high performance packet classification” INFOCOM, 2012 Proceedings IEEE, vol. 15, no. 3, pp. 1989-1906, March. 2012.
[10] Pankaj Gupta and Nick McKeown, “Packet Classification on Multiple Fields”,
Proc. Sigcomm, Computer Communication Review, vol. 29, no. 4, pp 147- 60, September 1999.
[11] T.V. Lakshman and D. Stiliadis. “High-Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching”, Proceedings of ACM Sigcomm, pages 191-202, September 1998.
[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] V. Srinivasan, S. Suri, G. Varghese, “Packet classification using tuple space search.” Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication (ACM SIGCOMM 1999), vol. 29, no. 4, pp. 135-146, Oct. 1999.
[14] P. Warkhede; S. Suri, G. Varghese, “Fast packet classification for two-dimensional conflict-free filters.” INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, vol 3, pp. 1434-1443, apr. 2001.
[15] 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.
[16] Cheng-Liang Hsieh and Ning Weng, “Many-Field Packet Classification for Software-Defined Networking Switches.” Proceedings of the 2016 Symposium on Architectures for Networking and Communications Systems, pp. 13-24, March 2016.
[17] Hai Sun; Yan Sun; Victor C. Valgenti; Min Sik Kim, “OpenFlow Accelerator: a Decomposition-based Hashing Approach for Flow Processing”, 2015 24th International Conference on Computer Communication and Networks (ICCCN). PP. 1-10, Aug. 2015.